Los algoritmos genéticos son tan nobles que, aunque estén mal implementados, funcionan: Carlos Coello Coello

“Los algoritmos genéticos se han usado para el diseño de múltiples objetos, desde optimizar el desempeño del tren bala en Japón hasta realizar aplicaciones de Linux, pasando por su uso en el cine”, sostuvo Carlos Coello Coello, miembro de El Colegio Nacional, en la segunda sesión del curso Una introducción a la computación evolutiva: conceptos básicos y aplicaciones, realizada el 16 de enero en el Aula Mayor de la institución.

Comentó que las aplicaciones de los algoritmos genéticos van desde la optimización y el aprendizaje de máquina, hasta las bases de datos, pasando por el reconocimiento de patrones, la planeación de movimientos de robots y las predicciones. La computación evolutiva es una dinámica basada en el neodarwinismo, que se utiliza para resolver problemas de alta complejidad. Ésta simula el proceso evolutivo de una población sujeta a un proceso de selección basado en su aptitud y que se recombinan (sexualmente) entre ellos, explicó el experto en matemáticas aplicadas y algoritmos de optimización multi-objetivo. En este proceso se someten a mutaciones aleatorias, de tal forma que los individuos más aptos producen descendientes “mejores” que ellos.

Agregó que la computación evolutiva considera que toda la diversidad de vida en el planeta se explica mediante cuatro procesos que se simulan: competencia, reproducción, selección natural y mutación. Y con esa simulación se busca resolver problemas de optimización de alto grado de dificultad.

Antes de pasar a los tres grandes paradigmas de la computación evolutiva, Coello Coello realizó un recorrido por la historia de esta área del conocimiento de las ciencias de la computación. Ver la evolución como proceso de aprendizaje surge a partir de los años 30, con el científico estadounidense Walter Bradford Cannon, quien planteó que la evolución se podía ver como un proceso de aprendizaje de la naturaleza que optimiza las especies.

A finales de los 50 y principios de los 60, hubo científicos biológicos interesados en simular la evolución en una computadora digital, como Alex S. Fraser, que realizó simulaciones similares a lo que hoy es el algoritmo genético, y George E. P. Box, que creó un algoritmo de optimización que simulaba la evolución.

Por su parte, George F. Friedman propuso aplicar las técnicas evolutivas a la robótica, en los 50 propuso evolucionar en circuitos de control similares a las redes neuronales actuales. Nils Aall Barricelli fue un matemático noruego-italiano que, entre 1953 y 1956, desarrolló las que probablemente fueron las primeras simulaciones de un sistema evolutivo en una computadora digital, lo que dio origen a la disciplina conocida como vida artificial.

Fue el matemático John R. Koza, quien en 1989 propuso un tipo de representación de árbol con la cual pudo utilizar un algoritmo evolutivo, implementó un algoritmo genético, en el que, en vez de utilizar cadenas binarias, utilizó expresiones S, árboles, y así nació un área que hoy se llama programación genética. El científico recibirá un premio como pionero en la computación evolutiva este 2024, en Japón.

Los tres grandes paradigmas de la computación evolutiva

Coello Coello explicó que los tres grandes paradigmas que conforman la computación evolutiva son: la programación evolutiva, las estrategias evolutivas y los algoritmos genéticos. De acuerdo con el informático estadounidense Lawrence J. Fogel, la programación evolutiva veía a la inteligencia como un comportamiento adaptativo y su motivación era resolver problemas autómatas de Estados Unidos, por ejemplo, un problema con tres estados, A, B, y C, requería de una tabla de transiciones con los elementos: estado actual, símbolo de entrada, estado siguiente y símbolo de salida. Lo que decía esta tabla es que, por ejemplo, si estoy en el estado A y recibo como entrada un 1, entonces produzco como salida una b y me voy a regresar al estado A.

El colegiado subrayó que el algoritmo básico de la programación evolutiva es, primero, generar aleatoriamente una población inicial al azar; segundo, aplicar mutación, normalmente hay varios operadores disponibles; tercero, calcular la aptitud de cada hijo y usar procesos de selección mediante torneo, el torneo compara a dos individuos en términos de su aptitud, el que tenga la mejor aptitud gana, y se le da una probabilidad de sobrevivir al que no para determinar cuáles serán las soluciones que se retendrán; y cuarto, regresar al paso 2, al menos que se haya alcanzado un cierto criterio de paro.

Dijo que uno de los paradigmas menos utilizados de la programación evolutiva es el de las aplicaciones que requieren predicción, generalización, juegos y control automático.

En relación al segundo paradigma, el de las estrategias evolutivas, el científico mexicano sostuvo que fueron desarrolladas en 1964 por un grupo de estudiantes alemanes de ingeniera encabezado por Ingo Rechengberg. Su objetivo era resolver problemas hidrodinámicos de alto grado de complejidad. “Él dijo voy a generar un vector de números reales que tenga todas las variables del problema al azar, después evaluó la función de objetivo, luego tomó una de las variables y la modificó sumándole o restándole un valor, lo que dio pie a un segundo individuo que fue el hijo y se evaluó la función objetivo en cada uno, si el hijo es más apto se elimina al padre. Por eso está técnica evolutiva se le llama (1+1)-EE, el + significa que la selección es extintiva, no es preservativa como en la programación evolutiva, eso significa que el menos apto se va a morir siempre”.

