Fundamentos de la Computación Evolutiva

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