ALGORITMOS EVOLUTIVOS

PRÓLOGO
AES: TÉCNICAS DE BÚSQUEDA Y OPTIMIZACIÓN
1.1 LA TEORÍA DE LA EVOLUCIÓN
1.2 ESQUEMA GENERAL DE UN ALGORITMO EVOLUTIVO
1.3 BÚSQUEDA Y OPTIMIZACIÓN
ALGORITMOS GENÉTICOS
2.1 PRINCIPALES ELEMENTOS DE UN AG
2.2 REPRESENTACIÓN DE LOS INDIVIDUOS
2.3 GENERACIÓN DE LA POBLACIÓN INICIAL
2.4 GRADO DE ADAPTACIÓN DE LOS INDIVIDUOS
2.5 CONDICIONES DE TERMINACIÓN
2.6 EL PROCESO DE SELECCIÓN: MECANISMOS DE MUESTREO
2.7 EL PROCESO DE REPRODUCCIÓN: OPERADORES GENÉTICOS
2.7.1 Operador de Cruce Monopunto
2.7.2 Operador de Mutación Aleatoria bit a bit
2.8 EL PROCESO DE REEMPLAZO
2.9 IMPLEMENTACIÓN DEL ALGORITMO GENÉTICO SIMPLE
2.9.1 Estructuras de Datos
2.9.2 Generación de la Población Inicial
2.9.3 Adaptación de los Individuos
2.9.4 Evaluación de la Población
2.9.5 Selección de Supervivientes
2.9.6 Reproducción, Cruce y Mutación
2.10 EJEMPLO DE APLICACIÓN A LA BÚSQUEDA DEL ÓPTIMO DE UNA FUNCIÓN
2.11 PROPIEDADES TEÓRICAS DE LOS ALGORITMOS GENÉTICOS
2.11.1 Esquemas
2.11.2 El Teorema Fundamental
2.11.3 Paralelismo Implícito
ALTERNATIVAS A LOS COMPONENTES DE UN ALGORITMO EVOLUTIVO 57
3.1 DE LA FUNCIÓN OBJETIVO A LA FUNCIÓN DE ADAPTACIÓN
3.1.1 Haciendo Positiva la Función de Adaptación
3.1.2 Escalado de la Función de Adaptación
3.2 ELITISMO
3.3 CRITERIOS DE TERMINACIÓN
3.4 VARIANTES DE LOS OPERADORES GENÉTICOS
3.4.1 Cruce Multipunto
3.4.2 Cruce Segmentado
3.4.3 Cruce Uniforme
3.4.4 Cruce Adaptativo
3.4.5 Tasa de Mutación Variable
3.4.6 Mutación Adaptativa
3.5 TRATAMIENTO DE PROBLEMAS CON RESTRICCIONES
3.5.1 Técnicas básicas
3.5.2 Algunos problemas de restricciones tratados con AEs
3.5.2.1 Técnicas de penalización
3.5.2.2 Técnicas de reparación
3.5.2.3 Técnicas de codificación
3.5.2.4 Comparativa
3.5.2.5 El problema de las N reinas
3.5.2.6 Empaquetado en Contenedores
3.5.2.7 Coloreado de grafos
OTROS TIPOS DE ALGORITMOS EVOLUTIVOS
4.1 ALGORITMOS EVOLUTIVOS EN OPTIMIZACIÓN COMBINATORIA
4.1.1 El problema del viajante de comercio
4.1.1.1 Representación de los individuos
4.1.1.2 Operadores de cruce
4.1.1.3 Operadores de mutación
4.2 ALGORITMOS EVOLUTIVOS PARA NÚMEROS REALES
4.2.1 Operadores de cruce
4.2.1.1 Cruce discreto simple
4.2.1.2 Cruce discreto de dos puntos
4.2.1.3 Cruce discreto uniforme
4.2.1.4 Cruce aritmético
4.2.1.5 Cruce media geométrica
4.2.1.6 Cruce SBX
4.2.1.7 Cruce BLX-a
4.2.2 Operadores de mutación
4.2.2.1 Mutación uniforme
4.2.2.2 Mutación No Uniforme
4.3 PROGRAMACIÓN GENÉTICA
4.3.1 Creación de los individuos
4.3.2 Operadores de cruce
4.3.3 Operadores de mutación
EXTENSIONES DE LOS ALGORITMOS GENÉTICOS
5.1 ALGORITMOS EVOLUTIVOS MULTIOBJETIVO
5.1.1 Funciones agregativas
5.1.2 Aproximaciones que utilizan el concepto de dominancia
5.1.3 Ejemplos de aplicación
5.2 ALGORITMOS EVOLUTIVOS PARALELOS
5.2.1 Modelos centralizados o en granja
5.2.2 Modelos de islas o distribuidos
5.2.3 Modelos de grano fino o celulares
5.2.4 Modelos híbridos
5.3 ALGORITMOS MEMÉTICOS
5.4 NUEVAS TENDENCIAS
5.4.1 Inteligencia colectiva y Algoritmos de Colonias de Hormigas
5.4.2 Evolución diferencial
5.4.3 Algoritmos de Estimación de Distribuciones
5.4.4 Evolución gramatical
OPTIMIZACIÓN DE FUNCIONES (A)
1. MAXIMIZACION DE FUNCIONES
2. MINIMIZACIÓN DE FUNCIONES
3. OPTIMIZACIÓN DE FUNCIONES DE VARIAS VARIABLES
OPTIMIZACIÓN DE FUNCIONES (B)
BÚSQUEDA DE RUTAS DE METRO
1. DESCRIPCIÓN DEL PROBLEMA
2. DISEÑO DEL ALGORITMO
2.1 Representación de los individuos
2.2 Generación de la población inicial
2.3 Función de adaptación
2.4 Operador de cruce
2.5 Operador de mutación
2.6 Consideraciones adicionales
3. TRATAMIENTO ALTERNATIVO DE LAS RESTRICCIONES
4. CON OTRAS RESTRICCIONES
5. UN EJEMPLO DE INTERFAZ GRÁFICA
PLANIFICACIÓN DE HORARIOS
1. DESCRIPCIÓN DEL PROBLEMA
2. DISEÑO DEL ALGORITMO
2.1 Representación de los individuos
2.2 Generación de la población inicial
2.3 Función de adaptación
2.4 Operador de cruce
2.5 Operador de mutación
2.6 Consideraciones adicionales
3. TRATAMIENTO ALTERNATIVO DE LAS RESTRICCIONES
4. CON OTRAS RESTRICCIONES
CORTADO DE PATRONES
1. DESCRIPCIÓN DEL PROBLEMA
2. DISEÑO DEL ALGORITMO
2.1 Representación de los datos de entrada
2.2 Representación de los individuos
2.3 Generación de la población inicial
2.4 Función de adaptación
2.5 Operador de cruce
2.6 Operador de mutación
2.7 Parámetros del algoritmo
3. VARIANTES DEL DISEÑO DEL ALGORITMO
3.1 Diseño e implementación
CONTROL DE TRÁFICO AÉREO
1. DESCRIPCIÓN DEL PROBLEMA
2. DISEÑO DEL ALGORITMO
2.1 Representación de los individuos
2.2 Generación de la población inicial
2.3 Función de adaptación
2.4 Operador de cruce
2

