Algoritmos Geneticos

ALGORITMOS GENÉTICOS 3

1 Búsqueda, optimización y aprendizaje 3
1.1 Método analítico 7
1.2 Métodos exhaustivos, aleatorios y heurísticos 8
1.3 Hillclimbing, 8
1.4 Recocimiento simulado 9
1.5 Técnicas basadas en población 9
1.6 Técnicas experimentales 9
2 La evolución 10
2.1 Mecanismos de cambio en la evolución 13
• Selección natural: 13
• Derivagénica: 14
• Mutación: 14
• Poliploidía: 14
• Recombinación: 15
• Flujo genético: 15
3 Algoritmo genético simple. 15
3.1 Introducción 16
3.2 Anatomía de un algoritmo genético simple 17
3.3 Codificación de las variables 19
EJEMPLO 1: 19
Ejemplo2: 19
3.4 Algoritmo genético propiamente dicho 21
Tamaño de la población: 21
Condición determinación: 22
3.5 Evaluación y selección 22
Basado en el rango: 23
Rueda de ruleta: 24
Selección de torneo: 24
3.6 Crossover 24
Crossover n-puntos: 25
Crossover uniforme: 26
Crossover especializados: 26
3.7 Mutación 27
3.8 Otros operadores 27
3.8.1 Cromosomas de longitud variable 28
3.8.2 Operadores de nicho (ecológico) 28
3.8.3Operadores especializados 29
Zap: 29
Creep: 29
Transposición: 30
3.8.4 Aplicando operadores genéticos 30
EJEMPLO SIMPLE DE ALGORITMOS GENÉTICO: 31
ejemplo completo de un algoritmo genético 34
1.- Inicialización: 35
2.- Evaluación: 37
3.- Selección: 37
4.- Reproducción: 38
5.- Entrenamiento: 39
CONCLUSIÓN DEL TRABAJO: 41
Aplicaciones de búsqueday optimización : 41
Aprendizaje automático: 42
DiRECCIONES DE CONSULTA: 42

ALGORITMOS GENÉTICOS

1 Búsqueda, optimización y aprendizaje

EN REALIDAD, LOS ALGORITMOS DE BÚSQUEDA ABARCAN PRÁCTICAMENTE TODO ALGORITMO PARA RESOLVER PROBLEMAS AUTOMÁTICAMENTE. HABITUALMENTE, EN INFORMÁTICA SE HABLA DE BÚSQUEDA CUANDO HAY QUE HALLAR INFORMACIÓN, SIGUIENDO UN DETERMINADO CRITERIO,DENTRO DE UN CONJUNTO DE DATOS ALMACENADOS; SIN EMBARGO, AQUÍ NOS REFERIREMOS A OTRO TIPO DE ALGORITMOS DE BÚSQUEDA, A SABER, AQUELLOS QUE, DADO EL ESPACIO DE TODAS LAS POSIBLES SOLUCIONES A UN PROBLEMA, Y PARTIENDO DE UNA SOLUCIÓN INICIAL, SON CAPACES DE ENCONTRAR LA SOLUCIÓN MEJOR O LA ÚNICA. EL EJEMPLO CLÁSICO DE ESTE TIPO DE PROBLEMAS SE ENCUENTRA EN LOS ROMPECABEZAS Y JUEGOS QUE SE SUELENABORDAR EN INTELIGENCIA ARTIFICIAL. UN EJEMPLO ES EL PROBLEMA DE LAS 8 REINAS, EN EL CUAL SE DEBEN DE COLOCAR 8 REINAS EN UN TABLERO DE AJEDREZ DE FORMA QUE NINGUNA AMENACE A OTRA; O LAS TORRES DE HANOI, EN EL QUE, DADA UNA SERIE DE DISCOS DE RADIO DECRECIENTE APILADOS, HAY QUE APILARLOS EN OTRO SITIO TENIENDO EN CUENTA QUE NO SE PUEDE COLOCAR NINGÚN DISCO ENCIMA DE OTRO DE RADIO INFERIOR.Este tipo de problemas es fácil de abordar usando algoritmos "clásicos", como por ejemplo algoritmos recursivos o de tipo voraz (greedy), sin embargo, hay otro tipo de problemas mucho más complicados, sobre todo los NP-completos (aquellos cuya complejidad crece con el tamaño del problema de forma exponencial) que no pueden ser abordados de esta forma. Algunos ejemplos de estos problemas serían lossiguientes:

8-puzzle, en el cual, como se muestra en la ilustración 1, a partir de una configuración inicial donde hay 8 cuadros desordenados, hay que llegar a otra configuración donde estén ordenados, usando para el intercambio cualquier posición que se halle vacía. El problema de búsqueda en este caso consiste en encontrar un camino que vaya desde la configuración inicialhasta la final.

Problema del viajante, en el cual, dadas una serie de ciudades separadas por distancias diferentes, hay que calcular un camino tal que la distancia total recorrida sea mínima, y no que no repita ninguna ciudad. Este problema es NP-completo, y es paradigmático de este tipo de problemas.

Mastermind: En este juego, que se muestra en la figura 2,...