Algoritmos genéticos masivamente paralelos

Según Beyer, en el artículo escrito el año 2001 acerca de la “teoría de las estrategias de la evolución”, las estrategias evolutivas son métodos computacionales que trabajan con una población de individuos que pertenecen al dominio de los números reales, que mediante los procesos de mutación y de recombinación evolucionan para alcanzar el óptimo de la función objetivo. Entre los años 1965 y 1973 Rechenberg las introdujo como método para optimizar parámetros reales para ciertos dispositivos. La misma idea fue desarrollada poco después por Schwefel entre los años 1975 a 1977. El campo de las estrategias evolutivas ha permanecido como un área de investigación activa, cuyo desarrollo se produce en su mayor parte, de modo independiente al de los algoritmos genéticos. En palabras de Michalewicz, en el libro escrito el año 1996 acerca de “Programa evolutivo = Algoritmo genético + Estructura de datos”, la programación evolutiva es prácticamente una variación de los algoritmos genéticos, donde lo que cambia es la representación de los individuos. En el caso de la programación evolutiva los individuos son tripletas cuyos valores representan estados de un autómata finito. Cada terna está formada por el valor del estado actual, un símbolo del alfabeto utilizado y el valor del nuevo estado. Fogel, Owens y Walsh fueron los creadores en 1966 de la programación evolutiva, una técnica en la cual los candidatos a soluciones a tareas determinadas son representados por máquinas de estados finitos, cuyos diagramas de estados de transición evolucionaban mediante mutación aleatoria, seleccionándose el que mejor se aproximara a la meta.

La primera mención del término algoritmo genético y la primera publicación sobre una aplicación del mismo, se deben al investigador Bagley en la disertación presentada el año 1967 sobre “el comportamiento de los sistemas adaptativos que emplean algoritmos genéticos y correlacionales.” Bagley diseñó algoritmos genéticos para buscar conjuntos de parámetros en funciones de evaluación de juegos, y los comparó con los algoritmos de correlación, procedimientos de aprendizaje modelados después de los algoritmos de pesos variantes de ese periodo. Sin embargo el que es considerado como el creador de los algoritmos genéticos es el gran investigador John Holland a partir de su libro escrito el año 1975 titulado “Adaptación en sistemas naturales y artificiales”. En contraste con las estrategias evolutivas y la programación evolutiva, el propósito original de Holland no era diseñar algoritmos para resolver problemas concretos, sino estudiar, de un modo formal, el fenómeno de la adaptación tal y como ocurre en la naturaleza, y desarrollar vías para extrapolar esos mecanismos de adaptación natural a los sistemas computacionales. En el libro de Holland se presenta el algoritmo genético como una abstracción de la evolución biológica, y se proporciona el entramado teórico para la adaptación bajo el algoritmo genético. El algoritmo genético de Holland es un método para desplazarse, de una población de cromosomas, representado por bits a una nueva población, utilizando un sistema similar a la selección natural junto con los operadores de apareamiento, mutación e inversión inspirados en la genética. En este primitivo algoritmo, cada cromosoma consta de genes, y cada uno de ellos es una muestra de un alelo particular, cero o uno.

Holland adapta los operadores de selección, apareamiento, mutación e inversión a su algoritmo genético: (1) Selección. Este operador escoge entre los cromosomas de la población aquellos con capacidad de reproducción, y entre estos, los que sean más compatibles, producirán más descendencia que el resto. (2) Apareamiento. Este operador extrae partes de dos cromosomas, imitando la combinación biológica de dos cromosomas aislados. (3) Mutación. Operador que se encarga de cambiar, de modo aleatorio, los valores del alelo en algunas localizaciones del cromosoma. (4) Inversión. Este operador invierte el orden de una sección contigua del cromosoma, recolocando por tanto el orden en el que se almacenan los genes. La mayor innovación de Holland fue la de introducir un algoritmo basado en poblaciones con apareamientos, mutaciones e inversiones. Es más, Holland fue el primero en intentar colocar la computación evolutiva sobre una base teórica firme. Hasta hace poco, esta base teórica, fundamentada en la noción de esquemas, es la estructura sobre la que se edificaron la mayoría de los trabajos teóricos sobre algoritmos genéticos.

