Algoritmos geneticos

ALGORITMOS GENETICOS
NATYHELEM GIL LONDOÑO 27 de Noviembre de 2006

Universidad Nacional de Colombia
Escuela de Estadística Sede Medellín 2006

ÍNDICE

2

Índice
1. GENERALIDADES 1.1. INTRODUCCIÓN . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.1. Reseña Historica . . . . . . . . . . . . . . . . . . . . . . 1.1.2. ¿Que son los Algoritmos Genéticos? . . . . . . . . . . . .1.1.3. ¿Por qué utilizar Algoritmos Genéticos en la Optimización? 1.1.4. Ventajas . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 5 5 6 7 8

1.1.5. Desventajas . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.1.6. ¿Cómo Saber si es Posible usar un Algoritmo Genético? . 17 1.1.7. Algunas Aplicaciones de los Algoritmos Genéticos . . . . 18 2. ALGORITMOS GENÉTICOS 20

2.1. ALGORITMOSGENÉTICOS SIMPLES . . . . . . . . . . . . . 20 2.1.1. Tipos de Representación . . . . . . . . . . . . . . . . . . 20 2.1.2. Tamaño de la Población . . . . . . . . . . . . . . . . . . 22 2.1.3. Población Inicial . . . . . . . . . . . . . . . . . . . . . . 22 2.1.4. Función Objetivo . . . . . . . . . . . . . . . . . . . . . . 22 2.1.5. Operador de Selección . . . . . . . . . . . . . . . . . . . 252.1.6. Operador de Cruce . . . . . . . . . . . . . . . . . . . . . 26 2.1.7. Operador de Mutación . . . . . . . . . . . . . . . . . . . 27 2.1.8. Reemplazo de la Población y Condición de Parada . . . . 28 2.1.9. Otros Operadores . . . . . . . . . . . . . . . . . . . . . . 30 2.1.10. Aplicando Operadores Genéticos . . . . . . . . . . . . . 32 2.2. ALGORITMOS GENÉTICOS PARALELOS . . . . . . . . . . . 372.3. COMPARACIÓN DE LOS ALGORITMOS GENÉTICOS CON OTRAS TÉCNICAS DE OPTIMIZACIÓN . . . . . . . . . . . . 40

ÍNDICE 3. ALGORITMOS GENÉTICOS: CÓDIGO EN R

3 43

3.1. PROGRAMA EN R: ALGORITMOS GENÈTICOS . . . . . . . 43 3.2. ALGORITMO GENÉTICO DE BÚSQUEDA ÓPTIMA: UN SUBCONJUNTO DE K-VARIABLES . . . . . . . . . . . . . . . . . 49 3.2.1. Descripción . . . . . . . . . . . . . . . . . . . . . . .. . 49 3.2.2. Uso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.2.3. Argumentos . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.2.4. Detalles . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.2.5. Ejemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.3. FUNCIÓN PLOT . . . . . . . . . . . . . . . . . . . . . . . . . . 52 3.3.1. Descripción . . . . . . .. . . . . . . . . . . . . . . . . . 52 3.3.2. Uso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 3.3.3. Argumentos . . . . . . . . . . . . . . . . . . . . . . . . . 52 3.3.4. Ejemplos . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.4. CROMOSOMA FLOTANTE . . . . . . . . . . . . . . . . . . . . 53 3.4.1. Descripción . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.4.2.Uso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.4.3. Argumentos . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.4.4. Ejemplos . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.5. CROMOSOMA BINARIO . . . . . . . . . . . . . . . . . . . . . 55 3.5.1. Descripción . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.5.2. Uso . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 55 3.5.3. Argumentos . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.5.4. Ejemplos . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.6. FUNCIÓN SUMMARY . . . . . . . . . . . . . . . . . . . . . . 59 3.6.1. Descripción . . . . . . . . . . . . . . . . . . . . . . . . . 59 3.6.2. Uso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

ÍNDICE

4 3.6.3.Argumentos . . . . . . . . . . . . . . . . . . . . . . . . . 59 3.6.4. Ejemplos . . . . . . . . . . . . . . . . . . . . . . . . . . 59

4. APLICACIÓN 5. CONCLUSIONES

60 64

1

GENERALIDADES

5

1.
1.1.
1.1.1.

GENERALIDADES
INTRODUCCIÓN
Reseña Historica

Los algoritmos genéticos (AG), fueron inventados en 1975 por John Holland, de la Universidad de Michigan. Los AG son,...