La palabra optimización o, más bien, el verbo optimizar, suele estar presente en diferentes aspectos de nuestra vida cotidiana, pero, ¿a qué nos referimos exactamente cuando decimos que estamos ante un problema de optimización en matemáticas, estadística, economía o computación?
Un problema de optimización se define como el problema que trata de encontrar la mejor solución que cumpla ciertas restricciones, a partir de todas las soluciones factibles. En muchos casos, este tipo de problemas pueden llegar a ser muy difíciles de solucionar con técnicas tradicionales, por lo que se aplican algoritmos inspirados en el funcionamiento de la naturaleza, que replican la forma con la que ésta afronta problemas de optimización.
Estos métodos se conocen con el nombre de algoritmos bioinspirados y tratan de imitar la evolución natural de las especies y la respuesta de los sistemas sociales ante los desafíos que se les presentan. Dentro de estos, como veremos, se encuentra la familia de los algoritmos evolutivos y, más en concreto, los algoritmos genéticos, que se basan en la evolución de las especies y en la de los cromosomas respectivamente.
Características de los algoritmos bioinspirados
Los algoritmos bioinspirados se caracterizan por ser no determinísticos. Además, presentan a menudo, implícitamente, una estructura paralela y son adaptativos. En nuestro día a día nos encontramos con aplicaciones de ellos continuamente, para optimizar el diseño de antenas de comunicación, de tácticas militares, de fármacos, de alas de aviones o incluso de salas de conciertos, el transporte de materiales, el cálculo de estrategias de mercado, etc.
Dentro de un algoritmo bioinspirado, encontramos las siguientes partes bien diferenciadas:
- Población: conjunto de candidatos a ser solución.
- Mecanismo de Evolución: conjunto de métodos por los cuales se modifica la población.
- Mecanismo de Calificación: conjunto de métodos por los cuales se asigna un valor a cada elemento de la población (solución). Para asignar las calificaciones se utiliza normalmente la función a optimizar.
- Condiciones de Parada: procedimiento que controla si se ha encontrado una solución o se ha alcanzado un número de operaciones determinado con anterioridad.
Estos elementos pueden categorizarse en dos grupos en función de si se trata de elementos dependientes del problema o, por el contrario, son dependientes del propio algoritmo. La población, el mecanismo de calificación y las condiciones de parada vienen determinados por el problema a resolver, mientras que el mecanismo de evolución es característico del algoritmo.
Los algoritmos bioinspirados abarcan, a su vez, una amplia gama de algoritmos que incluyen algunos modelos de computación, como los algoritmos evolutivos, la inteligencia de enjambre, los algoritmos inmunológicos y las redes neuronales. Todos estos métodos pueden agruparse bajo un término general llamado “inteligencia computacional”, que es un subcampo de la inteligencia artificial.
Algoritmos evolutivos para la optimización
Los algoritmos evolutivos son una familia de algoritmos bioinspirados que tratan de replicar el proceso de evolución natural de las especies propuesto por Darwin para resolver problemas de optimización. En el libro El origen de las especies, Darwin se plantea el universo como un conjunto de individuos en constante competición y evolución para poder perpetuar su especie en el tiempo. Las especies se crean, evolucionan y desaparecen si no se adaptan, de forma que solo las que mejor se adapten al medio sobreviven para perpetuar sus aptitudes.
De acuerdo con esta visión de la evolución, los algoritmos evolutivos parten de un conjunto inicial aleatorio de soluciones candidatas a un problema (la población de individuos), que se somete a ciertas modificaciones y a un proceso de selección que favorece a las mejores. Cada ciclo de transformación y selección constituye una generación, de tal modo que, tras un cierto número de generaciones, se espera que el mejor individuo de la población esté cerca de la solución óptima.
Los algoritmos evolutivos combinan la búsqueda aleatoria, dada por las transformaciones de la población, con una búsqueda dirigida, que viene dada por la selección. Por lo tanto, podemos definir los principales componentes de un algoritmo evolutivo como los siguientes:
- Población de individuos, que son una representación de las posibles soluciones.
- Procedimiento de selección basado en la aptitud de los individuos para resolver el problema.
- Procedimiento de transformación para construir nuevos individuos a partir de los anteriores.
La característica fundamental de estos algoritmos reside en los métodos que se aplican para la generación de soluciones: se parte de un conjunto de soluciones iniciales y se van empleando un conjunto de operadores de búsqueda para ir refinando la solución final. Para realizar dicho proceso de refinamiento de las soluciones, se pueden utilizar técnicas clásicas complementadas con mecanismos biológicos de exploración: población de soluciones, operadores genéticos.
El siguiente diagrama refleja de una forma sencilla la estructura general de los algoritmos evolutivos:
El problema del viajante (también conocido por TSP por sus siglas en inglés) nos permite ilustrar estos conceptos de una forma clara. Este problema responde a la siguiente pregunta: dada una lista de ciudades y las distancias entre cada par de ellas, ¿cuál es la ruta más corta posible que permita al viajante visitar cada ciudad exactamente una vez y al finalizar regrese a la ciudad origen?
En este caso, la población inicial de soluciones serían las posibles rutas que cumplan las condiciones, es decir, que empiecen y comiencen en la ciudad de origen y que pasen una sola vez por cada ciudad. Para calificar estas soluciones utilizaremos la distancia total de la ruta que trace cada una. Una vez evaluadas todas las soluciones, se repetirá el siguiente proceso hasta que alcancemos la condición de parada (fijaremos previamente un número máximo de iteraciones): se escogen pares de soluciones a las que se le aplica una serie de transformaciones, se seleccionan aquellas con mejor puntuación y se reemplazan por las anteriores en la población inicial para constituir soluciones mejores. Finalizado este proceso iterativo, se obtendrá la mejor ruta de la última generación.
Existen determinadas modificaciones sobre el esquema general del algoritmo evolutivo, ya sea por la forma en la que se representa la solución o por los métodos de transformación y selección que se utilicen, que dan lugar a diferentes subtipos de algoritmos dentro de esta clase: estrategias evolutivas, programación evolutiva, algoritmos genéticos, programación genética… Los algoritmos genéticos constituyen el enfoque más completo de todos ellos, ya que resumen todas las ideas fundamentales de la computación evolutiva.
Optimización con algoritmos genéticos
Los algoritmos genéticos están inspirados en la evolución de los cromosomas. Los genes representan el material genético básico, los cromosomas son secuencias de genes y la población es un conjunto de cromosomas que evoluciona en las distintas generaciones. En este proceso, el nuevo material genético se obtiene mediante cruces y mutaciones de las estructuras de los cromosomas existentes, de tal modo que las que son mejores sobreviven con más probabilidad.
En un algoritmo genético, cada individuo o solución (cromosoma) de la población inicial está definido como una estructura de datos que representa una posible solución del espacio de búsqueda del problema y se simboliza como una cadena binaria (0-1). Cada individuo se define por su valor aptitud o calificación, que se obtiene al evaluarlo mediante la función a optimizar.
Para la obtención de las siguientes generaciones, se crean nuevos individuos a partir de la población inicial utilizando el operador de cruce, que implica la combinación de los individuos entre sí, y el operador de mutación, que hace referencia a cambios en partes de la propia estructura de un individuo, ambos de forma aleatoria:
Una nueva generación es el resultado de la utilización del operador de selección sobre el valor de aptitud de la población obtenida tras el cruce y la mutación, es decir, aquel individuo con mayor valor de aptitud tiene mayores posibilidades de ser seleccionado en la siguiente generación. El operador de selección se encarga de mantener constante en todo momento el número de individuos de la población, así como la diversidad.
Se realizan múltiples copias de los mejores candidatos (los que han obtenido mayor valor), a las que se les aplicarán cambios aleatorios durante el proceso de copia. Esta descendencia prosigue con la siguiente generación, formando un nuevo conjunto de soluciones candidatas que son nuevamente sometidas a un proceso de evaluación de aptitud. Las candidatas que han empeorado o no han mejorado con los cambios aplicados son eliminadas. De nuevo, se seleccionan y copian estos individuos vencedores hacia la siguiente generación con cambios aleatorios, y el proceso se repite.
Se espera que la aptitud media de la población se incremente en cada ronda y, por tanto, tras varias iteraciones del proceso (hasta alcanzar la condición de parada fijada previamente), el algoritmo converge al individuo con mejor valor de aptitud, el cual representará la solución óptima o, en su defecto, la subóptima del problema.
Si volvemos al problema del viajante, en este caso, los genes serían las ciudades y, por tanto, los cromosomas representarían las rutas candidatas. Un cromosoma tiene que ser una permutación de la lista de ciudades para que sea una ruta válida. Si se cruzan o mutan permutaciones, los cromosomas resultantes pueden no ser permutaciones y, por tanto, no representar una solución válida. Para evitar este problema, hay que diseñar operadores de cruce y de mutación específicos.
Librería Inspyred de algoritmos bioinspirados
Para implementar los algoritmos bioinspirados en Python contamos con una librería de código abierto llamada Inspyred. En ella se incluyen todos los tipos de algoritmos evolutivos, así como los basados en inteligencia de enjambre e inmunocomputación.
El principio de diseño central de Inspyred es separar los componentes específicos del problema de los componentes específicos del algoritmo de una manera clara para que los algoritmos sean lo más generales posible en una variedad de problemas diferentes. La librería proporciona versiones canónicas (clases) de muchos de estos algoritmos, así como benchmarks orientados a probar su funcionamiento.
En el Instituto de Ingeniería del Conocimiento (IIC) desarrollamos proyectos de optimización donde es posible encontrar soluciones a diversos problemas de negocio mediante la aplicación de los algoritmos bioinspirados y técnicas de aprendizaje por refuerzo.