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. El investigador Baluja, en el artículo escrito el año 1992 denominado “algoritmo genético paralelo masivamente distribuido”, modificó los algoritmos genéticos masivamente paralelos, introduciendo poblaciones estructuradas con solapamiento, que permiten la transferencia gradual de información genética sin la introducción súbita de cromosomas. Para el diseño de su modelo de algoritmo genético paralelo masivamente distribuido, Baluja analizó estructuras de las poblaciones y tamaños de las secciones solapadas, indicando que debe lograrse un compromiso entre la lentitud de propagación de soluciones para áreas de solapamiento pequeñas y la desviación de la idea de poblaciones múltiples al crecer las áreas y acercarse a un modelo panmíctico, en el que todos los individuos tienen la misma probabilidad de aparearse y el apareamiento es al azar.
Referencias Bibliográficas
- Alba Enrique (1999) Análisis y Diseño de Algoritmos Genéticos Paralelos Distribuidos. Tesis de Doctorado, Universidad de Málaga.
- Alba, E., Cotta, C. (2003) Tutorial on evolutionary computation. Disponible en http://www.lcc.uma.es/~ccottap/semEC/ec.html [Consulta: Marzo 2006]
- Bagley, J.D. (1967) The behavior of adaptive systems which employ genetic and correlation algorithms. Dissertation Abstracts International. 1967. Vol. 28 No.12.
- Baluja S. (1992) A Massively Distributed Parallel Genetic Algorithm. CMU-CS-92-196R, Carnegie Mellon.
- Beyer, H.G. (2001) The Theory of Evolution Strategies. Natural Computing Series. Springer, Berlin.
- Gordon V. & Whitley D. (1993) Serial and Parallel Genetic Algorithms as Function Optimizers. Proceedings of the Fifth International Conference on Genetic Algorithms, pp. 177-183, 1993.
- Gorges-Schleuter M. (1990) Explicit parallelism of genetic algorithms through population structures. Proceedings of 1st PPSN'90, pp. 150-159.
- Holland, J. (1975) Adaptation in Natural and Artificial Systems. Ann Arbor, MI: The University of Michigan Press. • Michalewicz, Zbigniew (1996) Genetic Algorithms + Data Structures = Evolution Programs. Springer-Verlag, 1996.
No hay comentarios:
Publicar un comentario