Fundamentos de la computación evolutiva

Descripción: I Algoritmos evolutivos 1 1 Introducción a la computación evolutiva 3 1.1 Inspiración en la biología . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.1 Teoría de la evolución . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.2 Del ADN a las proteínas . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1.3 Reproducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.1.4 Mutación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Historia de la computación evolutiva . . . . . . . . . . . . . . . . . . . . . 9 1.3 Algoritmo evolutivo canónico . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.3.1 Representación de individuos . . . . . . . . . . . . . . . . . . . . . 12 1.3.2 Función de adaptación . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.3.3 Población . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.3.4 Inicialización de la población . . . . . . . . . . . . . . . . . . . . . 14 1.3.5 Selección de padres . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.3.6 Operadores de variación . . . . . . . . . . . . . . . . . . . . . . . . 14 1.3.7 Selección de supervivientes . . . . . . . . . . . . . . . . . . . . . . 15 1.3.8 Condición de terminación . . . . . . . . . . . . . . . . . . . . . . . 15 1.4 Algoritmos evolutivos como métodos de búsqueda . . . . . . . . . . . . . . 16 1.5 Campos de aplicación de la computación evolutiva . . . . . . . . . . . . . 17 1.5.1 Aplicaciones en clasi_cación . . . . . . . . . . . . . . . . . . . . . . 18 1.5.2 Aplicaciones en control . . . . . . . . . . . . . . . . . . . . . . . . 18 1.5.3 Aplicaciones en diseño . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.5.4 Aplicaciones en plani_cación . . . . . . . . . . . . . . . . . . . . . 19 1.5.5 Aplicaciones en simulación . . . . . . . . . . . . . . . . . . . . . . 19 2 Algoritmos genéticos 21 2.1 Ejemplo introductorio: el problema del viajante . . . . . . . . . . . . . . . 21 2.2 Representación de individuos . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.2.1 Representación binaria . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.2.2 Representación entera . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.2.3 Representación real . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.2.4 Representación mediante permutaciones . . . . . . . . . . . . . . . 29 2.3 Inicialización de la población . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.4 Selección de padres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.4.1 Selección proporcional al valor de adaptación . . . . . . . . . . . . 32 2.4.2 Selección por ordenación . . . . . . . . . . . . . . . . . . . . . . . . 33 2.4.3 Selección por torneo . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.4.4 Muestreo de distribuciones de probabilidad . . . . . . . . . . . . . 35 2.5 Recombinación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.5.1 Operadores de recombinación para representación binaria . . . . . 37 2.5.1.1 Cruce por un punto . . . . . . . . . . . . . . . . . . . . . 38 2.5.1.2 Cruce por n puntos . . . . . . . . . . . . . . . . . . . . . 38 2.5.1.3 Cruce uniforme . . . . . . . . . . . . . . . . . . . . . . . . 38 2.5.2 Operadores de recombinación para representación entera . . . . . . 38 2.5.3 Operadores de recombinación para representación real . . . . . . . 39 2.5.3.1 Recombinación discreta . . . . . . . . . . . . . . . . . . . 39 2.5.3.2 Recombinación aritmética . . . . . . . . . . . . . . . . . . 39 2.5.4 Operadores de recombinación para representación mediante permutaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.5.4.1 Cruce por orden . . . . . . . . . . . . . . . . . . . . . . . 41 2.5.4.2 Cruce por ciclos . . . . . . . . . . . . . . . . . . . . . . . 41 2.5.4.3 Cruce parcialmente mapeado . . . . . . . . . . . . . . . . 42 2.5.4.4 Cruce por enlaces . . . . . . . . . . . . . . . . . . . . . . 43 2.6 Mutación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.6.1 Operadores de mutación para representación binaria . . . . . . . . 45 2.6.2 Operadores de mutación para representación entera . . . . . . . . 46 2.6.3 Operadores de mutación para representación real . . . . . . . . . . 46 2.6.4 Operadores de mutación para representación mediante permutaciones 46 2.6.4.1 Mutación por intercambio . . . . . . . . . . . . . . . . . . 47 2.6.4.2 Mutación por inserción . . . . . . . . . . . . . . . . . . . 47 2.6.4.3 Mutación por mezcla . . . . . . . . . . . . . . . . . . . . 47 2.6.4.4 Mutación por inversión . . . . . . . . . . . . . . . . . . . 47 2.7 Selección de supervivientes . . . . . . . . . . . . . . . . . . . . . . . . . . 48 2.8 Algoritmos de estimación de distribuciones . . . . . . . . . . . . . . . . . 49 2.9 Ejemplo de aplicación: el problema del viajante . . . . . . . . . . . . . . . 49 3 Estrategias evolutivas 53 3.1 Introducción: algoritmo EE-(1+1) . . . . . . . . . . . . . . . . . . . . . . 53 3.2 Estrategia evolutiva estándar . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.3 Representación de individuos . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.4 Inicialización de la población . . . . . . . . . . . . . . . . . . . . . . . . . 59 3.5 Selección de padres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3.6 Recombinación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3.7 Mutación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 3.7.1 Interpretación geométrica . . . . . . . . . . . . . . . . . . . . . . . 64 3.7.2 Mutación no correlacionada de 1-tamaño de paso . . . . . . . . . . 66 3.7.3 Mutación no correlacionada de n-tamaños de paso . . . . . . . . . 67 3.7.4 Mutación correlacionada . . . . . . . . . . . . . . . . . . . . . . . . 68 3.8 Selección de supervivientes . . . . . . . . . . . . . . . . . . . . . . . . . . 70 3.9 Variantes de estrategias evolutivas . . . . . . . . . . . . . . . . . . . . . . 72 3.9.1 CMA-ES: Estrategia evolutiva basada en la adaptación de la matriz de covarianza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 3.10 Ejemplo de aplicación: problema de resolución de ecuaciones diferenciales 76 4 Programación evolutiva 83 4.1 Ejemplo introductorio: el problema de la hormiga arti_cial . . . . . . . . . 83 4.2 Representación de individuos . . . . . . . . . . . . . . . . . . . . . . . . . 87 4.3 Inicialización, selección de padres y recombinación . . . . . . . . . . . . . 89 4.4 Mutación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 4.5 Selección de supervivientes . . . . . . . . . . . . . . . . . . . . . . . . . . 92 4.6 Ejemplo de aplicación: diseño de redes neuronales arti_ciales . . . . . . . 92 4.6.1 Introducción a las redes neuronales arti_ciales . . . . . . . . . . . . 93 4.6.2 Redes neuronales arti_ciales evolutivas . . . . . . . . . . . . . . . . 94 4.6.2.1 Evolución de los pesos de las conexiones . . . . . . . . . . 94 4.6.2.2 Evolución de la topología . . . . . . . . . . . . . . . . . . 95 4.6.2.3 Evolución conjunta de pesos y topología: EPNet . . . . . 96 5 Evolución diferencial 99 5.1 Ejemplo introductorio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 5.2 Evolución diferencial canónica . . . . . . . . . . . . . . . . . . . . . . . . . 101 5.3 Representación de individuos . . . . . . . . . . . . . . . . . . . . . . . . . 104 5.4 Algoritmo clásico en ED: _DE/rand/1 /bin_ . . . . . . . . . . . . . . . . . 105 5.5 Inicialización de la población . . . . . . . . . . . . . . . . . . . . . . . . . 105 5.6 Selección de padres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 5.7 Operadores de variación . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 5.7.1 Mutación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 5.7.2 Recombinación (discreta o binomial) . . . . . . . . . . . . . . . . . 108 5.8 Selección de supervivientes . . . . . . . . . . . . . . . . . . . . . . . . . . 109 5.9 Otras variantes en evolución diferencial . . . . . . . . . . . . . . . . . . . 109 5.9.1 Formas de seleccionar el vector base . . . . . . . . . . . . . . . . . 110 5.9.2 Incremento del número de diferenciales . . . . . . . . . . . . . . . . 111 5.9.3 Otros tipos de recombinación . . . . . . . . . . . . . . . . . . . . . 112 5.9.4 Otras variantes usadas en entornos complejos . . . . . . . . . . . . 113 5.10 Aspectos prácticos en evolución diferencial . . . . . . . . . . . . . . . . . . 114 5.10.1 Inicialización de la población . . . . . . . . . . . . . . . . . . . . . 114 5.10.2 Restringir la búsqueda al espacio de búsqueda . . . . . . . . . . . . 114 5.10.3 Acerca del valor de F . . . . . . . . . . . . . . . . . . . . . . . . . 115 5.10.4 Acerca del valor de CR . . . . . . . . . . . . . . . . . . . . . . . . 116 5.10.5 Recomendaciones generales . . . . . . . . . . . . . . . . . . . . . . 117 5.11 Aplicaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 5.12 Ejemplo de aplicación: optimización de una función multimodal . . . . . . 118 6 Programación genética 125 6.1 Ejemplo introductorio: regresión simbólica . . . . . . . . . . . . . . . . . . 126 6.2 Algoritmo estándar en programación genética . . . . . . . . . . . . . . . . 130 6.3 Representación de individuos . . . . . . . . . . . . . . . . . . . . . . . . . 131 6.4 Inicialización de la población . . . . . . . . . . . . . . . . . . . . . . . . . 134 6.4.1 Método de crecimiento uniforme . . . . . . . . . . . . . . . . . . . 135 6.4.2 Método de crecimiento no uniforme . . . . . . . . . . . . . . . . . 135 6.4.3 Método de crecimiento mixto . . . . . . . . . . . . . . . . . . . . . 135 6.5 Selección de padres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 6.6 Operadores de variación . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 6.6.1 Reproducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 6.6.2 Recombinación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 6.6.3 Mutación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 6.6.4 Mutación vs. recombinación . . . . . . . . . . . . . . . . . . . . . . 139 6.7 Selección de supervivientes . . . . . . . . . . . . . . . . . . . . . . . . . . 140 6.8 Funciones de_nidas automáticamente . . . . . . . . . . . . . . . . . . . . . 140 6.9 El efecto engorde . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 6.10 Variantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 6.10.1 Evolución gramatical . . . . . . . . . . . . . . . . . . . . . . . . . . 143 6.10.2 Programación de expresiones de genes . . . . . . . . . . . . . . . . 146 6.11 Ejemplo de aplicación: diseño de circuitos electrónicos analógicos . . . . . 149 6.11.1 De_nición del problema . . . . . . . . . . . . . . . . . . . . . . . . 149 6.11.2 Diseño de circuitos analógicos basado en EG . . . . . . . . . . . . 149 7 Sistemas clasi_cadores evolutivos 157 7.1 Ejemplo introductorio: el multiplexor . . . . . . . . . . . . . . . . . . . . . 158 7.2 Sistema clasi_cador evolutivo genérico . . . . . . . . . . . . . . . . . . . . 160 7.3 Sistema clasi_cador evolutivo basado en fuerza: ZCS . . . . . . . . . . . . 162 7.4 Sistema clasi_cador evolutivo basado en exactitud: XCS . . . . . . . . . . 164 7.5 Enfoque tipo Pittsburgh . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 7.6 Representaciones alternativas de reglas . . . . . . . . . . . . . . . . . . . . 167 7.6.1 Representación basada en intervalos . . . . . . . . . . . . . . . . . 167 7.6.2 Representación basada en hiperelipsoides . . . . . . . . . . . . . . 167 7.6.3 Representación basada en envolturas convexas . . . . . . . . . . . 168 7.6.4 Representación basada en redes neuronales . . . . . . . . . . . . . 169 7.6.5 Representación desordenada . . . . . . . . . . . . . . . . . . . . . . 169 7.6.6 Representación basada en expresiones S . . . . . . . . . . . . . . . 170 7.6.7 Representación basada en expresiones de genes . . . . . . . . . . . 170 7.6.8 Representación basada en lógica difusa . . . . . . . . . . . . . . . . 171 7.7 Ejemplo de aplicación: diagnóstico de cáncer . . . . . . . . . . . . . . . . 172 8 Algoritmos meméticos 175 8.1 Introducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176 8.2 Características de un algoritmo memético . . . . . . . . . . . . . . . . . . 177 8.2.1 Heurísticas y metaheurísticas . . . . . . . . . . . . . . . . . . . . . 178 8.2.2 Algoritmo memético canónico . . . . . . . . . . . . . . . . . . . . . 178 8.3 Búsqueda local . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 8.3.1 Espacios de búsqueda combinatorios . . . . . . . . . . . . . . . . . 182 8.3.2 Espacios de búsqueda continuos . . . . . . . . . . . . . . . . . . . . 184 8.4 Algoritmos meméticos basados en la hibridación de un algoritmo evolutivo 188 8.4.1 Representación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 8.4.2 Inicialización de la población . . . . . . . . . . . . . . . . . . . . . 189 8.4.3 Operadores de variación basados en conocimiento . . . . . . . . . . 193 8.4.4 Operadores de selección basados en conocimiento . . . . . . . . . . 196 8.5 Aspectos prácticos de implementación en algoritmos meméticos . . . . . . 197 8.5.1 Elección del algoritmo de búsqueda local . . . . . . . . . . . . . . . 198 8.5.2 Frecuencia de la búsqueda local . . . . . . . . . . . . . . . . . . . . 199 8.5.3 Probabilidad de la búsqueda local . . . . . . . . . . . . . . . . . . 200 8.5.4 Intensidad de la búsqueda local . . . . . . . . . . . . . . . . . . . . 201 8.5.5 Coste de la función de adaptación . . . . . . . . . . . . . . . . . . 202 8.5.6 Manejo de la pérdida de diversidad . . . . . . . . . . . . . . . . . . 202 8.6 Algoritmos meméticos avanzados . . . . . . . . . . . . . . . . . . . . . . . 203 8.7 Aplicaciones de los algoritmos meméticos . . . . . . . . . . . . . . . . . . 205 9 Evaluación de algoritmos evolutivos 207 9.1 Qué evaluar en un algoritmo evolutivo . . . . . . . . . . . . . . . . . . . . 208 9.2 Índices promedio de prestaciones . . . . . . . . . . . . . . . . . . . . . . . 209 9.2.1 Tasa de éxito . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 9.2.2 Valor de adaptación medio del mejor individuo . . . . . . . . . . . 209 9.2.3 Tiempo medio para alcanzar el éxito . . . . . . . . . . . . . . . . . 211 9.3 Medidas de robustez . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213 9.3.1 Robustez a cambios del valor de un parámetro . . . . . . . . . . . 213 9.3.2 Robustez a cambios de la instancia de un problema . . . . . . . . . 215 9.3.3 Robustez frente a las diferentes ejecuciones realizadas . . . . . . . 216 9.4 Estudio del comportamiento estadístico . . . . . . . . . . . . . . . . . . . 216 9.4.1 Margen de error e intervalo de con_anza . . . . . . . . . . . . . . . 217 9.4.2 Test de hipótesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219 9.5 Visualización de resultados . . . . . . . . . . . . . . . . . . . . . . . . . . 222 9.5.1 Curva de progreso . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 9.5.2 Comportamiento frente al cambio de escala del problema . . . . . 224 9.5.3 Otras formas de visualizar resultados . . . . . . . . . . . . . . . . . 225 9.6 Uso de problemas de referencia para evaluar AEs . . . . . . . . . . . . . . 227 II Técnicas avanzadas en computación evolutiva 233 10 Manejo de restricciones 235 10.1 Región factible . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235 10.2 Tipos de problemas que manejan restricciones . . . . . . . . . . . . . . . . 236 10.2.1 Problemas de optimización libre de restricciones . . . . . . . . . . 237 10.2.2 Problemas de optimización con restricciones . . . . . . . . . . . . 238 10.2.3 Problemas de satisfacción de restricciones . . . . . . . . . . . . . . 238 10.3 Manejo de restricciones en algoritmos evolutivos . . . . . . . . . . . . . . 239 10.3.1 Funciones de penalización . . . . . . . . . . . . . . . . . . . . . . . 240 10.3.1.1 Penalización estática . . . . . . . . . . . . . . . . . . . . . 242 10.3.1.2 Penalización dinámica . . . . . . . . . . . . . . . . . . . . 243 10.3.1.3 Penalización adaptativa . . . . . . . . . . . . . . . . . . . 244 10.3.2 Funciones decodi_cadoras . . . . . . . . . . . . . . . . . . . . . . . 245 10.3.3 Separación de función objetivo y restricciones . . . . . . . . . . . 248 10.3.3.1 Memoria conductual . . . . . . . . . . . . . . . . . . . . . 248 10.3.3.2 Reglas de factibilidad . . . . . . . . . . . . . . . . . . . . 249 10.3.3.3 Ordenación estocástica . . . . . . . . . . . . . . . . . . . 251 10.3.3.4 Método "-restringido . . . . . . . . . . . . . . . . . . . . 253 10.3.4 Operadores especiales que garantizan la factibilidad . . . . . . . . 254 10.3.4.1 Operadores que preservan la factibilidad . . . . . . . . . 254 10.3.4.2 Operadores de reparación . . . . . . . . . . . . . . . . . . 256 11 Mantenimiento de la diversidad 261 11.1 Algoritmos evolutivos paralelos de grano grueso . . . . . . . . . . . . . . . 262 11.2 Algoritmos evolutivos paralelos de grano _no . . . . . . . . . . . . . . . . 263 11.3 Reparto de adaptación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264 11.4 Restricción del emparejamiento . . . . . . . . . . . . . . . . . . . . . . . . 266 11.4.1 Métodos tradicionales de restricción del emparejamiento . . . . . . 266 11.4.2 Generalización del método de restricción del emparejamiento . . . 268 11.5 Agrupamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271 11.5.1 Variantes del método original de agrupamiento . . . . . . . . . . . 272 11.5.2 Generalización del método de agrupamiento . . . . . . . . . . . . . 274 11.5.2.1 Agrupamiento generalizado adaptativo basado en diversidad276 11.5.2.2 Agrupamiento generalizado autoadaptativo . . . . . . . . 277 12 Con_guración de parámetros 279 12.1 Sintonización de parámetros . . . . . . . . . . . . . . . . . . . . . . . . . . 279 12.1.1 Inconvenientes de la sintonización manual . . . . . . . . . . . . . . 280 12.1.2 De_nición del problema y nomenclatura . . . . . . . . . . . . . . . 281 12.1.3 Taxonomía de métodos de sintonización . . . . . . . . . . . . . . . 282 12.1.4 Ejemplos de métodos de sintonización de parámetros . . . . . . . . 284 12.1.4.1 Métodos de competición . . . . . . . . . . . . . . . . . . . 284 12.1.4.2 Meta-optimizadores . . . . . . . . . . . . . . . . . . . . . 286 12.1.4.3 Métodos basados en modelo . . . . . . . . . . . . . . . . 287 12.1.4.4 El método LUS . . . . . . . . . . . . . . . . . . . . . . . 288 12.1.4.5 Consideraciones _nales . . . . . . . . . . . . . . . . . . . 291 12.2 Control de parámetros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292 12.2.1 Introducción al control de parámetros . . . . . . . . . . . . . . . . 292 12.2.2 Taxonomía de métodos de control de parámetros . . . . . . . . . . 294 12.2.3 Ejemplos de control de parámetros . . . . . . . . . . . . . . . . . . 297 12.2.3.1 Tamaño de la población . . . . . . . . . . . . . . . . . . . 297 12.2.3.2 Función de adaptación . . . . . . . . . . . . . . . . . . . . 299 12.2.3.3 Cruce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300 12.2.3.4 Mutación . . . . . . . . . . . . . . . . . . . . . . . . . . . 300 12.2.3.5 Selección de supervivientes . . . . . . . . . . . . . . . . . 301 12.2.3.6 Modi_cación de varios parámetros simultáneamente . . . 302 12.2.3.7 Consideraciones _nales . . . . . . . . . . . . . . . . . . . 303 13 Problemas multiobjetivo 305 13.1 Dominancia y frente de Pareto . . . . . . . . . . . . . . . . . . . . . . . . 306 13.2 Tipos de algoritmo evolutivo multiobjetivo . . . . . . . . . . . . . . . . . . 308 13.2.1 Técnicas _a priori_ . . . . . . . . . . . . . . . . . . . . . . . . . . . 308 13.2.2 Técnicas progresivas . . . . . . . . . . . . . . . . . . . . . . . . . . 310 13.2.3 Técnicas _a posteriori_ . . . . . . . . . . . . . . . . . . . . . . . . . 310 13.2.3.1 Muestreo independiente . . . . . . . . . . . . . . . . . . . 311 13.2.3.2 Selección por criterio . . . . . . . . . . . . . . . . . . . . 311 13.2.3.3 Función de adaptación mediante dominancia . . . . . . . 312 13.3 Técnicas avanzadas en algoritmos evolutivos multiobjetivo . . . . . . . . . 315 13.3.1 AEMOs basados en descomposición . . . . . . . . . . . . . . . . . 315 13.3.2 AEMOs meméticos . . . . . . . . . . . . . . . . . . . . . . . . . . . 315 13.3.3 Tratamiento de restricciones mediante AEMOs . . . . . . . . . . . 316 13.3.4 Aplicación de AEMOs a problemas multimodales . . . . . . . . . . 317 13.3.5 Aplicación de AEMOs a problemas dinámicos . . . . . . . . . . . . 317 13.3.5.1 Mantenimiento de la diversidad . . . . . . . . . . . . . . 318 13.3.5.2 Introducción de diversidad tras un cambio en la función de adaptación . . . . . . . . . . . . . . . . . . . . . . . . 318 13.3.5.3 Predicción de cambios en la función de adaptación . . . . 318 13.3.5.4 Uso de memoria . . . . . . . . . . . . . . . . . . . . . . . 319 13.3.5.5 Poblaciones múltiples . . . . . . . . . . . . . . . . . . . . 320 13.4 Ejemplo de aplicación: asignación de horarios de clase . . . . . . . . . . . 320 14 Modelos matemáticos de algoritmos evolutivos 323 14.1 Teorema del esquema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323 14.2 Cadenas de Markov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326 14.2.1 Modelo de Markov para selección uniforme . . . . . . . . . . . . . 327 14.2.2 Modelo de Markov para un algoritmo genético estándar . . . . . . 327 14.2.3 Modelo de Markov para estados agrupados . . . . . . . . . . . . . 328 14.3 Sistemas dinámicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328 14.3.1 Sistema dinámico para un algoritmo genético estándar . . . . . . . 330 14.4 Métodos reduccionistas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331 14.5 Mecánica estadística . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333 14.6 Espacios de búsqueda continuos . . . . . . . . . . . . . . . . . . . . . . . . 334 Anexo A: Traducción de términos relevantes del libro 337 Bibliografía 347 Índice alfabético 397