Sin embargo según los investigadores Alba y Cotta, en el tutorial escrito el año 2003 sobre “computación evolucionaría”, los algoritmos genéticos secuenciales suelen presentar las siguientes tres desventajas: (1) Para mantener grandes poblaciones de individuos se necesita mucha memoria y puede tornarse ineficiente abordar problemas con estos requerimientos de manera secuencial. (2) Al afrontar problemas complejos, la evaluación de la función de adaptabilidad puede ser muy costosa en tiempo de cómputo y el lapso demandado por una ejecución completa de un algoritmo genético podría ser inaceptable. (3) Los algoritmos genéticos secuenciales pueden converger prematuramente hacia valores subóptimos. Una solución para contrarrestar estos tres problemas consiste en paralelizar la ejecución de los algoritmos genéticos. Un algoritmo genético que utiliza más de un procesador para llevar a cabo su ejecución, es llamado algoritmo genético paralelo. Además de las mejoras en el rendimiento de los sistemas paralelos respecto de sus pares secuenciales, pueden lograrse beneficios adicionales referentes a la calidad de las soluciones.

En la tesis de doctorado del investigador Alba, escrita el año 1999 sobre “Análisis y Diseño de Algoritmos Genéticos Paralelos Distribuidos”, se menciona que antes de realizar la paralelización de un algoritmo, de cualquier tipo, es imprescindible realizar una primera fase de estudio acerca de los elementos del algoritmo que son susceptibles de paralelizarse. En el caso de los algoritmos genéticos resulta evidente que la evaluación de la adecuación de los individuos es una tarea cuya paralelización no afecta al comportamiento del algoritmo. Sin embargo, el operador de selección sí debe ser aplicado de forma global a toda la población si se quiere que el comportamiento del algoritmo siga siendo el mismo que el de la versión secuencial. Esta primera aproximación para la paralelización de los algoritmos genéticos dará lugar a un conjunto de algoritmos que recibirán el nombre de algoritmos maestro-esclavo. La otra gran aproximación a la paralelización de los algoritmos genéticos consiste en dividir la población inicial en subpoblaciones de mayor o menor tamaño que se comuniquen de alguna manera. Este sistema de paralelización es el que más éxito ha obtenido en comparación con su equivalente secuencial. Además de las mejoras de rendimiento debidas a la subdivisión del problema se ha demostrado que el hecho de considerar subpoblaciones que evolucionan independientemente suele, por lo general, ayudar en el proceso de búsqueda. Este tipo de algoritmos se dice que da lugar a especies o nichos de individuos separados. Dentro de esta segunda aproximación se pueden distinguir entre algoritmos de grano grueso y algoritmos de grano fino. La diferencia entre ambos es el tamaño de las poblaciones, que suele ser mayor en los primeros, y la forma en que los individuos interactúan los unos con los otros.

En el artículo de Gordon y Whitley, escrito el año 1993 y relacionado con “algoritmos genéticos paralelos y seriales como optimizadores de funciones”, se propone una clasificación de algoritmo genético paralelo que reconoce tres categorías: (1) Algoritmo genético paralelo de población global, una versión del modelo maestro-esclavo que utiliza selección por torneo y sus versiones elitistas para simplificar el paralelismo. (2) Algoritmo genético paralelo con modelo de islas y migración, similar a los modelos de Gorges-Schleuter, descrito en el articulo “paralelismo explicito de algoritmos genéticos a través de estructuras poblacionales”. (3) Algoritmos genéticos masivamente paralelos o algoritmos genéticos celulares, que asignan un número bajo de individuos por elemento de procesamiento. En este modelo, cada individuo se procesa en paralelo en cada generación y el apareamiento está limitado a un deme, o vecindad, del individuo. Usualmente la topología de conexión y la estructura de los demes es fija, y se corresponde con la topología de conexión de los elemento de procesamiento en la super computadora. La denominación celular se justifica por comportarse el algoritmo genético paralelo como un tipo particular de autómata celular.

Según Michalewicz, en la obra citada párrafos arriba, los algoritmos genéticos masivamente paralelos se caracterizan por asignar, en el caso ideal, un procesador a cada individuo. Es por esto que en general se utiliza en arquitecturas con un gran número de procesadores y alguna topología de interconexión entre ellos, tal como anillo, grilla, hipercubo, etc. Durante la ejecución del algoritmo un individuo puede solamente competir y aparearse con sus vecinos, los cuales se encuentran definidos según la topología de interconexión.