Método Científico

Anuncios

Funcionamiento de un algoritmo genético básico

Un algoritmo genético puede presentar diversas variaciones, dependiendo de cómo se aplican los operadores genéticos (cruzamiento, mutación), de cómo se realiza la selección y de cómo se decide el reemplazo de los individuos para formar la nueva población. En general, el pseudocódigo consiste de los siguientes pasos:

Algoritmo genético i: inicialización, f(X): evaluación: condición de término, Se: selección, Cr: cruzamiento, Mu: mutación, Re: reemplazo, X*: mejor solución.

  • Inicialización: Se genera aleatoriamente la población inicial, que está constituida por un conjunto de cromosomas los cuales representan las posibles soluciones del problema. En caso de no hacerlo aleatoriamente, es importante garantizar que dentro de la población inicial, se tenga la diversidad estructural de estas soluciones para tener una representación de la mayor parte de la población posible o al menos evitar la convergencia prematura.
  • Evaluación: A cada uno de los cromosomas de esta población se aplicará la función de aptitud para saber cómo de “buena” es la solución que se está codificando.
  • Condición de término El AG se deberá detener cuando se alcance la solución óptima, pero ésta generalmente se desconoce, por lo que se deben utilizar otros criterios de detención. Normalmente se usan dos criterios: correr el AG un número máximo de iteraciones (generaciones) o detenerlo cuando no haya cambios en la población. Mientras no se cumpla la condición de término se hace lo siguiente:
    • Selección Después de saber la aptitud de cada cromosoma se procede a elegir los cromosomas que serán cruzados en la siguiente generación. Los cromosomas con mejor aptitud tienen mayor probabilidad de ser seleccionados.
    • Cruzamiento El cruzamiento es el principal operador genético, representa la reproducción sexual, opera sobre dos cromosomas a la vez para generar dos descendientes donde se combinan las características de ambos cromosomas padres.
    • Mutación modifica al azar parte del cromosoma de los individuos, y permite alcanzar zonas del espacio de búsqueda que no estaban cubiertas por los individuos de la población actual.
    • Reemplazo una vez aplicados los operadores genéticos, se seleccionan los mejores individuos para conformar la población de la generación siguiente

Historia del Algoritmo Genético

La historia de la evolución de los seres vivos ha sido primordial para que se de grandes saltos en la historia que implica el proceso de cambio en el tiempo.

La evolución biológica es el proceso continuo de transformación de las especies a través de cambios producidos en sucesivas generaciones. El naturalista Charles Darwin definió en su libro “Sobre el Origen de las Especies por medio de la Selección Natural” la Selección Natural o Supervivencia del más Adaptado como el proceso del resguardo de las variaciones y diferencias benévolas en cada individuo, así como la destrucción de aquellas variaciones dañinas. Dentro de la naturaleza, los individuos deberán de adaptarse a su entorno para poder sobrevivir mediante el proceso que llamamos evolución, en el cual aquellas características o cambios que favorecen su competitividad son preservados, y aquellas características que disminuyen su adaptación son excluidos.

La teoría de la evolución defendida por Charles Darwin se sustenta en cuatro argumentos: La naturaleza está en constante evolución. El proceso de cambio es gradual y continuo. Los organismos que presentan semejanzas están emparentados. El cambio evolutivo es el resultado del proceso de selección natural. Gregor Mendel descubrió que los caracteres se heredaban de forma discreta, y que se tomaban del padre o de la madre, dependiendo de su carácter dominante o recesivo.

Estos caracteres, favorables o desfavorables, se almacenan y controlan desde unas unidades llamadas genes y a los valores que podían tomar, alelos, y gracias al estudio de James Watson y Francis Crick que descubrieron que la base molecular de los genes se encuentra en el ácido desoxiribonucleico. Los cromosomas están compuestos por acido desoxiribonucleico y por tanto los genes están en los cromosomas.

Los primeros hechos relacionados con los algoritmos genéticos surgieron en 1932 cuando Cannon interpreta la evolución natural como un proceso de aprendizaje muy similar al proceso mediante el cual una persona aprende por ensayo y error.

También en 1950 Turing reconoce una conexión entre la evolución y el aprendizaje de una maquina, pero los primeros intentos serios de relacionar la informática y la evolución surgieron a principios de los años sesenta cuando varios biólogos comenzaron a experimentar con simulaciones de sistemas genéticos; esto es, modelos computacionales que imitan la evolución biológica.

La apertura en el desarrollo de los algoritmos genéticos se da gracias al trabajo un investigador matemático de la Universidad de Michigan que lleva el nombre de John Holland, quien estaba convencido de que era la recombinación de grupos de genes, que se realiza mediante el apareamiento, la parte más importante de la evolución.

A mediados de los años 60 desarrolla el Algoritmo Genético, que se adapta a la evolución tanto por el apareamiento como por la mutación, en décadas posteriores sienta bases teóricas que fundamentan el desarrollo de los algoritmos genéticos desde un perspectiva computacional en donde abstrae conceptos de l genética natural y los aplica ala economía y al reconocimiento de patrones, esta base teórica fue publicada en su monografía llamada “Adaptación en Sistemas Naturales y Artificiales”en 1975.

Unos 15 años más adelante, David Goldberg, fue uno de los primeros que aplicó los algoritmos genéticos a problemas industriales y sucesivamente se realizaron nuevas aplicaciones de estos algoritmos genéticos que utilizaron diferentes temas como.

Charles Darwin y su libro: El Origen de las especies (Frase)

…”Como de cada especie nacen muchos más individuos de los que pueden sobrevivir, y como, en consecuencia, hay una lucha por la vida, que se repite frecuentemente, se sigue que todo ser, si varía, por débilmente que sea, de algún modo provechoso para él bajo las complejas y a veces variables condiciones de la vida, tendrá mayor probabilidad de sobrevivir y, de ser así, será naturalmente seleccionado. Según el poderoso principio de la herencia, toda variedad seleccionada tenderá a propagar su nueva y modificada forma”…

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

Fuentes