Detalló que, en la versión original, Rechengberg usaba un sólo padre y con él generaba un sólo hijo, este hijo se mantenía si era mejor que el padre o de lo contrario se eliminaba, a este tipo de selección se le llama extintiva, porque los peores individuos tienen una probabilidad de cero de ser seleccionados.

Después Propuso otra versión llamada (μ+1), que significa que se tienen Miu padres que generan un sólo hijo y fue el científico Schwefel, quien introdujo el uso de los múltiples hijos en las denominadas (μ+ λ)-EEs, es decir, se pueden generar 50 padres y generar 50 o más hijos, pero sólo se quedarán los 50 mejores. Schwefel propuso que una mutación es exitosa cuando el hijo es mejor que el padre y a esto lo denominó la “regla de éxito 1/5”, lo óptimo es que tenga un quinto de mutaciones exitosas, es decir, que una de cada cinco nutaciones lo será, no debe ser menos ni más.

Este procedimiento dio paso a la auto adaptación, lo que significa hacer que el algoritmo ajuste sus parámetros por sí mismo y lo que permite al usuario no definir los parámetros de la estrategia evolutiva, los hace el algoritmo mismo. Así operan actualmente. Las estrategias operan a nivel del individuo, aquí sí hay recombinación, pero es distinta a la del algoritmo genético.

Existen dos tipos de operadores de recombinación de las estrategias evolutivas, los sexuales, el operador actúa sobre dos individuos elegidos aleatoriamente de la población de padres; y los Panmíticos, se elige un sólo padre al azar y se mantiene fijo, mientras se elige al azar un segundo padre para componente de sus vectores, se les llama multiparentales, porque son bastantes padres los que pueden generar dos o más hijos.

Las estrategias evolutivas han sido muy exitosas en problemas de optimización en los cuales todas las variables son números reales, sin embargo, como en sus orígenes, las únicas publicaciones que habían de las estrategias estaban en alemán, hasta los años 80 muy poca gente las había usado. A la fecha sigue igual.

El tercer paradigma de la computación evolutiva son los algoritmos genéticos, aseguró Carlos Coello, quien explicó que éstos enfatizan la importancia de la cruza, es decir, aquí el operador fundamental es la recombinación que es siempre sexual, dos padres generan siempre dos hijos, y la mutación existe como un operador secundario, es decir, se aplica con menos frecuencia que la recombinación, la mutación es fundamental en el algoritmo genético, porque es el que garantiza que todo el espacio de búsqueda esté conectado. La cruza es un operador cerrado, lo que significa que no garantiza generar todas las soluciones posibles, por eso se requiere la mutación.

“Su algoritmo básico es sencillo, se genera aleatoriamente una población inicial, se calcula la aptitud de cada individuo, se hace una selección probabilística con base en la aptitud, se aplican operadores genéticos de cruza y mutación para generar la siguiente población, y se hace el ciclo hasta que cierta combinación satisfaga. La representación tradicional es la cadena binaria de tipo 0110 1101 0011 1001, a la cadena se le llama cromosoma y a cada posición de la cadena se le denomina gen y al valor dentro de esta posición se le llama alelo”.

Para aplicar un algoritmo genético se requieren cinco componentes básicos: primero, la representación de las soluciones potenciales del problema; segundo, una forma de crear una población inicial de posibles soluciones; tercero, una función de evaluación que juegue el papel del ambiente, clasificando las soluciones en términos de su “aptitud”; cuarto, son los operadores genéticos que alteran la composición de los hijos que se producirán para las siguientes generaciones, normalmente son cruza y mutación; y quinto, los valores para los diferentes parámetros que utiliza el algoritmo genético, tamaño de la población, probabilidad de cruza,  número máximo de generaciones, etcétera.

“La parte más difícil es saber qué parámetros son los adecuados, porque hay problemas muy raros donde intuitivamente uno dice: si pongo mayor población hay mayor diversidad”, pero hay problemas donde si se aumenta la población le puede ir peor al algoritmo evolutivo. Sin embargo, los algoritmos genéticos son tan nobles que, aunque están mal implementados, funcionan, eso es lo más desconcertante de ellos, aún en condiciones extremas logran funcionar”.

El colegiado concluyó que hoy en día varios algoritmos evolutivos son considerados métodos de búsqueda directa y son una herramienta muy poderosa para resolver problemas de optimización de alta complejidad.

La primera sesión del curso Una introducción a la computación evolutiva: conceptos básicos y aplicaciones, que se lleva a cabo del 15 al 19 de enero en el Aula Mayor de El Colegio Nacional, se encuentra disponible en el Canal de YouTube de la institución: elcolegionacionalmx.

jb