Algoritmos que evolucionan, ¿es posible? 

Hoy en día existen diferentes métodos computacionales usados para resolver problemas en diversas áreas de ciencia e ingeniería. Entre ellos podemos encontrar los algoritmos evolutivos. El nombre puede sonar un poco raro, y la pregunta que siempre surge es ¿los algoritmos evolucionan? Los algoritmos evolutivos por si solos no evolucionan. Sin embargo, los diseñadores de estos métodos toman como base algunos comportamientos de la teoría de la evolución para generar operadores que simulen dichos comportamientos. Cuando hablamos de este tipo de algoritmos, se debe tener en cuenta que trabajan con una población de soluciones y dependiendo del contexto del algoritmo cada elemento de la población puede llamarse individuo. Cada individuo esta conformado por un numero definido de variables, que dependen de la dimensión del problema a resolver (ver Figura 1).

Figura 1. Ejemplo de la estructura de un algoritmo evolutivo.

Los operadores comúnmente usados para modificar la población son el operador de cruzamiento (también llamado cruce o recombinación), el operador de mutación y el de selección. En el cruzamiento, se consideran dos elementos de la población, los cuales son llamados padres, de tal manera que se tiene al padre 1 y al padre 2. El método más sencillo para el cruzamiento contempla el uso de un punto de corte, el cual sirve como referencia para saber cuántas y cuales variables serán intercambiadas de cada padre. Al realizar el intercambio de información se generan dos hijos que contienen características de ambos padres. La Figura 2 muestra a detalle cómo se realiza este proceso. 

Figura 2. Operador de cruzamiento.

Por otra parte, la mutación consiste en modificar un individuo de manera interna, esto puede ser en todas sus variables o solo en algunas de ellas. Para esto a nivel computacional lo más sencillo es intercambiar las posiciones de los elementos del individuo (ver Figura 3), pero también es posible usar un valor aleatorio que modifique al individuo. Con esto, se logra preservar la información, pero también hacer una modificación relevante.

Figura 3. Operador de mutación.

Los operadores de cruzamiento y mutación son fundamentales en el computo evolutivo, sin embargo, también es importante saber cómo elegir los elementos que van a ser modificados. Para esto, los individuos son previamente evaluados y con esto se logra saber la aptitud que cada uno de ellos tiene para resolver el problema. El método más simple para elegir a los padres es mediante un proceso elitista, donde los mejores padres tienen una mayor probabilidad de ser seleccionados. Existen también otras formas de realizar el proceso de selección, por ejemplo, el mecanismo de la ruleta, el torneo, o la selección jerárquica. 

Una vez, que los operadores de selección, cruzamiento y mutación se han aplicado, lo siguiente es reemplazar algún (o algunos) miembro de la población con los nuevos individuos. Para esto, lo mas simple es descartar los que tienen peor aptitud. Sin embargo, como uno de los propósitos es tener diversidad en la población, se deben tener ciertas consideraciones que permitan de vez en cuando mantener a los peores individuos y reemplazar a algunos cuya aptitud no se ni buena ni mala. Todo el proceso descrito hasta ahora se lleva a cabo de manera secuencial e iterativa hasta que se cumple un criterio de parada. Es común que el algoritmo se detenga cuando se llega a un número máximo de iteraciones o bien, cuando se a alcanzado un valor de aptitud deseado en el mejor individuo.

Los algoritmos evolutivos entonces están formados por cuatro operadores básicos, pero existen diferentes modificaciones que permiten adaptarlos a un sinnúmero de problemas reales. Aunque parecen sencillos internamente existen procesos de toma de decisiones que permiten generar métodos más robustos y con mejores capacidades.

Referencias

1. Goldberg DE, Holland JH (1988) Genetic Algorithms and Machine Learning. Mach Learn 3:95–99. https://doi.org/10.1023/A:1022602019183
2. Koza JR (1995) Survey of genetic algorithms and genetic programming. Wescon Conf Rec 589–594. https://doi.org/10.1109/wescon.1995.485447
3. Mitchell M (1995) Genetic algorithms: An overview. Complexity 1:31–39. https://doi.org/10.1002/cplx.6130010108
4. Goldberg DE, Deb K (1991) A Comparative Analysis of Selection Schemes Used in Genetic Algorithms. Found Genet Algorithms 1:69–93. https://doi.org/https://doi.org/10.1016/B978-0-08-050684-5.50008-2
5. Baker JE (1987) Reducing bias and inefficiency in the selection algorithm. Genet algorithms their Appl  Proc Second Int Conf Genet Algorithms  July 28-31, 1987 Massachusetts Inst Technol Cambridge, MA
6. Oliva D, Rodriguez-Esparza E, Martins MSR, et al (2020) Balancing the Influence of Evolutionary Operators for Global optimization. In: 2020 IEEE Congress on Evolutionary Computation, CEC 2020 – Conference Proceedings
7. Das S, Suganthan PN (2011) Differential evolution: A survey of the state-of-the-art. IEEE Trans Evol Comput 15:4–31. https://doi.org/10.1109/TEVC.2010.2059031