ISBN:
9788426727558
Formato:
17x24 cms

Fundamentos de la computación evolutiva

25,60 24,33
25,60 24,33

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.

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

A color
Páginas:
Edición:
Año Publicación:
ISBN:
9788426727558
Formato:
17x24 cms
Colección

Relacionados

¿Quiéres conocer las últimas novedades?

Inscribiéndote recibirás unos regalos exclusivos para ti