Detalle del libro
Ver Índice
I Algoritmos evolutivos 1
1 Introducción a la computación evolutiva 3
11 Inspiración en la biología 3
111 Teoría de la evolución 4
112 Del ADN a las proteínas 5
113 Reproducción 7
114 Mutación 7
12 Historia de la computación evolutiva 9
13 Algoritmo evolutivo canónico 10
131 Representación de individuos 12
132 Función de adaptación 13
133 Población 13
134 Inicialización de la población 14
135 Selección de padres 14
136 Operadores de variación 14
137 Selección de supervivientes 15
138 Condición de terminación 15
14 Algoritmos evolutivos como métodos de búsqueda 16
15 Campos de aplicación de la computación evolutiva 17
151 Aplicaciones en clasi_cación 18
152 Aplicaciones en control 18
153 Aplicaciones en diseño 18
154 Aplicaciones en plani_cación 19
155 Aplicaciones en simulación 19
2 Algoritmos genéticos 21
21 Ejemplo introductorio: el problema del viajante 21
22 Representación de individuos 26
221 Representación binaria 28
222 Representación entera 28
223 Representación real 29
224 Representación mediante permutaciones 29
23 Inicialización de la población 30
24 Selección de padres 31
241 Selección proporcional al valor de adaptación 32
242 Selección por ordenación 33
243 Selección por torneo 34
244 Muestreo de distribuciones de probabilidad 35
25 Recombinación 37
251 Operadores de recombinación para representación binaria 37
2511 Cruce por un punto 38
2512 Cruce por n puntos 38
2513 Cruce uniforme 38
252 Operadores de recombinación para representación entera 38
253 Operadores de recombinación para representación real 39
2531 Recombinación discreta 39
2532 Recombinación aritmética 39
254 Operadores de recombinación para representación mediante permutaciones
40
2541 Cruce por orden 41
2542 Cruce por ciclos 41
2543 Cruce parcialmente mapeado 42
2544 Cruce por enlaces 43
26 Mutación 45
261 Operadores de mutación para representación binaria 45
262 Operadores de mutación para representación entera 46
263 Operadores de mutación para representación real 46
264 Operadores de mutación para representación mediante permutaciones 46
2641 Mutación por intercambio 47
2642 Mutación por inserción 47
2643 Mutación por mezcla 47
2644 Mutación por inversión 47
27 Selección de supervivientes 48
28 Algoritmos de estimación de distribuciones 49
29 Ejemplo de aplicación: el problema del viajante 49
3 Estrategias evolutivas 53
31 Introducción: algoritmo EE-(1+1) 53
32 Estrategia evolutiva estándar 56
33 Representación de individuos 57
34 Inicialización de la población 59
35 Selección de padres 59
36 Recombinación 59
37 Mutación 62
371 Interpretación geométrica 64
372 Mutación no correlacionada de 1-tamaño de paso 66
373 Mutación no correlacionada de n-tamaños de paso 67
374 Mutación correlacionada 68
38 Selección de supervivientes 70
39 Variantes de estrategias evolutivas 72
391 CMA-ES: Estrategia evolutiva basada en la adaptación de la matriz
de covarianza 72
310 Ejemplo de aplicación: problema de resolución de ecuaciones diferenciales 76
4 Programación evolutiva 83
41 Ejemplo introductorio: el problema de la hormiga arti_cial 83
42 Representación de individuos 87
43 Inicialización, selección de padres y recombinación 89
44 Mutación 90
45 Selección de supervivientes 92
46 Ejemplo de aplicación: diseño de redes neuronales arti_ciales 92
461 Introducción a las redes neuronales arti_ciales 93
462 Redes neuronales arti_ciales evolutivas 94
4621 Evolución de los pesos de las conexiones 94
4622 Evolución de la topología 95
4623 Evolución conjunta de pesos y topología: EPNet 96
5 Evolución diferencial 99
51 Ejemplo introductorio 100
52 Evolución diferencial canónica 101
53 Representación de individuos 104
54 Algoritmo clásico en ED: _DE/rand/1 /bin_ 105
55 Inicialización de la población 105
56 Selección de padres 107
57 Operadores de variación 107
571 Mutación 108
572 Recombinación (discreta o binomial) 108
58 Selección de supervivientes 109
59 Otras variantes en evolución diferencial 109
591 Formas de seleccionar el vector base 110
592 Incremento del número de diferenciales 111
593 Otros tipos de recombinación 112
594 Otras variantes usadas en entornos complejos 113
510 Aspectos prácticos en evolución diferencial 114
5101 Inicialización de la población 114
5102 Restringir la búsqueda al espacio de búsqueda 114
5103 Acerca del valor de F 115
5104 Acerca del valor de CR 116
5105 Recomendaciones generales 117
511 Aplicaciones 117
512 Ejemplo de aplicación: optimización de una función multimodal 118
6 Programación genética 125
61 Ejemplo introductorio: regresión simbólica 126
62 Algoritmo estándar en programación genética 130
63 Representación de individuos 131
64 Inicialización de la población 134
641 Método de crecimiento uniforme 135
642 Método de crecimiento no uniforme 135
643 Método de crecimiento mixto 135
65 Selección de padres 136
66 Operadores de variación 137
661 Reproducción 137
662 Recombinación 137
663 Mutación 138
664 Mutación vs recombinación 139
67 Selección de supervivientes 140
68 Funciones de_nidas automáticamente 140
69 El efecto engorde 141
610 Variantes 143
6101 Evolución gramatical 143
6102 Programación de expresiones de genes 146
611 Ejemplo de aplicación: diseño de circuitos electrónicos analógicos 149
6111 De_nición del problema 149
6112 Diseño de circuitos analógicos basado en EG 149
7 Sistemas clasi_cadores evolutivos 157
71 Ejemplo introductorio: el multiplexor 158
72 Sistema clasi_cador evolutivo genérico 160
73 Sistema clasi_cador evolutivo basado en fuerza: ZCS 162
74 Sistema clasi_cador evolutivo basado en exactitud: XCS 164
75 Enfoque tipo Pittsburgh 166
76 Representaciones alternativas de reglas 167
761 Representación basada en intervalos 167
762 Representación basada en hiperelipsoides 167
763 Representación basada en envolturas convexas 168
764 Representación basada en redes neuronales 169
765 Representación desordenada 169
766 Representación basada en expresiones S 170
767 Representación basada en expresiones de genes 170
768 Representación basada en lógica difusa 171
77 Ejemplo de aplicación: diagnóstico de cáncer 172
8 Algoritmos meméticos 175
81 Introducción 176
82 Características de un algoritmo memético 177
821 Heurísticas y metaheurísticas 178
822 Algoritmo memético canónico 178
83 Búsqueda local 181
831 Espacios de búsqueda combinatorios 182
832 Espacios de búsqueda continuos 184
84 Algoritmos meméticos basados en la hibridación de un algoritmo evolutivo 188
841 Representación 188
842 Inicialización de la población 189
843 Operadores de variación basados en conocimiento 193
844 Operadores de selección basados en conocimiento 196
85 Aspectos prácticos de implementación en algoritmos meméticos 197
851 Elección del algoritmo de búsqueda local 198
852 Frecuencia de la búsqueda local 199
853 Probabilidad de la búsqueda local 200
854 Intensidad de la búsqueda local 201
855 Coste de la función de adaptación 202
856 Manejo de la pérdida de diversidad 202
86 Algoritmos meméticos avanzados 203
87 Aplicaciones de los algoritmos meméticos 205
9 Evaluación de algoritmos evolutivos 207
91 Qué evaluar en un algoritmo evolutivo 208
92 Índices promedio de prestaciones 209
921 Tasa de éxito 209
922 Valor de adaptación medio del mejor individuo 209
923 Tiempo medio para alcanzar el éxito 211
93 Medidas de robustez 213
931 Robustez a cambios del valor de un parámetro 213
932 Robustez a cambios de la instancia de un problema 215
933 Robustez frente a las diferentes ejecuciones realizadas 216
94 Estudio del comportamiento estadístico 216
941 Margen de error e intervalo de con_anza 217
942 Test de hipótesis 219
95 Visualización de resultados 222
951 Curva de progreso 222
952 Comportamiento frente al cambio de escala del problema 224
953 Otras formas de visualizar resultados 225
96 Uso de problemas de referencia para evaluar AEs 227
II Técnicas avanzadas en computación evolutiva 233
10 Manejo de restricciones 235
101 Región factible 235
102 Tipos de problemas que manejan restricciones 236
1021 Problemas de optimización libre de restricciones 237
1022 Problemas de optimización con restricciones 238
1023 Problemas de satisfacción de restricciones 238
103 Manejo de restricciones en algoritmos evolutivos 239
1031 Funciones de penalización 240
10311 Penalización estática 242
10312 Penalización dinámica 243
10313 Penalización adaptativa 244
1032 Funciones decodi_cadoras 245
1033 Separación de función objetivo y restricciones 248
10331 Memoria conductual 248
10332 Reglas de factibilidad 249
10333 Ordenación estocástica 251
10334 Método "-restringido 253
1034 Operadores especiales que garantizan la factibilidad 254
10341 Operadores que preservan la factibilidad 254
10342 Operadores de reparación 256
11 Mantenimiento de la diversidad 261
111 Algoritmos evolutivos paralelos de grano grueso 262
112 Algoritmos evolutivos paralelos de grano _no 263
113 Reparto de adaptación 264
114 Restricción del emparejamiento 266
1141 Métodos tradicionales de restricción del emparejamiento 266
1142 Generalización del método de restricción del emparejamiento 268
115 Agrupamiento 271
1151 Variantes del método original de agrupamiento 272
1152 Generalización del método de agrupamiento 274
11521 Agrupamiento generalizado adaptativo basado en diversidad276
11522 Agrupamiento generalizado autoadaptativo 277
12 Con_guración de parámetros 279
121 Sintonización de parámetros 279
1211 Inconvenientes de la sintonización manual 280
1212 De_nición del problema y nomenclatura 281
1213 Taxonomía de métodos de sintonización 282
1214 Ejemplos de métodos de sintonización de parámetros 284
12141 Métodos de competición 284
12142 Meta-optimizadores 286
12143 Métodos basados en modelo 287
12144 El método LUS 288
12145 Consideraciones _nales 291
122 Control de parámetros 292
1221 Introducción al control de parámetros 292
1222 Taxonomía de métodos de control de parámetros 294
1223 Ejemplos de control de parámetros 297
12231 Tamaño de la población 297
12232 Función de adaptación 299
12233 Cruce 300
12234 Mutación 300
12235 Selección de supervivientes 301
12236 Modi_cación de varios parámetros simultáneamente 302
12237 Consideraciones _nales 303
13 Problemas multiobjetivo 305
131 Dominancia y frente de Pareto 306
132 Tipos de algoritmo evolutivo multiobjetivo 308
1321 Técnicas _a priori_ 308
1322 Técnicas progresivas 310
1323 Técnicas _a posteriori_ 310
13231 Muestreo independiente 311
13232 Selección por criterio 311
13233 Función de adaptación mediante dominancia 312
133 Técnicas avanzadas en algoritmos evolutivos multiobjetivo 315
1331 AEMOs basados en descomposición 315
1332 AEMOs meméticos 315
1333 Tratamiento de restricciones mediante AEMOs 316
1334 Aplicación de AEMOs a problemas multimodales 317
1335 Aplicación de AEMOs a problemas dinámicos 317
13351 Mantenimiento de la diversidad 318
13352 Introducción de diversidad tras un cambio en la función
de adaptación 318
13353 Predicción de cambios en la función de adaptación 318
13354 Uso de memoria 319
13355 Poblaciones múltiples 320
134 Ejemplo de aplicación: asignación de horarios de clase 320
14 Modelos matemáticos de algoritmos evolutivos 323
141 Teorema del esquema 323
142 Cadenas de Markov 326
1421 Modelo de Markov para selección uniforme 327
1422 Modelo de Markov para un algoritmo genético estándar 327
1423 Modelo de Markov para estados agrupados 328
143 Sistemas dinámicos 328
1431 Sistema dinámico para un algoritmo genético estándar 330
144 Métodos reduccionistas 331
145 Mecánica estadística 333
146 Espacios de búsqueda continuos 334
Anexo A: Traducción de términos relevantes del libro 337
Bibliografía 347
Índice alfabético 397
La computación evolutiva puede mejorar su vida y la del resto de personas. ¿Quiere saber cómo?
Adéntrese en este libro y descubra la computación evolutiva, una rama de la inteligencia artificial formada por una familia de algoritmos de optimización global: los algoritmos evolutivos.
Inspirados en la evolución natural, los algoritmos evolutivos son capaces de obtener soluciones equiparables a las de expertos humanos en gran variedad de problemas. Además, son atractivos por aportar soluciones novedosas y brillantes que podrían ser difíciles de lograr por un humano.
A lo largo de las últimas décadas, han surgido diferentes variantes de algoritmos evolutivos como resultado del gran interés que han despertado en la comunidad científica.
En esta guía encontrará explicaciones detalladas de:
- Las subáreas de la computación evolutiva, desde las ideas pioneras hasta las más actuales y novedosas.
- Los principales tipos de algoritmos evolutivos.
- Las técnicas avanzadas que dotan a estos algoritmos de mayor potencia y versatilidad.
Si quiere conseguir una perspectiva global sobre la computación evolutiva, tiene a su alcance el libro adecuado: no pierda la oportunidad de leerlo.
Los autores del libro son profesores titulares en el área de Ciencia de la Computación e Inteligencia Artificial y pertenecen al Departamento de Inteligencia Artificial de la Universidad Nacional de Educación a Distancia (UNED). Además de su actividad en docencia, realizan investigación en diferentes campos de la inteligencia artificial y de la computación evolutiva