Algoritmo genetico

Algoritmos Genéticos
Departamento de Ciencias de la Computación e Inteligencia Artificial Universidad del País Vasco
Euskal Herriko Unibertsitatea
http://www.geocities.com/CapeCanaveral/9802/3d5ca000.htm

ABSTRACT
El objetivo de este trabajo es introducir un tipo de algoritmos evolutivos denominados algoritmos genéticos. Dichos algoritmos usan una analogía directa con elcomportamiento natural y pueden ser considerados como métodos adaptivos, siendo usados para resolver problemas de búsqueda y optimización. A lo largo del trabajo se introducirá el denominado algoritmo genético simple, revisándose algunas de las extensiones y modificaciones que sobre el mismo se han ido introduciendo en la literatura. Se tratará también la relación existente entre los algoritmos genéticos yotros heurísticos de optimización.

ÍNDICE
1. Introducción
2. El Algoritmo Genético Simple
1. Codificación
2. Ejemplo
3. Extensiones y Modificaciones del Algoritmo Genético Simple
1. Población
1. Tamaño de la población
2. Población inicial
2. Función objetivo
3. Selección
4. Cruce
5. Mutación6. Reducción
7. Algoritmos Genéticos Paralelos
4. Evaluación del Comportamiento de los Algoritmos Genéticos
5. ¿Por qué funcionan?
1. Teorema de los esquemas
2. Paralelismo implícito
3. Teoremas de convergencia
6. Relación con otras técnicas de optimización
1. Intoducción
2. Estatregias Evolutivas
3. ProgramaciónEvolutiva
4. Programación Genética
5. Simulated Annealing
7. Referencias (Bibliografía)

1 Introducción

Los Algoritmos Genéticos (AG’s) son métodos adaptivos que pueden usarse para resolver problemas de búsqueda y optimización. Están basados en el proceso genético de los organismos vivos. A lo largo de las generaciones, las poblaciones evolucionan en la naturalezaacorde con los principios de la selección natural y la supervivencia de los más fuertes, postulados por Darwin [9]. Por imitación de este proceso, los Algoritmos Genéticos son capaces de ir creando soluciones para problemas del mundo real. La evolución de dichas soluciones hacia valores óptimos del problema depende en buena medida de una adecuada codificación de las mismas.
Los principiosbásicos de los Algoritmos Genéticos fueron establecidos por Holland [22], y se encuentran bien descriptos en varios textos – Goldberg [19], Davis [11], Michalewicz [29], Reeves [32].
En la naturaleza los individuos de una población compiten entre sí en la búsqueda de recursos tales como comida, agua y refugio. Incluso los miembros de una misma especie compiten a menudo en la búsqueda de unapareja. Aquellos individuos que tienen más éxito en sobrevivir y en atraer compañeros tienen mayor probabilidad de generar un gran número de descendientes. Por el contrario individuos poco dotados producirán un menor número de descendientes. Esto significa que los genes de los individuos mejor adaptados se propagarán en sucesivas generaciones hacia un número de individuos creciente. La combinación debuenas características provenientes de diferentes ancestros, puede a veces producir descendientes particularmente interesantes (superindividuos), ya que se encuentran muy bien dotados, con una gran adaptación, típicamente mucho mayor que la de cualquiera de sus ancestros. De esta manera, las especies evolucionan logrando características cada vez mejor adaptadas al entorno en el que viven.Los Algoritmos Genéticos usan una analogía directa con el comportamiento natural. Trabajan con una población de individuos, cada uno de los cuales representa una solución factible a un problema dado. A cada individuo se le asigna un valor ó puntuación, relacionado con la bondad de dicha solución. En la naturaleza esto equivaldría al grado de efectividad de un organismo para competir por unos...