Algoritmos genéticos

INTELIGENCIA ARTIFICIAL II
ALGORITMOS
GENÉTICOS
2006-2007
Adrián Juan Verdejo
2
INDICE
1. Introducción ………………………………………………………………………5
2. Definición de algoritmo genético………………………………………...……8
3. Transformación de conceptos de evolución biológica a algoritmos ge-néticos
3.1 Acercamiento teórico a los conceptos biológicos básicos……………..…....... 11
3.2 Extrapolación de los conceptosbiológicos a los AG………………….............. 12
4. Operadores Genéticos más usuales……………………………………...… 13
4.1 Mutación ………………….....……….....……….....……….....……….....……............ 13
4.2 Reproducción ………………….....……….....……….....………........……….............. 14
4.3 Crossover …………………...……….....……….....……….....……….....……............ 15
5. Algoritmo Genético Simple………………………………………………...… 16
5.1Pseudocódigo……………........……….....……….....……….....……….....………....... 16
5.2 Codificación del problema……………..............……….....……….....………........... 16
5.3 Ejemplo…………….……….....……….....……….....……….....……….....…............... 18
6. Algoritmo Genético Paralelo ……………...……………………………...… 20
6.1 Modelos de Islas……………....……….....……….....……….....……….................... 21
6.1.1 Algoritmos maestro-esclavo
6.1.2 Algoritmos degrano fino
6.1.3 Algoritmos de grano grueso
6.1.4 Algoritmos híbridos
6.2 Influencia de las migraciones en un algoritmo paralelo………………............ 25
6.3 Influencia de la topología de comunicación en un algoritmo paralelo........... 26
7. Aplicaciones de los algoritmos genéticos ………………………….....… 27
8. Aplicación Informática basada en algoritmos genéticos…….….....… 28
9. Bibliografía…….….....……….….....……….….....……….…...…….….....… 31
3
4
1. Introducción
El algoritmo genético es una técnica de búsqueda basada en la teoría de la evolución de Darwin, que ha cobrado tremenda popularidad alrededor del mundo durante los últimos años.
Fue en las décadas de 1950 y 1960 cuando varios científicos, de modo indepen-diente, comenzaron a estudiar los sistemas evolutivos, guiados por la intuición de quese podrían emplear como herramienta en problemas de optimización en ingeniería. La idea era evolucionar una población de candidatos a ser solución de un problema conocido, utilizando operadores inspirados en la selección natural y la variación genética natural.
Con esta idea nace en el año 1993 la computación evolutiva, que retoma con-ceptos de la evolución y la genética para resolverprincipalmente problemas de optimi-zación. Esta rama de la inteligencia artificial tiene sus raíces en tres desarrollos relacio-nados pero independientes entre sí:
- Algoritmos genéticos
- Programación evolutiva
- Estrategias Evolutivas
De estas tres áreas parten los caminos hacia todos los campos de investigación inspirados en nuestros conocimientos sobre Evolución.
Las estrategias evolutivas sonmé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 1965 y 1973 Rechenberg las introdujo como método para opti-mizar parámetros reales para ciertos dispositivos. La misma idea fue desarrollada poco después (75-77)por Schwefel. 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 (aunque recientemente se ha visto como las dos comunidades han comenzado ha colaborar).
La programación evolutiva (PE) es prácticamente una variación de los algorit-mos genéticos, donde lo quecambia es la representación de los individuos. En el caso de la PE los individuos son ternas (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.
Estos valores se utilizan como en un autómata finito, teniendo el valor del estado actual en el...