Los algoritmos evolutivos constituyen una técnica general de resolución de problemas de búsqueda y optimización inspirada en la teoría de la evolución de las especies y la selección natural. Estos algoritmos permiten abordar problemas complejos que surgen en las ingenierías y los campos científicos: problemas de planificación de tareas, horarios, tráfico aéreo y ferroviario, búsqueda de caminos óptimos, optimización de funciones, etc. Con este libro hemos querido aportar un enfoque práctico al estudio de los algoritmos evolutivos, que es fundamental para aplicarlos a problemas reales de cualquier disciplina del conocimiento. El libro tiene dos partes: la primera, en la que se describen los algoritmos; y la segunda en la que se proponen numerosos proyectos y se resuelven empleando estas técnicas.

Los algoritmos evolutivos presentan una estructura general que puede aplicarse a los distintos problemas, facilitando así enormemente las tareas de diseño e implementación. El único requisito de un usuario que desee aplicar esta técnica para resolver un problema concreto es saber programar en cualquier lenguaje de propósito general en el que codificaría el algoritmo evolutivo. Sin embargo, para obtener buenos resultados con estos algoritmos es necesario conocerlos con detalle, ya que dentro del esquema general de un algoritmo evolutivo hay que elegir múltiples componentes y parámetros, de los que va a depender la calidad del resultado y la eficiencia del algoritmo. El conocimiento de la elección más adecuada en cada caso, que a menudo depende de detalles sutiles del problema considerado, sólo se consigue con la práctica. Esta idea nos ha llevado a proponer este libro, que consideramos adecuado para cualquier ingeniero o licenciado con conocimientos básicos de programación.