La Habana, Cuba. – Una forma de enfrentar los problemas, es ver como lo ha hecho la Naturaleza en el proceso de evolución. Uno de estos casos es el que presento hoy, Los Algoritmos Genéticos son utilizados para resolver problemas de búsqueda y optimización pues se basan en hacer evolucionar poblaciones de soluciones hacia valores óptimos del problema.
Como se dice popularmente, lo primero, es lo primero. Un algoritmo es una serie de pasos ordenados, secuenciales, libre de ambigüedades que describen el proceso para alcanzar un objetivo. Un algoritmo genético es aquel que usa procesos que simulan los de la evolución biológica de las especies. Es una técnica de Inteligencia Artificial basada en la idea de que el “elemento” que sobrevive es el que está mejor adaptado al medio, es decir la misma que subyace a la teoría de la evolución que formuló Charles Darwin y que combina esa idea de la evolución con la genética.
Por ejemplo, entre un camaleón verde y uno rojo que viven en la selva, es más fácil que sobreviva el de color verde pues está mejor adaptado al medio en el que vive (la selva en este caso, que es de color verde). Sin embargo, el camaleón rojo es muy probable que no sobreviva, ya que será comido con rapidez. Además, tampoco tendrá la oportunidad de reproducirse y trasladar sus genes (entre ellos el color rojo) a su descendencia. Es por eso que los individuos que se reproducen dando lugar a descendencia con sus genes son los que están mejor adaptados. Por lo tanto, las generaciones están cada vez mejor adaptadas pues son combinación de los mejores genes de las generaciones anteriores.
Además, esa teoría de la evolución introduce un concepto muy interesante que son las mutaciones. Una mutación es un pequeño cambio que se produce de manera aleatoria en ciertos individuos e introduce de esa manera versatilidad en las poblaciones. Habrá mutaciones que den lugar a cambios favorables y otros desfavorables. Siguiendo con los camaleones de la selva, imagine que un individuo sufre una mutación por la cual su cola, que hasta entonces era rígida, ahora no tiene huesos, eso le permite no caerse de los árboles e incluso alcanzar cosas más lejanas con ella. En ese caso el nuevo camaleón está todavía mejor adaptado por lo que le será más fácil sobrevivir e introducirá sus genes en la población que después de cierto número de generaciones tendrá la cola sin huesos. Sin embargo, si la mutación es la de quitarle la lengua, ese camaleón tendrá muchas dificultades para alimentarse y terminará muriendo de hambre, por lo que esta mutación no se introducirá en la población.
Tomando en consideración estas ideas, en los años 1970, el científico estadounidense John Henry Holland, sugirió una de las líneas más prometedoras de la Inteligencia Artificial, la de los Algoritmos Genéticos, lo que fue retomado por en 1989 por David Goldberg como un método de optimización de búsqueda global, debido a que ese tipo de métodos explora todo el espacio de soluciones del problema permitiendo salir de posibles óptimos locales e ir en busca de óptimos globales. Para entender lo que es la optimización hay que considerar que la programación matemática intenta resolver procesos que tienen diferentes posibles soluciones, pero sólo una de ellas corresponde al óptimo global, es decir la solución que se ajusta mejor a las condiciones del mismo problema. Cualquier otra solución que se parezca al óptimo global es un óptimo local. Los Algoritmos Genéticos hacen evolucionar una población de individuos sometiéndola a acciones aleatorias semejantes a las que actúan en la evolución biológica (mutaciones y recombinaciones genéticas), así como también a una selección de acuerdo con algún criterio, en función del cual se decide cuáles son los individuos más adaptados, que sobreviven, y cuáles los menos aptos, que son descartados. Los Algoritmos Genéticos se enmarcan dentro de los algoritmos evolutivos.
Los Algoritmos Genéticos son de probada eficacia en caso de querer calcular funciones no derivables (o de derivación muy compleja) aunque su uso es posible con cualquier función. Deben tenerse en cuenta también las siguientes consideraciones: Si la función a optimizar tiene muchos máximos o mínimos locales se requerirán más iteraciones del algoritmo para «asegurar» el máximo o mínimo global. Si la función a optimizar contiene varios puntos muy cercanos en valor al óptimo, solamente se puede «asegurar» que se encuentre uno de ellos (no necesariamente el óptimo).
El asunto es como pasar del mundo de las ciencias biológicas al de la Inteligencia Artificial. Lo que se hace es transformar la resolución de un problema en un conjunto de soluciones en el que cada una de ellas funciona como si fuera un individuo. Se aborda el problema de forma tal que el conjunto de soluciones seleccionados es como una población, una población de soluciones. Imagine que el problema a resolver es determinar el camino más corto para ir de San Cristóbal a Mayarí y se tienen decenas de soluciones. Cada camino que se encuentre podría ser una opción, si se aplica un algoritmo genético, cada camino encontrado sería un individuo. Para poder aplicar Algoritmos Genéticos se debe convertir las soluciones al problema en vectores matemáticos, un vector para ir de San Cristóbal a Mayarí puede ser uno que enumere las ciudades por las que vas pasando. Habrá muchos recorridos: unos más largos y otros más cortos, unos tendrán más tráfico, otros tendrán menos tráfico.
Los Algoritmos Genéticos parten de un conjunto de soluciones aleatorio. Continuando con el ejemplo mencionado, se ponen ciudades entre los dos puntos, y se puedo pasar incluso por Nueva Gerona para ir a Mayarí. Obviamente esa combinación no va a ser eficiente pero el procedimiento acabará descartándola. Una vez que se tiene ese grupo de soluciones inicial aleatorio se aplica la llamada función objetivo, que en este caso es llegar en el menor tiempo posible a Mayarí. Esa función es el tiempo que se tarda considerando el tráfico y los kilómetros a recorrer. La función objetivo sirve para clasificar las soluciones aleatorias: las que duran menos tiempo son mejores y las que duran más tiempo son peores. Una vez clasificadas entra la “genética” en juego, Se reproducen las soluciones, como se reproducen los individuos en una población, y se implementan los tres mecanismos que intervienen en la selección de las especies: la reproducción en sí, el cruzamiento y la mutación.
Para imitar la reproducción hay diferentes mecanismos matemáticos, uno de ellos es a que a partir de la función objetivo se reproduzcan más aquellas soluciones que son mejores y por lo tanto las que son peores desaparecerán; al aplicar el cruzamiento se combinan unas soluciones con otras. Por ejemplo, se toma la mitad de una solución que pasaba por Nueva Gerona y se combina con otra solución que pasaba por Plaza de la Revolución. Se van realizando combinaciones y finalmente, se aplica un procedimiento de mutación de forma matemática. Si antes se pasaba por Nueva Gerona se implementa matemáticamente que me cambie esa ciudad por ejemplo por cualquier otra ciudad de la Isla y ya no pasa por Nueva Gerona, sino por Cocodrilo. Eso es como aplicar las tres dinámicas que existen en el mundo biológico cuando se reproducen las especies.
Una vez que se aplicó todo eso, se reevalúa la función objetivo de la nueva población. Se apreciará que algunas soluciones habrán mejorado y otras habrán empeorado. al volver a aplicar el mecanismo de la reproducción basado en la función objetivo, se van a reproducir en mayor número las soluciones que tardan menos y se van a eliminar aquellas que tarden mucho. Y se sigue repitiendo el proceso. Así funcionan los Algoritmos Genéticos. Cuando se busca resolver problemas en un campo enorme no es viable el procedimiento enumerativo de ir de una en una porque pueden existir millones y millones de posibles soluciones. Esos algoritmos combinan la aleatoriedad porque se inician con un conjunto de soluciones totalmente aleatorio, pero luego están dirigidas porque buscan el resultado óptimo. Y gracias a ello encuentras soluciones muy eficientes en muy poco tiempo de computación.
Las aplicaciones de los Algoritmos Genéticos son muchas, y entre ellas se pueden mencionar el diseño de componentes automovilísticos, automatización de los sistemas de comercio en el sector financiero, la logística en la carga de contenedores, el comportamiento de robots, la calibración y detección de daños en estructuras civiles, bioinformática, optimización de estructuras moleculares, predicción del plegamiento de proteínas, construcción de horarios en grandes universidades, y el problema del viajero ambulante entre otras.
Entre las limitaciones de los Algoritmos Genéticos se encuentran las siguientes: Para problemas de alta complejidad la función de evaluación puede tornarse demasiado costosa en términos de tiempo y recursos. Puede haber casos en los cuales dependiendo los parámetros que se utilicen para la evaluación el algoritmo podría no llegar a converger en una solución óptima o bien terminar en una convergencia prematura con resultados no satisfactorios. La «mejor» solución lo es solo en comparación a otras soluciones por lo que no se tiene claro un criterio de cuándo detenerse ya que no se cuenta con una solución específica. No es recomendable utilizarlos para problemas que buscan respuesta a problemas que convergen en soluciones simples como Correcto/Incorrecto ya que el algoritmo difícilmente convergerá y el resultado será tan válido como escogerlo al azar.
Espero les haya resultado interesante conocer sobre esta tecnología, nacida de la convergencia de conceptos de las ciencias de la vida y las computacionales para trabajar problemas de optimización. Aquí lo dejo y recuerden si me ven por ahí, me saludan.