Apuntes Coello
Apuntes Coello
Apuntes Coello
(Notas de Curso)
c 2000,2001,2002,2003,2004
Todos los derechos reservados
Dedicatorias
A mi esposa Lupita,
por todo el apoyo que
siempre me ha brindado.
lejos en mi profesion.
Contenido
1
Conceptos Basicos
1.1 Analisis de algoritmos . . . . . .
1.2 Tecnicas Clasicas de Optimizacion
1.3 Tecnicas heursticas . . . . . . . .
1.4 Conceptos Importantes . . . . . .
1.5 Problemas propuestos . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
23
23
27
33
35
38
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
41
41
43
44
45
46
47
48
50
50
51
52
52
53
54
55
56
57
57
58
60
2.21
2.22
2.23
2.24
Ecosistemas artificiales
Programacion genetica
Dinamica evolutiva . .
Problemas propuestos .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. 61
. 62
. 63
. 64
3 Principales Paradigmas
3.1 Introduccion . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.1 Programacion evolutiva . . . . . . . . . . . . . . . . . . .
3.1.1.1 Algoritmo . . . . . . . . . . . . . . . . . . . .
3.1.1.2 Ejemplo . . . . . . . . . . . . . . . . . . . . .
3.1.2 Aplicaciones . . . . . . . . . . . . . . . . . . . . . . . .
3.1.3 Estrategias Evolutivas . . . . . . . . . . . . . . . . . . .
3.1.3.1 Algoritmo . . . . . . . . . . . . . . . . . . . .
3.1.3.2 Ejemplo . . . . . . . . . . . . . . . . . . . . .
3.1.3.3 Convergencia . . . . . . . . . . . . . . . . . .
3.1.3.4 Auto-Adaptacion . . . . . . . . . . . . . . . .
3.1.3.5 Estrategias Evolutivas vs Programacion Evolutiva
3.1.3.6 Aplicaciones . . . . . . . . . . . . . . . . . . .
3.1.4 Algoritmos Geneticos . . . . . . . . . . . . . . . . . . .
3.1.4.1 Algoritmo . . . . . . . . . . . . . . . . . . . .
3.1.4.2 Algoritmos geneticos vs otras tecnicas evolutivas
3.1.4.3 Aplicaciones . . . . . . . . . . . . . . . . . . .
3.2 Diferencias de las tecnicas evolutivas con respecto a las tradicionales
3.3 Ventajas de las Tecnicas Evolutivas . . . . . . . . . . . . . . . .
3.4 Crticas a las Tecnicas Evolutivas . . . . . . . . . . . . . . . . . .
3.5 Problemas Propuestos . . . . . . . . . . . . . . . . . . . . . . . .
4 Terminologa Biologica y de Computacion Evolutiva
4.1 Introduccion . . . . . . . . . . . . . . . . . . . .
4.2 Tipos de Aprendizaje . . . . . . . . . . . . . . .
4.3 Conceptos de Computacion Evolutiva . . . . . .
4.4 Problemas propuestos . . . . . . . . . . . . . . .
5 La Importancia de la Representacion
5.1 Introduccion . . . . . . . . . . . . . . .
5.2 Codigos de Gray . . . . . . . . . . . .
5.3 Codificando Numeros Reales . . . . . .
5.4 Representaciones de Longitud Variable .
6
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
67
67
68
68
69
69
70
70
70
71
72
73
73
74
74
75
76
78
78
79
80
.
.
.
.
83
. 83
. 89
. 89
. 94
.
.
.
.
95
95
98
99
102
.
.
.
.
5.5
5.6
5.7
5.8
5.9
5.10
6
Representacion de a rbol . . . . . . . . . . . . . . . . . . . . . .
Algoritmo Genetico Estructurado . . . . . . . . . . . . . . . . .
Otras propuestas . . . . . . . . . . . . . . . . . . . . . . . . . .
Tendencias futuras . . . . . . . . . . . . . . . . . . . . . . . .
Recomendaciones para el Diseno de una Buena Representacion .
Problemas propuestos . . . . . . . . . . . . . . . . . . . . . . .
Tecnicas de Seleccion
6.1 Seleccion Proporcional . . . . . . . . . . . . . . . . . . . . .
6.1.1 La Ruleta . . . . . . . . . . . . . . . . . . . . . . . .
6.1.1.1 Analisis de la Ruleta . . . . . . . . . . . . .
6.1.2 Sobrante Estocastico . . . . . . . . . . . . . . . . . .
6.1.2.1 Analisis del Sobrante Estocastico . . . . . .
6.1.3 Universal Estocastica . . . . . . . . . . . . . . . . . .
6.1.3.1 Analisis de la seleccion universal estocastica
6.1.4 Muestreo Determinstico . . . . . . . . . . . . . . . .
6.1.4.1 Analisis del muestreo determinstico . . . .
6.1.5 Escalamiento Sigma . . . . . . . . . . . . . . . . . .
6.1.5.1 Analisis del escalamiento sigma . . . . . . .
6.1.6 Seleccion por Jerarquas . . . . . . . . . . . . . . . .
6.1.6.1 Analisis de las jerarquas lineales . . . . . .
6.1.7 Seleccion de Boltzmann . . . . . . . . . . . . . . . .
6.1.7.1 Analisis de la seleccion de Boltzmann . . .
6.2 Seleccion Mediante Torneo . . . . . . . . . . . . . . . . . . .
6.2.1 Analisis de la seleccion mediante torneo . . . . . . . .
6.3 Seleccion de Estado Uniforme . . . . . . . . . . . . . . . . .
6.3.1 Analisis de la Seleccion de Estado Uniforme . . . . .
6.4 Brecha Generacional . . . . . . . . . . . . . . . . . . . . . .
6.5 Otras Tecnicas de Seleccion . . . . . . . . . . . . . . . . . .
6.5.1 Seleccion Disruptiva . . . . . . . . . . . . . . . . . .
6.5.1.1 Analisis de la seleccion disruptiva . . . . . .
6.5.2 Jerarquas No Lineales . . . . . . . . . . . . . . . . .
6.5.2.1 Analisis de las jerarquas no lineales . . . .
6.5.3 Seleccion Competitiva . . . . . . . . . . . . . . . . .
6.6 Clasificaciones de Tecnicas de Seleccion . . . . . . . . . . . .
6.7 Problemas Propuestos . . . . . . . . . . . . . . . . . . . . . .
7
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
105
110
112
112
113
114
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
115
115
116
117
117
119
119
121
121
122
122
123
123
124
125
126
126
128
129
130
130
131
131
132
132
133
135
135
136
7 Tecnicas de Cruza
7.1 Introduccion . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7.1.1 Cruza de un punto . . . . . . . . . . . . . . . . . . . . .
7.1.1.1 Orden de un esquema . . . . . . . . . . . . . .
7.1.1.2 Longitud de definicion . . . . . . . . . . . . . .
7.1.1.3 Analisis de la cruza de un punto . . . . . . . . .
7.1.2 Cruza de dos puntos . . . . . . . . . . . . . . . . . . . .
7.1.3 Cruza uniforme . . . . . . . . . . . . . . . . . . . . . . .
7.1.4 Cruza Acentuada . . . . . . . . . . . . . . . . . . . . . .
7.1.4.1 Observaciones sobre la cruza acentuada . . . .
7.2 Sesgos de la Cruza . . . . . . . . . . . . . . . . . . . . . . . . .
7.2.1 Sesgo distribucional . . . . . . . . . . . . . . . . . . . .
7.2.2 Sesgo posicional . . . . . . . . . . . . . . . . . . . . . .
7.3 Variantes de la Cruza . . . . . . . . . . . . . . . . . . . . . . . .
7.4 Comportamiento Deseable de la Cruza . . . . . . . . . . . . . . .
7.5 Cruza para representaciones alternativas . . . . . . . . . . . . . .
7.5.1 Cruza para Programacion Genetica . . . . . . . . . . . .
7.5.1.1 Observaciones sobre la cruza para programacion
genetica . . . . . . . . . . . . . . . . . . . . .
7.5.2 Cruza para Permutaciones . . . . . . . . . . . . . . . . .
7.5.2.1 Order Crossover (OX) . . . . . . . . . . . . . .
7.5.2.2 Partially Mapped Crossover (PMX) . . . . . . .
7.5.2.3 Position-based Crossover . . . . . . . . . . . .
7.5.2.4 Order-based Crossover . . . . . . . . . . . . .
7.5.2.5 Cycle Crossover (CX) . . . . . . . . . . . . . .
7.5.3 Otras propuestas . . . . . . . . . . . . . . . . . . . . . .
7.6 Cruza para Representacion Real . . . . . . . . . . . . . . . . . .
7.6.1 Cruza Simple . . . . . . . . . . . . . . . . . . . . . . . .
7.6.2 Cruza de dos puntos . . . . . . . . . . . . . . . . . . . .
7.6.3 Cruza uniforme . . . . . . . . . . . . . . . . . . . . . . .
7.6.4 Cruza intermedia . . . . . . . . . . . . . . . . . . . . . .
7.6.5 Cruza aritmetica simple . . . . . . . . . . . . . . . . . .
7.6.6 Cruza aritmetica total . . . . . . . . . . . . . . . . . . . .
7.6.7 Simulated Binary Crossover (SBX) . . . . . . . . . . . .
7.7 Problemas Propuestos . . . . . . . . . . . . . . . . . . . . . . . .
8
141
141
141
142
142
143
143
145
145
146
147
147
148
148
149
149
149
150
151
152
153
153
154
155
157
157
158
158
158
159
159
160
161
162
Mutacion
8.1 Mutacion para Permutaciones . . . . . . . . . . . . . .
8.1.1 Mutacion por Insercion . . . . . . . . . . . . .
8.1.2 Mutacion por Desplazamiento . . . . . . . . .
8.1.3 Mutacion por Intercambio Recproco . . . . .
8.1.4 Mutacion Heurstica . . . . . . . . . . . . . .
8.2 Mutacion para Programacion Genetica . . . . . . . . .
8.3 Mutacion para Representacion Real . . . . . . . . . .
8.3.1 Mutacion No Uniforme . . . . . . . . . . . . .
8.3.2 Mutacion de Lmite . . . . . . . . . . . . . . .
8.3.3 Mutacion Uniforme . . . . . . . . . . . . . . .
8.3.4 Parameter-Based Mutation . . . . . . . . . . .
8.4 Cruza vs. Mutacion . . . . . . . . . . . . . . . . . . .
8.4.1 Cual es el poder exploratorio de la mutacion?
8.5 Problemas Propuestos . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
165
165
165
166
166
166
167
168
168
169
170
171
172
172
173
Ajuste de Parametros
9.1 Introduccion . . . . . . . . . . . . . . . . . . . . . . . .
9.2 Los experimentos de De Jong . . . . . . . . . . . . . . .
9.3 Tamano o ptimo de poblacion . . . . . . . . . . . . . . .
9.4 Los experimentos de Schaffer . . . . . . . . . . . . . . .
9.5 Auto-adaptacion . . . . . . . . . . . . . . . . . . . . . .
9.5.1 La propuesta de Davis . . . . . . . . . . . . . .
9.5.2 Crticas a la auto-adaptacion . . . . . . . . . . .
9.6 Mecanismos de Adaptacion . . . . . . . . . . . . . . . .
9.6.1 Mutaciones Variables . . . . . . . . . . . . . . .
9.6.2 Mutacion dependiente de la aptitud . . . . . . .
9.6.3 AGs adaptativos . . . . . . . . . . . . . . . . .
9.6.4 Tecnicas Adaptativas Basadas en Logica Difusa .
9.6.5 Representaciones Adaptativas . . . . . . . . . .
9.7 Problemas Propuestos . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
175
175
175
178
180
181
184
185
185
185
186
186
187
187
189
.
.
.
.
.
191
191
193
193
193
194
10 Manejo de Restricciones
10.1 Funciones de Penalizacion . . .
10.1.1 Pena de Muerte . . . . .
10.1.1.1 Analisis . . .
10.1.2 Penalizaciones estaticas
10.1.2.1 Analisis . . .
9
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
217
219
220
221
221
222
223
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
11
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
224
224
225
226
226
229
231
231
234
235
237
239
.
.
.
.
.
.
.
241
241
243
245
245
245
245
246
.
.
.
.
.
.
.
.
247
247
247
248
248
249
249
251
252
.
.
.
.
.
255
255
257
258
259
263
12
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
263
265
266
266
267
270
271
271
272
.
.
.
.
273
273
274
275
276
Lista de Tablas
3.1
Tabla comparativa de los tres paradigmas principales que conforman la computacion evolutiva [9]. . . . . . . . . . . . . . . . . . 77
8.1
13
14
Lista de Figuras
1.1
1.2
1.3
35
36
1.4
2.1
2.2
2.3
2.4
2.5
2.6
2.7
2.8
2.9
2.10
2.11
2.12
2.13
2.14
2.15
2.16
2.17
2.18
2.19
42
42
44
45
46
47
49
49
51
52
53
57
59
60
61
61
63
64
65
3.1
Portada de la edicion reciente (1999) del libro Artificial Intelligence through Simulated Evolution, con el cual se originara la
programacion evolutiva. . . . . . . . . . . . . . . . . . . . . . . . 68
15
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
37
39
3.2
3.3
3.4
3.5
3.6
3.7
4.1
4.2
4.3
4.4
4.5
4.6
4.7
4.8
69
72
74
75
76
79
4.9
4.10
4.11
4.12
4.13
4.14
5.1
5.2
5.3
83
84
84
85
86
86
87
90
90
90
91
91
92
93
5.4
5.5
5.6
5.7
5.8
5.9
5.10
5.11
5.12
5.13
5.14
5.15
5.16
5.17
7.1
7.2
7.3
7.4
7.5
Una representacion entera de numeros reales. La cadena completa es decodificada como un solo numero real multiplicando y
dividiendo cada dgito de acuerdo a su posicion. . . . . . . . . . .
Otra representacion entera de numeros reales. En este caso, cada
gene contiene un numero real representado como un entero largo. .
Dos ejemplos de cadenas validas en un algoritmo genetico desordenado. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Un ejemplo del operador de corte en un AG desordenado. La
lnea gruesa indica el punto de corte. . . . . . . . . . . . . . . . .
Un ejemplo del operador union en un AG desordenado. La lnea
gruesa muestra la parte de la cadena que fue agregada. . . . . . .
Un ejemplo de un cromosoma usado en programacion genetica. .
Los nodos del a rbol se numeran antes de aplicar el operador de
cruza. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Los dos hijos generados despues de efectuar la cruza. . . . . . . .
Un ejemplo de mutacion en la programacion genetica. . . . . . . .
Un ejemplo de permutacion en la programacion genetica. . . . . .
Un ejemplo de encapsulamiento en programacion genetica. . . . .
Un ejemplo de estructura de dos niveles de un AG estructurado. .
Una representacion cromosomica de la estructura de 2 niveles del
AG estructurado. . . . . . . . . . . . . . . . . . . . . . . . . . .
Ejemplo de una estructura de datos usada para implementar un
AG estructurado. . . . . . . . . . . . . . . . . . . . . . . . . . .
101
102
103
104
105
106
107
107
108
109
109
110
111
111
7.6
Cruza de un punto. . . . . . . . . . . . . . . . . . . . . . . . . .
Cruza de dos puntos. . . . . . . . . . . . . . . . . . . . . . . . .
Cruza uniforme. . . . . . . . . . . . . . . . . . . . . . . . . . . .
Cruza Acentuada. . . . . . . . . . . . . . . . . . . . . . . . . . .
Un ejemplo con dos padres seleccionados para cruzarse, en programacion genetica. . . . . . . . . . . . . . . . . . . . . . . . . .
Los 2 hijos resultantes de la cruza entre los padres de la figura 7.5
142
144
144
146
8.1
8.2
150
151
clase de
. . . . .
clase de
. . . . .
problemas deceptivos de
. . . . . . . . . . . . . . . 234
problemas deceptivos de
. . . . . . . . . . . . . . . 235
18
256
258
259
262
264
264
265
266
268
268
269
270
Introduccion
Estas notas de curso son producto de la experiencia de haber impartido clases de
computacion evolutiva a nivel posgrado durante los u ltimos cinco anos.
El material contenido en estas paginas ha sido producto de muchas horas de
trabajo y esfuerzo y pretenden dar una vision general (si bien no completa) de lo
que es la computacion evolutiva y de sus alcances. El objetivo de este material, es
servir como apoyo para la ensenanza de un curso introductorio a la computacion
evolutiva a nivel maestra o doctorado, aunque se requiere obviamente de material
complementario (principalmente referencias bibliograficas). Por lo demas, estas
notas pretenden ser auto-contenidas, de manera que se haga innecesario consultar
otras fuentes bibliograficas (introductorias) adicionales.
La organizacion de estas notas es la siguiente: en el Captulo 1 se proporcionan algunos conceptos basicos de analisis de algoritmos y de optimizacion con
tecnicas clasicas. Partiendo de las limitaciones de las tecnicas clasicas, se plantea
la motivacion para el uso de heursticas en problemas de busqueda y optimizacion
de alta complejidad.
En el Captulo 2 se hace un rapido recorrido historico de la computacion evolutiva, yendo desde el Lamarckismo hasta las corrientes mas modernas, como la
dinamica evolutiva y la programacion genetica.
El Captulo 3 da un panorama general de los tres grandes paradigmas en computacion evolutiva (la programacion evolutiva, las estrategias evolutivas y el algoritmo genetico), describiendo el algoritmo basico de cada uno de ellos as como
algunas de sus aplicaciones. En ese captulo tambien se mencionan algunas de las
crticas de que ha sido objeto la computacion evolutiva (sobre todo, de parte de
los investigadores de IA simbolica).
En el Captulo 4 se proporciona una breve terminologa biologica, junto con
explicaciones del uso que se da a dichos terminos en computacion evolutiva.
El problema de la representacion, que resulta vital en los algoritmos geneticos,
es tratado en el Captulo 5.
19
20
Reconocimientos
La elaboracion de estas notas no habra sido posible sin la ayuda de la Mat. Ma.
Margarita Reyes Sierra, quien capturo mucho de este texto en formato LATEX2 y
convirtio mis bosquejos a mano en ntidas imagenes en Xfig.
Agradezco al Dr. Arturo Hernandez Aguirre sus incontables (y a veces interminables) discusiones en torno a diferentes temas, entre los que se incluye la
computacion evolutiva. Sus comentarios constructivos siempre me han resultado
de enorme vala.
Manifiesto tambien mi agradecimiento por la generosa ayuda del Laboratorio
Nacional de Informatica Avanzada (LANIA), del CINVESTAV-IPN y de REDIICONACyT, a quienes se debe en gran parte, haber podido preparar este material
didactico. Doy las gracias muy especialmente a la Dra. Cristina Loyo Varela,
Directora General del LANIA, quien siempre me brindo su apoyo incondicional
en todos mis proyectos.
Extiendo tambien un cordial reconocimiento a todos los estudiantes que he
tenido a lo largo de mi vida. Ha sido a traves de ellos que me he nutrido de ricas
experiencias docentes que han forjado mi actual estilo de ensenanza. Gracias a
todos por los buenos y, por que no?, tambien por los malos ratos que me hicieron
pasar.
21
22
Captulo 1
Conceptos Basicos
Antes de aventurarse a tomar un curso de computacion evolutiva (o sobre heursticas
de cualquier otro tipo), es muy importante tener frescos en la memoria algunos
conceptos basicos a fin de poder entender de manera clara la motivacion para desarrollar y usar heursticas.
De tal forma, iniciaremos el curso repasando algunos conceptos fundamentales de analisis de algoritmos y teora de la computacion.
(2) for i = 1 to
do
23
end for i
(3) for i = 1 to do
for j = 1 to do
end for j
end for i
es:
Una de las notaciones mas usadas para expresar la complejidad de un algoritmo es la denominada O (big-O, en ingles). Formalmente, la definimos de la
siguiente manera:
Definicion:
tales que
!
!
132(546 798;:%<46 5461 7=8>:%5461 ?54
@A54
1CBED;
Algunos algoritmos conocidos y sus complejidades correspondientes en esta
notacion son los siguientes:
24
2. Buscar un elemento en una lista ordenada: 1 7=8>:!
3. Quicksort: 1 7=8>:!
4. Calcular el determinante de una matriz: 1 @
5. Multiplicacion matricial: "F G"H
6. Bubble Sort:
1. Buscar un elemento en una lista no ordenada:
Los problemas cuya complejidad esta acotada por un polinomio (los primeros
seis o rdenes de magnitud de la jerarqua mostrada anteriormente) son los denominados problemas P. Mas detalladamente, podemos decir que un problema
pertenece a la clase si puede ser resuelto en tiempo polinomial en una computadora determinstica.
El termino determinstico significa que sin importar lo que haga el algoritmo,
solo hay una cosa que puede hacer a continuacion (es decir, el paso siguiente se
determina por los pasos anteriores). Los ejemplos de algoritmos conocidos dados
anteriormente, pertenecen todos a la clase P.
Un problema pertenece a la clase NP si puede ser resuelto en tiempo polinomial pero usando una computadora no determinstica.
Cuando una computadora no determinstica es confrontada con varias opciones, tiene el poder de adivinar la correcta (en caso de que e sta exista). Una
computadora no determinstica no hace nunca elecciones incorrectas que la hagan
regresar a un estado previo.
Consideremos el siguiente ejemplo de un algoritmo no determinstico en el
.
cual queremos buscar un elemento en un conjunto de elementos A[1: ],
Se quiere determinar un ndice tal que A[j]= , o
si
.
KML OPRN Q
I,J2
QS K>T
j = elige [1: ]
if
= then print(j)
else print(0)
UPRN Q
132(
N
NP.
1 B D
V DEWX HCY[Z
Para tener idea de estas magnitudes, basta decir que solo hay 1,000,000,000,
000,000,000,000 litros de agua en el planeta.
26
a`
de(f .
a`
H . Hacer bc]2 .
g ` f , definida como:
g ` fihjd0fkhlde Xf
(1.1)
`
g
4. Determinar la longitud o ptima de incremento mofn en la direccion ` f , y hacer:
a ` fqp a ` frsm fn g ` f! a ` fthUm fn de(f
(1.2)
H
27
5. Checar la optimalidad de
contrario, ir al paso 6.
6. Hacer
a ` fqp
H.
bcb2 . Ir al paso 2.
Ejemplo:
Min
a` z L
H
L6{
zi} ~ }
z w2
; yB(
}
}
de|j
~ H { z h.2 yB( H H sBE {
d H ^de a ` H h2 2 {
z h.2
g` i
H hlde H
2 {
Determinar mtn :
H
a ` a ` ym n g `
H H H
a ` H ymtnH g ` H hjm Hvu m H , lo cual se obtiene de:
z L
z h.2
L{ sm H 2 {
Y sabemos que:
mXnH
!~>m
H B>m H h
BL
de donde obtenemos:
mH
e igualar el
m nH ]2 .
bc^B , y:
a ` z L 2 z .h 2 z .h 2
L
{
2 {
2 {
Ahora
z 2 hUyB
z h2
a
d de ` h2 h
BsBy{
2 {
z L
Como de N
entonces tenemos que continuar con una iteracion mas:
6
L
{
g` z 2
2 {
Calculemos ahora mn a partir de:
z h2
z 2
2 { sm 2 {
de donde obtenemos:
h2wOm 2%
m ih2w
m h62wOm !OBrh2wOm
Brh2
m 2
m M2wsm 0 u M_>m hOB>m h
2
Para hallar m n :
!~ m ]2L+m hOBML
de donde: m ]2(~>_LB
Por lo que:
29
a ` a ` ymtn g `
@ z z
a ` h 2 H 2 z .h 2 H z jh L
@
2 {
U
2 {
2 H {
>2 B {
Procedemos nuevamente a checar optimalidad de esta solucion:
z 2 OthL+yBr32>B>
z LB
d @ h2yBr3hjL+sBr2>B>\{ hLB6{
z L
Como de N
@
L6{ tenemos que seguir iterando.
a`
H.
3. Obtener
m nH
a`
g` k
a
H hlde ` H %^de H
usando:
g`
a` a` y
n
m
H H H
5. Calcular
a qf p a f ym fn g ` f
H
30
g`
H . Hacer biB
a qf p
H
a f p
H
6. Evaluar la optimalidad de
. Si
es o ptimo, detener el proceso. De
y regresar al paso 4.
lo contrario,
bcb2
Ejemplo:
Min
a` z L
H
L {
Iteracion 1
z } ! ~ }
z 52 O; yBE
de| } !~ } H { h52 yBE H yB( {
z
H
a
2
d H de ` H h2 {
z h.2
g
La direccion de busqueda es: ` ihjd
H
H
2 {
g
a
Para obtener mXn , debemos minimizar ` Jm `
H H H
H
tanto:
a ` ym g ` z L sm z h.2
H H H
L
{ H 2 {
g
a
` H ym H ` H ^3hlm H?u m H
hlm H h
m H yBr3hlm H yBhjm H m H ymXH
]hlB;m H yB>m H h
B>m H sm H m H h
B>m H
!~ m ^B;m h
BL
H
H
m nH ]2
a ` a ` ymtn g ` z L 2 z h2 z h2
H H H
L {
2 {
2 {
31
.
con respecto a
m H.
Por
a ` z h 2
2 {
Iteracion 2
z 25OthjB>sBr2(
a
de|w^de ` h25yBr3h.2(sBr20\{
z h2
d h2O{
g ` ihlde | g `
z
z | H
22U{ ] ( h2 2 {
g` z L
By{ z
a ` sm g ` h2 sm z L
2 { B {
a ` ym g ` h2 u 2yB>m %
h.2h325sB>m yBr3h.20 yBr3h.2(2wsB>m M2wsB>m
h.2h
2h
B>m yBlhOBr325sB>m 2
+m
+m
]hjB>m h
BlhU*m 2
*m
*mX *mX hUB>m h
2
!~ m +m h
BML
mn ]2(~E
a ` a ` ymtn g ` z h.2 2(~E z L
@ z
2 {
B6{
a ` h2
2>_6{
Iteracion 3
z 52 Oth2(sBr2>_>
a
de|^de ` @ h52 yBr3h.2(sBr2;_>{
32
z L
d @
L {
g ` ihjd | g `
@
@ |
z L
z L
$
L{ ] ( By{
g` z L
@
L
{
nH ]h2 u n ]2>_
a`
@
es la solucion o ptima.
Existen tambien tecnicas que construyen parcialmente una solucion a un problema. Por ejemplo, la programacion dinamica y el metodo de ramificacion y
busqueda (branch & bound).
Cuando enfrentamos un cierto problema de optimizacion, si la funcion a optimizarse se encuentra definida en forma algebraica, es importante intentar resolverla primero con tecnicas clasicas, antes de utilizar cualquier heurstica.
Busqueda Tabu
Recocido Simulado
Escalando la Colina
La busqueda
tabu [102] es realmente una meta-heurstica, porque es un procedimiento que debe acoplarse a otra tecnica, ya que no funciona por s sola.
La busqueda tabu usa una memoria para guiar la busqueda, de tal forma que
algunas soluciones examinadas recientemente son memorizadas y se vuelven
tabu (prohibidas) al tomar decisiones acerca del siguiente punto de busqueda. La
busqueda tabu es determinstica, aunque se le pueden agregar elementos probabilsticos.
El recocido simulado [142] esta basado en el enfriamiento de los cristales. El
algoritmo requiere de una temperatura inicial, una final y una funcion de variacion
34
F
F
` H P
conjunto, el segmento rectilneo que une estos puntos esta tambien dentro del
conjunto. De tal forma, los conjuntos mostrados en la figura 1.1 son convexos y
los mostrados en la figura 1.2 no lo son.
El objetivo principal de cualquier tecnica de optimizacion es encontrar el
o ptimo (o los o ptimos) globales de cualquier problema. En matematicas, existe
un a rea que se ocupa de desarrollar los formalismos que nos permitan garantizar
35
`
sujeta a:
36
Zona Factible
) de un
20L)6 H M
) B;L
estamos definiendo que el rango de una variable de decision debe estar contenido dentro de un cierto intervalo. De tal forma, estamos restringiendo el tipo
de soluciones que se consideraran como validas.
Todas las soluciones a un problema que satisfagan las restricciones existentes
(de cualquier tipo), se consideran ubicadas dentro de la zona factible. De tal
37
-,L
, 10
b) BED , 2@
c) /798;: , %798>:
d) @ /2, "F G"H
a)
x2
x1
H
B;L
pared opuesta. Las escaleras se cruzan a una altura arriba del pavimento.
Dado que las longitudes de las escaleras son
my
m, y
que
m, encontrar , que es el ancho del pasillo, usando el programa
escrito en el inciso anterior (una solucion real es suficiente). Imprima las
iteraciones efectuadas por su programa al resolver este problema.
>L
Bonificacion. El problema del inciso b) tiene mas de una solucion real. Encuentre al menos una solucion real mas (distinta de la reportada en el inciso
anterior). Adicionalmente, encuentre una solucion real que sea valida pero
que no tenga sentido reportar dada la interpretacion fsica del problema.
Discuta brevemente acerca de esto.
3. Muestre las 2 primeras iteraciones del metodo de ascenso empinado al minusando el punto inicial
.
imizar
\MBE H O
2 u B>
39
Zbigniew Michalewicz & David B. Fogel, How to Solve It: Modern Heuristics, Springer, Berlin, 2000.
1. Mencione al menos 2 razones por las cuales un problema del mundo real
puede no ser resuelto facilmente. NO USE ninguna de las razones enumeradas en la pagina 11 del captulo proporcionado.
hj_;L)6Xf)_L
Xf
Xf
b) Si puede tomar valores reales y usaremos una precision de ocho lugares decimales, cual es el tamano del espacio de busqueda del problema?
3. Defina las restricciones rgidas (hard constraints) y las restricciones flexibles (soft constraints) con sus propias palabras. Comparelas entre s.
40
Captulo 2
Un vistazo historico a la
computacion evolutiva
2.1 El origen de las ideas
Contrario a lo que muchos creen, las ideas evolucionistas que bien hiciera en
popularizar Charles Darwin en 1858 no se originaron con e l, sino que estuvieron
presentes en las mentes de una serie de cientficos y pensadores en general que
no se sentan satisfechos con la (entonces popular) idea de que haba un Dios
originador de todas las especies del planeta (las cuales haban sido creadas de
forma separada) y de que las especies estaban jerarquizadas por Dios de tal manera
que el hombre ocupaba el rango superior, al lado del Creador.
Georges Louis Leclerc (Conde de Buffon) fue tal vez el primero en especular
(100 anos antes que Darwin) en su Historie Naturelle (una impresionante enciclopedia de 44 tomos que describa todo lo que se saba en aquel entonces sobre
la naturaleza), que las especies se originaron entre s. Leclerc no solo noto las
similitudes entre el hombre y los simios, sino que incluso habla sobre un posible
ancestro comun entre estas dos especies. Leclerc crea en los cambios organicos,
pero no describio un mecanismo coherente que fuera responsable de efectuarlos,
sino que especulo que era el ambiente el que influa directamente sobre los organismos.
41
42
2.2 Lamarckismo
A partir de 1801, el zoologo frances Jean Baptiste Pierre Antoine de Monet (Caballero de Lamarck) comienza a publicar detalles de su propia teora evolutiva.
Conocedor del trabajo de Leclerc (quien era ademas su mentor), Lamarck enfatizo la importancia de la naturaleza en los cambios de las especies.
A diferencia de Leclerc, Lamarck s explico un mecanismo responsable de
los cambios en las especies, al cual ahora se le conoce como Lamarckismo. A
pesar de que el termino Lamarckismo se usa hoy en da en sentido peyorativo
para referirse a la teora de que las caractersticas adquiridas por un individuo son
hereditarias1 , la verdad es que sus ideas fueron mas complejas. Lamarck crea
que los organismos no son alterados de forma pasiva por su ambiente, tal y como
afirmaba Etienne
Geoffroy Saint-Hilaire en su Philosophie Anatomique, sino que
mas bien un cambio en el ambiente produce cambios en las necesidades de los
organismos, lo que hace que, en consecuencia, e stos cambien su comportamiento.
Estos cambios de comportamiento conducen al mayor uso (o al desuso) de ciertos o rganos o estructuras corporales de un individuo, los cuales haran que dichos
o rganos o estructuras crezcan (ante un mayor uso) o se reduzcan (ante el menor
uso) con el paso de las generaciones. Ademas, Lamarck crea que estos cambios
eran hereditarios, lo que implicaba que los organismos se van adaptando gradualmente a su ambiente.
Es interesante hacer notar que aunque el mecanismo evolutivo propuesto por
Lamarck difiere notablemente del propuesto varios anos despues por Darwin, los
resultados a los que ambas teoras conducen son los mismos: las especies sufren
cambios adaptativos debido a la influencia del ambiente a lo largo de periodos de
tiempo considerables. De hecho, llama la atencion que en su libro Philosophie
Zoologique [150], Lamarck utiliza muchas de las mismas evidencias que despues
adoptara Darwin para enunciar su famosa teora.
Sin embargo, las ideas de Lamarck no fueron muy populares en su e poca, y
solo sirvieron para desacreditarlo con sus contemporaneos, incluyendo a su mentor Leclerc. Curiosamente, varias de las ideas de Lamarck fueron re-descubiertas
(de forma independiente) por Erasmus Darwin (el abuelo de Charles Darwin) en
su libro Zoonomia, que data de 1794. Tal vez a ello se deba que Charles Darwin
haya sido uno de los pocos naturalistas en defender las ideas de Lamarck, a pesar
de que e stas se oponan a su propia teora evolutiva.
1
El ejemplo clasico usado por Lamarck era el del crecimiento del cuello y las patas frontales
de las jirafas, ante la necesidad de alcanzar las hojas mas altas de los a rboles.
43
45
46
Hoy sabemos que esta ley solo es valida para los genes localizados en cromosomas diferentes.
47
49
El termino gene fue acunado en una e poca posterior, pero los factores hereditarios o
unidades de la herencia a los que se refirio Mendel son precisamente los genes.
8
Se denominan gametos a las celulas que llevan informacion genetica de sus padres con el
proposito de llevar a cabo una reproduccion sexual. En los animales, a los gametos masculinos se
les llama espermas y a los femeninos se les llama o vulos.
50
2.10 Neo-Darwinismo
La teora evolutiva propuesta originalmente por Charles Darwin en combinacion
con el seleccionismo de August Weismann y la genetica de Gregor Mendel, se
conoce hoy en da como el paradigma Neo-Darwiniano.
El Neo-Darwinismo establece que la historia de la vasta mayora de la vida en
nuestro planeta puede ser explicada a traves de un punado de procesos estadsticos
que actuan sobre y dentro de las poblaciones y especies [124]: la reproduccion, la
mutacion, la competencia y la seleccion.
La reproduccion es una propiedad obvia de todas las formas de vida de nuestro
planeta, pues de no contar con un mecanismo de este tipo, la vida misma no tendra
forma de producirse.
En cualquier sistema que se reproduce a s mismo continuamente y que esta en
constante equilibrio, la mutacion esta garantizada [80]. El contar con una cantidad finita de espacio para albergar la vida en la Tierra garantiza la existencia de la
competencia. La seleccion se vuelve la consecuencia natural del exceso de organismos que han llenado el espacio de recursos disponibles. La evolucion es, por lo
tanto, el resultado de estos procesos estocasticos (es decir, probabilsticos) fundamentales que interactuan entre s en las poblaciones, generacion tras generacion.
51
52
2.13 EVOP
Aproximadamente en la misma e poca en que iniciara su trabajo Fraser, el experto en estadstica ingles George E. P. Box propuso un enfoque evolutivo para
la optimizacion de la produccion industrial [26]. Su tecnica, denominada EVOP
(Evolutionary Operation) consista en efectuar pequenos cambios a un conjunto
de parametros de produccion, monitoreando ciertos datos estadsticos de los procesos para guiar la busqueda. Box [26] llego a establecer claramente la analoga
10
53
entre estos cambios y las mutaciones que ocurren en la naturaleza, e hizo ver
tambien que el proceso de ajuste de parametros que efectuaba con tecnicas estadsticas era similar al proceso de seleccion natural.
EVOP funcionaba mediante un proceso iterativo, pero requera de intervencion
humana en cada etapa, si bien Box [26] reconocio que la tecnica poda automatizarse. Como Fogel indica en su libro sobre historia de la computacion evolutiva
[81], aunque en forma limitada, EVOP sigue en uso hoy en da en la industria
qumica11 .
54
bajo de Friedberg era una falla total. Minsky atribuyo el fracaso del metodo
de Friedberg a lo que e l denomino el fenomeno de mesa [166], segun el cual
el estancamiento de la poblacion se deba al hecho de que solo una instruccion
del programa era modificada a la vez, y eso no permita explorar una porcion
significativa del espacio de busqueda. Aunque estas observaciones no son del
todo precisas [81], el problema del estancamiento siguio siendo el principal inconveniente del procedimiento de Friedberg, aunque Fogel [81] considera que su
trabajo precedio el uso de los sistemas clasificadores que popularizara varios anos
despues John Holland [127].
Dunham et al. [70, 72, 71] continuaron el trabajo de Friedberg, y tuvieron
e xito con algunos problemas de aprendizaje de mayor grado de dificultad que los
intentados por e ste.
Las siglas IAS significan Institute for Advanced Studies, que es el lugar donde la computadora
se desarrollo.
15
La simbiosis es la asociacion de dos tipos diferentes de organismos en la cual cada uno se
beneficia del otro y pueden incluso ser esenciales entre s para su existencia.
16
Se denomina co-evolucion al proceso evolutivo en el cual la aptitud de un individuo se
determina mediante la evaluacion parcial de otros.
56
de estados finitos, los cuales eran expuestos a una serie de smbolos de entrada (el
ambiente), y se esperaba que, eventualmente, seran capaces de predecir las secuencias futuras de smbolos que recibiran. Fogel utilizo una funcion de pago
que indicaba que tan bueno era un cierto automata para predecir un smbolo, y uso
un operador modelado en la mutacion para efectuar cambios en las transiciones y
en los estados de los automatas que tenderan a hacerlos mas aptos para predecir
secuencias de smbolos.
Esta tecnica no consideraba el uso de un operador de recombinacion sexual
porque, como veremos en un captulo posterior, pretenda modelar el proceso evolutivo al nivel de las especies y no al nivel de los individuos.
La programacion evolutiva se aplico originalmente a problemas de prediccion,
control automatico, identificacion de sistemas y teora de juegos, entre otros [83,
86, 35].
Donald W. Dearholt y algunos otros investigadores, experimentaron con programacion evolutiva en la Universidad de Nuevo Mexico en los 1970s, de forma
totalmente independiente a Fogel [85, 81, 193, 54].
Probablemente la programacion evolutiva fue la primera tecnica basada en la
evolucion en aplicarse a problemas de prediccion, ademas de ser la primera en usar
codificaciones de longitud variable (el numero de estados de los automatas poda
variar tras efectuarse una mutacion), ademas de constituir uno de los primeros
intentos por simular la co-evolucion.
En los dos primeros casos (el tubo y la placa), Rechenberg procedio a efectuar cambios aleatorios en ciertas posiciones de las juntas y en el tercer problema
procedio a intercambiar, agregar o quitar segmentos de boquilla. Sabiendo que
en la naturaleza las mutaciones pequenas ocurren con mayor frecuencia que las
grandes, Rechenberg decidio efectuar estos cambios en base a una distribucion
binomial con una varianza prefijada. El mecanismo basico de estos primeros experimentos era crear una mutacion, ajustar las juntas o los segmentos de boquilla
de acuerdo a ella, llevar a cabo el analisis correspondiente y determinar que tan
buena era la solucion. Si e sta era mejor que su predecesora, entonces pasaba a
ser utilizada como base para el siguiente experimento. De tal forma, no se requera informacion alguna acerca de la cantidad de mejoras o deterioros que se
efectuaban.
Esta tecnica tan simple dio lugar a resultados inesperadamente buenos para
los tres problemas en cuestion, y Peter Bienert [23] construyo un robot que poda
efectuar de forma automaticamente el proceso de optimizacion usando este metodo.
Simultaneamente, Hans-Paul Schwefel se dio a la tarea de implementar esta tecnica
en una computadora Z23 [202].
Aunque los primeros fundamentos teoricos de las estrategias evolutivas de
dos miembros (su version mas simple) se esbozaron en la tesis doctoral de Ingo
Rechenberg la cual se publico como libro en 1973 [184], no fue sino hasta que el
libro que Schwefel escribiera a fines de los 1970s [203] se tradujo al ingles [204]
que la tecnica atrajo la atencion de los investigadores fuera del mundo germanoparlante.
59
Se denomina genoma a la coleccion completa de genes (y por tanto cromosomas) que posee
un organismo.
61
tamiento que caracteriza a los procesos de sucesion ecologica deben emerger potencialmente, (b) los procesos de la busqueda evolutiva deben corresponder con
su contraparte biologica, y (c) la simulacion debe ser lo mas simple posible a
fin de permitir el estudio de caractersticas fundamentales de los ecosistemas as
como las condiciones mnimas necesarias para que ocurra la evolucion natural.
Sus esfuerzos en esta a rea se extendieron hasta los 1980s [48, 49, 53, 189, 52].
Michael Conrad [47] propuso tambien en los 1970s un modelo de circuitos
de aprendizaje evolutivo en el cual especulo sobre la posibilidad de que el cerebro use el mismo tipo de mecanismos que usa la evolucion para aprender. Su
tecnica fue uno de los primeros intentos por utilizar algoritmos evolutivos para
entrenar redes neuronales. Conrad tambien sugirio [50] el uso de la evolucion
para lidiar con problemas como el reconocimiento de patrones en que los enfoques algortmicos de alto nivel (como los sistemas expertos) no han proporcionado
resultados satisfactorios.
Herencia
Desvo genetico
Mutacion
Recombinacion
Aislamiento
66
Captulo 3
Principales Paradigmas
3.1 Introduccio n
El termino computacion evolutiva o algoritmos evolutivos, realmente engloba
una serie de tecnicas inspiradas biologicamente (en los principios de la teora
Neo-Darwiniana de la evolucion natural). En terminos generales, para simular el
proceso evolutivo en una computadora se requiere:
Aunque hoy en da es cada vez mas difcil distinguir las diferencias entre
los distintos tipos de algoritmos evolutivos existentes, por razones sobre todo
historicas, suele hablarse de tres paradigmas principales:
Programacion Evolutiva
Estrategias Evolutivas
Algoritmos Geneticos
Cada uno de estos paradigmas se origino de manera independiente y con motivaciones muy distintas. Aunque este curso se concentrara principalmente en el
tercero (los algoritmos geneticos), revisaremos rapidamente, y de manera muy
general, los otros dos paradigmas en este captulo.
67
Figura 3.1: Portada de la edicion reciente (1999) del libro Artificial Intelligence
through Simulated Evolution, con el cual se originara la programacion evolutiva.
Se aplica mutacion.
Se calcula la aptitud de cada hijo y se usa un proceso de seleccion mediante torneo (normalmente estocastico) para determinar cuales seran las
soluciones que se retendran.
0/c
B
0/b
1/a
0/b
1/b
1/c
B
1
C
a
C A
1 1
A A
c b
A
0
B
b
B
1
C
a
3.1.2 Aplicaciones
Algunas aplicaciones de la programacion evolutiva son [80]:
Prediccion
Generalizacion
Juegos
69
Control automatico
Planeacion de rutas
X p H X X
x L u
donde:
H pp H
sCL
H XH s
CL
h2>LsL2L;
u 2>2>L>L>%%i
i2sL_>]2>_>
u
Padre
Hijo
m
3.1.3.3 Convergencia
Rechenberg [184] formulo una regla para ajustar la desviacion estandar de forma
determinstica durante el proceso evolutivo de tal manera que el procedimiento
convergiera hacia el o ptimo.
Esta regla se conoce como la regla del e xito 1/5, y en palabras dice:
71
2(~;_
t ^
4^2(~;_
t ]
t 2(~;_
donde es el numero de dimensiones, es la generacion, es la frecuencia
relativa de mutaciones exitosas medida sobre intervalos de (por ejemplo) 2L; individuos, y #lkL2( (este valor fue derivado teoricamente por Schwefel [204]).
[ se aujsta cada mutaciones.
Thomas Back [9] derivo una regla de e xito 1/7 para las ( , m )-EEs.
si
si
si
3.1.3.4 Auto-Adaptacion
En las estrategias evolutivas se evoluciona no solo a las variables del problema,
sino tambien a los parametros mismos de la tecnica (es decir, las desviaciones
estandar). A esto se le llama auto-adaptacion).
Los padres se mutan usando las siguientes formulas:
u
u
bcbosCL u b"
72
Las estrategias evolutivas simulan el proceso evolutivo al nivel de los individuos, por lo que la recombinacion es posible. Asimismo, usan normalmente
seleccion determinstica.
3.1.3.5 Estrategias Evolutivas vs Programacio n Evolutiva
La Programacion Evolutiva usa normalmente seleccion estocastica, mientras que
las estrategias evolutivas usan seleccion determinstica.
Ambas tecnicas operan a nivel fenotpico (es decir, no requieren codificacion
de las variables del problema).
La programacion evolutiva es una abstraccion de la evolucion al nivel de las
especies, por lo que no se requiere el uso de un operador de recombinacion (diferentes especies no se pueden cruzar entre s). En contraste, las estrategias evolutivas son una abstraccion de la evolucion al nivel de un individuo, por lo que la
recombinacion es posible.
3.1.3.6 Aplicaciones
Algunas aplicaciones de las estrategias evolutivas son [204]:
Bioqumica
Optica
Diseno en ingeniera
Magnetismo
73
Figura 3.4: Portada de una edicion reciente (publicada por el MIT Press) del libro en el que Holland diera a conocer originalmente los algoritmos geneticos (en
1975).
Cadena 1
Cadena 2
Cadena 3
Cadena 4
Figura 3.5: Ejemplo de la codificacion (mediante cadenas binarias) usada tradicionalmente con los algoritmos geneticos.
A la cadena binaria se le llama cromosoma. A cada posicion de la cadena
se le denomina gene y al valor dentro de esta posicion se le llama alelo.
Para poder aplicar el algoritmo genetico se requiere de los 5 componentes
basicos siguientes:
Una forma de crear una poblacion inicial de posibles soluciones (normalmente un proceso aleatorio).
Operadores geneticos que alteren la composicion de los hijos que se produciran para las siguientes generaciones.
Valores para los diferentes parametros que utiliza el algoritmo genetico
(tamano de la poblacion, probabilidad de cruza, probabilidad de mutacion,
numero maximo de generaciones, etc.)
Figura 3.6: Portada del libro de David E. Goldberg sobre algoritmos geneticos. A
este importante libro se debe, en gran medida, el e xito (cada vez mayor) de que
han gozado los algoritmos geneticos desde principios de los 1990s.
Los AGs no son, normalmente, auto-adaptativos, aunque el uso de dicho mecanismo es posible, y ha sido explorado extensivamente en la literatura especializada
(ver por ejemplo: [6, 63, 201]).
Puede verse una comparacion mas detallada de los tres paradigmas anteriores
en la tabla 3.1.
3.1.4.3 Aplicaciones
Algunas aplicaciones de los AGs son las siguientes [105]:
76
Tabla 3.1: Tabla comparativa de los tres paradigmas principales que conforman la
computacion evolutiva [9].
Estrategias
Evolutivas
Programacion
Evolutiva
Algoritmo
Genetico
Representacion
Funcion
de Aptitud
Auto-Adaptacion
Real
Valor de la funcion
objetivo
Desviaciones Estandar
y a ngulos de rotacion
Binaria
Valor de la funcio n
objetivo ajustada
Ninguna
Mutacion
Gausiana,
operador principal
Discreta e intermedia,
sexual y panmtica,
importante para la
auto-adaptacion
Determinstica,
extintiva o basada
en la preservacion
Restricciones
arbitrarias de
desigualdad
Real
Valor de la funcion
objetivo ajustada
Ninguna
Varianzas (PE-estandar),
Coeficientes de
correlacion (meta-PE)
Gausiana,
operador u nico
Ninguna
Recombinacion
Seleccion
Restricciones
Teora
Probabilstica,
extintiva
Ninguna
Velocidad de
Convergencia para
casos especiales,
(1+1)-ES, (1+ )-ES,
Convergencia global
Velocidad de
Convergencia para
casos especiales,
(1+1)-PE,
Convergencia global
para (
para meta-PE
eym
)-ES
77
Inversion de bits,
operador secundario
Cruza de 2-puntos,
cruza uniforme,
u nicamente sexual,
operador principal
Probabilstica,
basada en la
preservacion
Lmites simples
mediante el
mecanismo de
codificacion
Teora de los
Esquemas,
Convergencia global
para la version
elitista
Las tecnicas evolutivas no necesitan conocimiento especfico sobre el problema que intentan resolver.
Simplicidad Conceptual.
Amplia aplicabilidad.
Figura 3.7: Portada del libro de John Koza sobre programacion genetica. Este
libro marco el inicio de una nueva a rea dentro de la computacion evolutiva, dedicada principalmente a la solucion de problemas de regresion simbolica.
2(hO
v
)
tf S
32
t = t+1
if (t mod n == 0) then
S hUT[~#
S T S hO#ATX(#
S hUT
S
S
else T h62T
if
if
if
2(~>_
t M
4 2(~>_
M
t k
t (2 ~>_
Algunos puntos importantes que deben observarse en este programa son los
siguientes:
El valor de la constante
suelen establecerlo en
Cuidar que los valores de las variables no se salgan del rango especificado.
(3.1)
82
Captulo 4
Terminologa Biologica y de
Computacion Evolutiva
4.1 Introduccio n
El Acido Desoxirribonucleico (ADN) es el material genetico fundamental de todos los organismos vivos. El ADN es una macro-molecula doblemente trenzada
que tiene una estructura helicoidal como se ilustra en la Figura 4.1. Ambos filamentos trenzados son moleculas de a cido nucleico lineales y sin ramificaciones,
formadas de moleculas alternadas de desoxirribosa (azucar) y fosfato. El ADN de
un organismo puede contener desde una docena de genes (como un virus), hasta
decenas de miles (como los humanos).
Las 4 bases de nucleotido (ver figura 4.2): Adenina (A), Timina (T), Citosina
(C) y Guanina (G) son el alfabeto de informacion genetica. Las secuencias de
estas bases en la molecula de ADN determinan el plan constructor de cualquier
organismo.
Caso Haploide: Se intercambian los genes entre los cromosomas (haploides) de los dos padres.
Caso Diploide: En cada padre, se intercambian los genes entre cada par de
cromosomas para formar un gameto, y posteriormente los gametos de los 2
85
86
de formar la hemoglobina. Al fallar, se afecta la circulacion sangunea, las funciones del hgado y las acciones capilares.
Cuando una sola caracterstica fenotpica de un individuo puede ser determinada mediante la interaccion simultanea de varios genes, se denomina al efecto:
poligenia. El color del cabello y de la piel son generalmente rasgos poligenicos.
Aunque no existe una definicion universalmente aceptada de especie, diremos
que es una coleccion de criaturas vivientes que tienen caractersticas similares, y
que se pueden reproducir entre s. Los miembros de una especie ocupan el mismo
nicho ecologico.
Se denomina especiacion al proceso mediante el cual aparece una especie. La
causa mas comun de especiacion es el aislamiento geografico.
Si una subpoblacion de una cierta especie se separa geograficamente de la
poblacion principal durante un tiempo suficientemente largo, sus genes divergiran.
Estas divergencias se deben a diferencias en la presion de seleccion en diferentes
lugares, o al fenomeno conocido como desvo genetico.
Se llama desvo genetico a los cambios en las frecuencias de genes/alelos en
una poblacion con el paso de muchas generaciones, como resultado del azar en
vez de la seleccion. El desvo genetico ocurre mas rapidamente en poblaciones
pequenas y su mayor peligro es que puede conducir a que algunos alelos se extingan, reduciendo en consecuencia la variabilidad de la poblacion.
En los ecosistemas naturales, hay muchas formas diferentes en las que los
animales pueden sobrevivir (en los a rboles, de la cacera, en la tierra, etc.) y cada
estrategia de supervivencia es llamada un nicho ecologico.
Dos especies que ocupan nichos diferentes (p.ej. una que se alimenta de plantas y otra que se alimenta de insectos) pueden coexistir entre ellas sin competir,
de una manera estable.
Sin embargo, si dos especies que ocupan el mismo nicho se llevan a la misma
zona, habra competencia, y a la larga, la especie mas debil se extinguira (localmente).
Por lo tanto, la diversidad de las especies depende de que ocupen una diversidad de nichos (o de que esten separadas geograficamente).
Se denomina reproduccion a la creacion de un nuevo individuo a partir de:
Filogenetica
Ontogenetica
Sociogenetica
genotipo
fenotipo
decodificacin
90
Individuo
Figura 4.11: Un ejemplo de un individuo.
alelo
320L20L 2L>L
Cadena original:
Puntos de inversin:
Cadena resultante:
Cruza
Mutacion
Reordenamiento
94
Captulo 5
La Importancia de la
Representacion
5.1 Introduccio n
Las capacidades para procesamiento de datos de las tecnicas de computacion evolutiva dentro de una amplia gama de dominios han sido reconocidas en los u ltimos
anos y han recibido mucha atencion por parte de cientficos que trabajan en diversas disciplinas. Dentro de estas tecnicas evolutivas, quizas la mas popular sea el
algoritmo genetico (AG) [105]. Siendo una tecnica heurstica estocastica, el algoritmo genetico no necesita informacion especfica para guiar la busqueda. Su
estructura presenta analogas con la teora biologica de la evolucion, y se basa en
el principio de la supervivencia del mas apto [127]. Por lo tanto, el AG puede
verse como una caja negra que puede conectarse a cualquier aplicacion en particular. En general, se necesitan los cinco componentes basicos siguientes para
implementar un AG que resuelva un problema cualquiera [159]:
1. Una representacion de soluciones potenciales al problema.
2. Una forma de crear una poblacion inicial de soluciones potenciales (esto
se efectua normalmente de manera aleatoria, pero tambien pueden usarse
metodos determinsticos).
3. Una funcion de evaluacion que juega el papel del ambiente, calificando a
las soluciones producidas en terminos de su aptitud.
95
Hvu u u <
Hvu u u
B G$
2L;
G$
2;2
#j20"
Un cromosoma es una estructura de datos que contiene una cadena de parametros de diseno
o genes.
2
La razon por la que se suma uno a la cardinalidad es porque en los esquemas se usa un smbolo
adicional (normalmente el asterisco o el smbolo de numero) para indicar que no nos importa el
valor de esa posicion.
96
Se denomina gene o gen a cualquier posicion a lo largo de una cadena que representa a un
individuo.
97
98
Signo
0
1 bit
Exponente
Mantisa
10001011 0100...0
8 bits
23 bits
=>E>.6>>
99
rX * 3
Gradualidad se refiere a los casos en los cuales un cambio pequeno en las variables se
100
101
145679
67893
37568
95432
Figura 5.5: Otra representacion entera de numeros reales. En este caso, cada gene
contiene un numero real representado como un entero largo.
improbable, ya que se tendran que hacer sacrificios notables en la representacion,
y los u nicos ahorros importantes que se lograran seran en terminos de memoria
(el almacenamiento de enteros toma menos memoria que el de numeros reales).
No obstante, este esquema ha sido usado en algunas aplicaciones del mundo real
[64].
(2 , 1) (2 , 0) (3 , 0) (3 , 1)
(1 , 1) (1 , 0) (1 , 1) (4 , 1) (4 , 0)
(2, 0)
(2 , 1) (3 , 1) (1 , 0) (4 , 1)
(1 , 1) (1 , 0) (4 , 1) (3 , 1) (3 , 0) (2 , 1) (4 , 0)
(2, 0)
(2 , 1) (2 , 1) (4 , 0)
(1 , 1) (1 , 0) (4 , 1) (3 , 1) (3 , 0) (3 , 1) (1 , 0) (4 , 1)
Figura 5.8: Un ejemplo del operador union en un AG desordenado. La lnea
gruesa muestra la parte de la cadena que fue agregada.
OR
AND
AND
NOT
NOT
A0
A1
A1
A0
0>
106
OR
AND
NOT
A1
A0
A1
OR
6
OR
A1
AND
NOT
A0
NOT
NOT
A0
A1
10
Figura 5.10: Los nodos del a rbol se numeran antes de aplicar el operador de cruza.
OR
OR
AND
AND
NOT
NOT
A0
A1
A0
NOT
OR
A1
A1
NOT
A1
A0
107
OR
OR
5
AND
AND
A0
A0
A1
A0
NOT
A1
A1
!
"$#!%&'
108
+
7
01!2&)'+
(*)'+,-/.'+
B
>@?BA476
(E0)
35476'8:9<;=6
B
109
c1
c11
c12
c2
c13
c 21
c 22
c3
c 23
c31
c32
nivel 1
c33
nivel 2
( c 1 c 2 c3
end
c1
c11
c111 c112 c113
c3 . . . c n
c2
c 12
c121 c122 c123
c13
c131 c132 c 133
c 21
c 22
c 23
su gene de mas bajo nivel y cuando es pasivo (apagado), apunta al gene del mismo
nivel en que se encuentre [60].
tambien saber mas acerca de las representaciones (distintas a la binaria tradicional) que actualmente existen, pues su uso adecuado puede ahorrar mucho trabajo innecesario y permitirnos concentrarnos en la aplicacion misma del algoritmo genetico a nuestro problema en vez de canalizar todas nuestras energas en
el diseno de operadores geneticos especiales.
de una Buena
5.9 Recomendaciones para el Dise no
Representacio n
Palmer [175] analizo las propiedades de las representaciones de a rbol y proporciono una serie de recomendaciones que pueden generalizarse a cualquier otro tipo
de representacion. Los puntos clave de la propuesta de Palmer son los siguientes:
C
C
Una codificacion debe ser capaz de representar todos los fenotipos posibles.
Una codificacion debe ser carente de sesgos en el sentido de que todos los
individuos deben estar igualmente representados en el conjunto de todos los
genotipos posibles.
Una codificacion no debiera codificar soluciones infactibles (esto no es normalmente posible en la mayora de los dominios).
C
C
Notese, sin embargo, que existe evidencia reciente que contradice el u ltimo
punto de los lineamientos de Ronald, pues las representaciones redundantes parecen mejorar el desempeno de un algoritmo evolutivo [194].
DFEHG IG!J+
0>
a) Cual es la longitud mnima de la cadena cromosomica que puede codificar a estas 3 variables?
b) Cual es el tamano intrnseco del espacio de busqueda para un AG que
se usara con estas cadenas cromosomicas.
c) Cual es la cantidad de esquemas que esta representacion codifica?
d) Muestre las cadenas cromosomicas que representen los siguientes puntos:
(-8.1,50,0.0), (11.1, 98, -0.2).
2. Resuelva el problema anterior usando representacion entera de punto fijo.
3. Investigue la representacion de permutaciones. Discuta por que se considera mas adecuada para problemas como el del viajero. Que problemas presenta una representacion binaria en este dominio? Que operadores deben
definirse en una representacion de permutaciones?
114
Captulo 6
Tecnicas de Seleccion
Una parte fundamental del funcionamiento de un algoritmo genetico es, sin lugar
a dudas, el proceso de seleccion de candidatos a reproducirse. En el algoritmo
genetico este proceso de seleccion suele realizarse de forma probabilstica (es
decir, aun los individuos menos aptos tienen una cierta oportunidad de sobrevivir),
a diferencia de las estrategias evolutivas, en las que la seleccion es extintiva (los
menos aptos tienen cero probabilidades de sobrevivir).
Las tecnicas de seleccion usadas en algoritmos geneticos pueden clasificarse
en tres grandes grupos:
C
C
Seleccion proporcional
3. Universal Estocastica
4. Muestreo Determinstico
Adicionalmente, las tecnicas de seleccion proporcional pueden tener los siguientes aditamentos:
1. Escalamiento Sigma
2. Jerarquas
3. Seleccion de Boltzmann
6.1.1 La Ruleta
Esta tecnica fue propuesta por DeJong [137], y ha sido el metodo mas comunmente
usado desde los orgenes de los algoritmos geneticos. El algoritmo es simple, pero
. Asimismo, presenta el problema de que el
ineficiente (su complejidad es
individuo menos apto puede ser seleccionado mas de una vez. Sin embargo, buena
parte de su popularidad se debe no solo a su simplicidad, sino al hecho de que su
implementacion se incluye en el libro clasico sobre AGs de David Goldberg [105].
K1ML
C
C
veces (
es el tamano de la poblacion):
(1)
(2)
aptitud
25
81
Ve
0.35
1.13
116
(3)
(4)
36
144
0.51
2.01
Q R T STU Q R WV>
X
D R Z[Y R V
\^]_ Ra`c` d b
N R Suma de Ve
PfehgiVjGkNml
Generar PnehgjViGWVol
r = 1.3
(ind1) suma =
(ind2) suma =
jV+npqP
V$SfrqP
Seleccionar a ind2
\s]
En este ejemplo,
se refiere al valor esperado (o numero esperado de copias
que se esperan obtener) de un individuo.
6.1.1.1 Analisis de la Ruleta
\s]
Complejidad:
de la poblacion).
(tamano
KtL
K1tL=>:L!
\suwvM]*xzy
117
\suwvM]*xzyW_ R `c` d b
La idea principal es asignar determinsticamente las partes enteras de los valores esperados para cada individuo y luego usar otro esquema (proporcional) para
la parte fraccionaria.
El sobrante estocastico reduce los problemas de la ruleta, pero puede causar
convergencia prematura al introducir una mayor presion de seleccion.
El algoritmo es el siguiente:
1. Asignar de manera determinstica el conteo de valores esperados a cada
individuo (valores enteros).
2. Los valores restantes (sobrantes del redondeo) se usan probabilsticamente
para rellenar la poblacion.
Hay 2 variantes principales:
C
C
Sin reemplazo: Cada sobrante se usa para sesgar el tiro de una moneda que
determina si una cadena se selecciona de nuevo o no.
Con reemplazo: Los sobrantes se usan para dimensionar los segmentos de
una ruleta y se usa esta tecnica de manera tradicional.
Veamos un ejemplo:
(1)
(2)
(3)
(4)
Cadena
aptitud
]_
110100
011010
111001
001101
220
140
315
42
1.23
0.78
1.76
0.23
Padres:
1 y 3 (partes enteras)
Q R ( Q R WV;
D X R 0T{jV>
Sin reemplazo:
118
enteros
dif
1
0
1
0
0.23
0.78
0.76
0.23
Q R
flip(0.23)
flip(0.78)
..
.
flip(0.23)
ind 1
ind 2
ind 4
(1)
(2)
(3)
(4)
]_
0.23
0.78
0.76
0.23
Q R V
% del total
0.12
0.39
0.38
0.11
(12%)
(39%)
(38%)
(11%)
Q R V>
K tL
K1ML
ptr=Rand();
p R L
\suwvM]*x/yot}zGk~
for(sum=0,i=1;i
;i++)
for(sum+=
;sum ptr;ptr++)
Seleccionar(i);
Ejemplo:
(1)
(2)
(3)
(4)
i=1
aptitud
220
140
315
42
ptr=0.4
sum=0.0
inicializacion
Q R WV;
r
p
sum=1.23
ptr=1.4
sum=2.01
2.01 ptr
Seleccionar (2)
ptr=2.4
sum=2.01
i=3
1.23
0.78
1.76
0.23
sum=1.23
1.23 ptr
Seleccionar (1)
ptr=1.4
sum=1.23
i=2
]_
Cadena
110100
011010
111001
001101
sum=3.77
3.77 ptr
Seleccionar (3)
ptr=3.4
sum=3.77
3.77 ptr
Seleccionar (3)
120
KtL .
Problemas:
C
C
=F R `cb `
C Calcular \uwvM]*xzyW_ R =MWL (L =tamano de la poblacion)
C Asignar determinsticamente la parte entera de \uwvM]*xzy_ .
C Ordenar la poblacion de acuerdo a las partes decimales (de mayor a menor).
C Obtener los padres faltantes de la parte superior de la lista.
C
Calcular
Ejemplo:
(1)
(2)
(3)
(4)
aptitud
:M
]_
enteros
220
140
315
42
0.3068
0.1953
0.4393
0.0586
1.23
0.78
1.76
0.23
1
0
1
0
121
ordenar
fracciones
0.78 (2)
0.76 (3)
0.23 (1)
0.23 (4)
Q R (
Q R TV>; Q R WV> Q R
Seleccionar: 1 y 3 (enteros)
Seleccionar: 2 y 3 (fracciones)
6.1.4.1 Analisis del muestreo determinstico
Complejidad: El algoritmo es
para la ordenacion.
KtL
KtL=>L
` _ `d si M~R
Z
\suwvM]*x/yot}zGk~
R
si M~
V
Q DM~ Q D F~"
L
M~
L
= tamano de la poblacion
Si
\^u vM]*xzyM}zGz~p6
Ejemplo:
(1)
(2)
(3)
(4)
aptitud
220
140
315
42
puede hacerse
D_F~
\uwvt]*xzyM}zGz~ R iV=
\su vM]*xzy
48,400
19,600
99,225
1,764
1.20
0.81
1.67
0.32
122
(6.1)
(6.2)
Q R (
Q R UTSjG!{S{ Q R WV>
D X Q R 0T {jVR >
n=4
D_ WGATS{
[
[
R ZYz ZYZ " ZYZ R 0>jVTS0
`cb ` d
R
1+ Z
Observacion: Bajo un poco el valor esperado del mejor individuo y subio el del
peor.
6.1.5.1 Analisis del escalamiento sigma
El escalamiento sigma produce el siguiente comportamiento en la seleccion:
C
C
123
(donde
Elegir
u$Ec3su$E;
C Calcular }L R juE
Ejemplo:
(1)
(2)
(3)
(4)
(5)
jerarquas
2
5
1
4
3
\uwvt]*xzy
0.95
1.10
0.90
1.05
1.00
Aplicar ruleta
u otra tecnica
proporcional
Q R i V>
uE R V= }cL R l6V R jV{
O R
s\ uwvM]*xzy R jV{mMCjV> ZZcX b X
KtLBvt L
+ tiempo de seleccion.
Complejidad:
Algunos puntos interesantes respecto a la aplicabilidad de esta tecnica:
C
C
Es u til cuando la funcion tiene ruido (p.ej., cuando hay una variable aleatoria).
b
R
]
(6.3)
Valesp(i,t)
]b
generacion t.
Veamos un ejemplo de su uso:
Ejemplo:
aptitud
220
140
315
42
Q R (
b
]
9.025
4.055
23.336
1.522
\su vM]*xzy
0.952
0.428
2.460
0.160
Q R + V{>TS Q R W V>>
R k [ Y R {iV$S*
NC+ R R >>>>
NM~ NM ~c
(7<jV
(bajo)
(bajo)
(subio)
(bajo)
~R
N + R 0;>>><jV <jV j V R 0;
Supongamos:
125
C
C
C
C
Determinstica
Probabilstica
C
C
Aptitud
254
47
457
194
85
310
Barajar
(2)
(6)
(1)
(3)
(5)
(4)
Barajar
(4)
(1)
(6)
(5)
(2)
(3)
Ganadores
Ganadores
(6)
(3)
(4)
(1)
(6)
(3)
Padres:
(6) y (1), (3) y (6), (4) y (3)
Otra forma:
P R PLCiG(
Selecciona
Selecciona
/*aleatorio real*/
?~
~
~?
~
R R
R PP R Ct U++
R R
R PP R *(
Ganador
(3)
(1)
127
padres
Y as sucesivamente.
El algoritmo de la version probabilstica es identico al anterior, excepto por el
paso en que se escoge al ganador. En vez de seleccionar siempre al individuo con
1
y si el resultado es cierto, se selecciona al mas
aptitud mas alta, se aplica
apto. De lo contrario, se selecciona al menos apto.
El valor de permanece fijo a lo largo de todo el proceso evolutivo y se escoge
en el siguiente rango:
DBvF}yoy
jVnpyJ
R , la tecnica se reduce a la version determinstica.
Observe que si y
R jV )
Ejemplo: (y
(1)
(2)
(3)
(4)
(5)
(6)
Aptitud
254
47
457
194
85
310
Barajar
(2)
(6)
(1)
(3)
(5)
(4)
DBvF}yy
DBvF}yy
DBvF}yy
R N s elige (6)
R elige (1)
R Ns elige (4)
Esta variante reduce un poco la presion de seleccion, permitiendo que en algunas cuantas ocasiones el individuo menos apto gane el torneo.
C
C
K(
KtL .
Puede introducir una presion de seleccion muy alta (en la version determinstica) porque a los individuos menos aptos no se les da oportunidad de
sobrevivir.
Tiene sentido aplicar jerarquas lineales a la seleccion mediante torneo?
No, porque la seleccion mediante torneo realiza comparaciones directas entre individuos. El uso de jerarquas lineales no cambiara en nada la presion
de seleccion.
C
C
Si se usa tam torneo=1, se produce una caminata aleatoria con una presion
de seleccion muy baja.
En general, la tecnica resulta u til cuando los miembros de la poblacion resuelven colectivamente (y no de manera individual) un problema.
Asimismo, los AGs generacionales se usan cuando es importante recordar
lo que se ha aprendido antes.
El algoritmo de la seleccion de estado uniforme es el siguiente:
C
C
Llamaremos
Seleccionar
plo,
.
Reemplazar los
.
. (o a los
peores individuos de
mejores).
por los
mejores individuos de
C
C
K1MLvM* L!
Los AGs no generacionales no son muy comunes en aplicaciones de optimizacion, aunque s pueden utilizarse.
C
C
Disruptiva
Jerarquas no lineales
Competitiva
Suele usarse:
donde
X
DM~
R *D _3FE DX M ~
DI_ ME
`/
\suwvM]*xzyW_ R ` d b
X
D ME son los valores normalizados.
Ejemplo:
Aptitud
220
140
315
42
Normalizacion ( )
40.75
39.25
135.75
137.25
Valesp
0.462
0.445
1.538
1.555
Q R (
Q R +;
Q R WV>>
DX F~ R [ R 0T{jV> , DIX [M~ R [ R SSjV>
\uwvM]*xzy R ` d `
extremos
mas aptos
R 3 t Zc b X
PT/_
donde:
PT/_
h
de presion de seleccion.
]e PTu$gP jo VV 7 l u es_ esellafactor
jerarqua del individuo } en estudio.
Al igual que con las jerarquas lineales, se asigna la jerarqua mas baja al peor
individuo y la mas alta al mejor.
Una vez que se conocen las probabilidades de que un individuo sea seleccionado, obtenemos
multiplicando por .
Veamos un ejemplo:
\suwvM]*xzy
aptitud
12
245
9
194
48
^Po'tccM
jerarqua
2
5
1
4
3
0.210
0.072
0.300
0.103
0.147
\su vM]*xzy
1.05
0.36
1.50
0.52
0.74
Q R i VS>>
Q R WV (
R jV
Supongamos:
Poo/_ R jVX3 OjV> tZZc b X
\^uwvt]*xzy R PT/_WL
L R
(mayor)
(menor)
(mayor)
(menor)
(menor)
133
PT/_ R 3 Z b X
R
Z
= tamano de la poblacion
donde:
Ejemplo:
aptitud
12
245
9
194
48
jerarqua
2
5
1
4
3
:tccM
0.2524
0.0865
0.3606
0.1238
0.1767
\su vM]*xzy
1.2620
0.4325
1.8030
0.6190
0.8835
Q R V;> Q R iV>>
^R jV
Usando de nuevo:
R
@R R V;+;+E*;{
z
(mayor)
(menor)
(mayor)
(menor)
(menor)
Cabe mencionar que se han usado tambien otras variantes de las jerarquas
no lineales. Por ejemplo, Whitley & Kauth [226] propusieron el uso de una distribucion geometrica de acuerdo a la cual la probabilidad de que un individuo
sea seleccionado esta dada por:
ueqgjVV='l
P_
yW_ R u3hu Z b
(6.4)
donde
es un parametro definido por el usuario, es el tamano de la
poblacion y es la jerarqua del individuo (definida de tal forma que el menos
apto tiene una jerarqua de 1 y el mas apto tiene una jerarqua de ). Si el individuo
es el mejor en la poblacion, entonces
, con lo que se hara . Por lo
tanto, es realmente la probabilidad de que seleccionar al mejor individuo en la
poblacion [69].
P_ R L
134
y_
cision de seis cifras despues del punto decimal. Lo que debe entregarse es
lo siguiente:
Estime el tamano intrnseco del espacio de busqueda para este problema. Es decir, dada la longitud de la cadena binaria que representa
los valores posibles de , estime cuantas posibles soluciones pueden
generarse. Dada una corrida promedio de las realizadas (con los parametros
que Ud. guste), indique que porcentaje aproximado del espacio de
busqueda ha explorado el AG para encontrar la solucion.
Una corrida con parametros mminos (una poblacion de solo 6 individuos, corriendo solo 2 generaciones), a fin de ilustrar que la cruza,
mutacion y seleccion se efectuaron correctamente. En la corrida se
mostraran las cadenas binarias correspondientes a cada individuo, as
como sus valores decodificados (es decir, el valor de en cada caso),
sus valores de aptitud, los puntos de cruza elegidos, los padres y los
hijos producidos en cada caso, y los efectos producidos por la mutacion (usar un porcentaje relativamente alto a fin de que se produzca
mutacion con una poblacion pequena). Asimismo, se debera ilustrar
el proceso de seleccion paso por paso, indicando los valores esperados
para cada individuo, la aptitud promedio de la poblacion y el numero
de copias de cada individuo tras el proceso de seleccion.
Una corrida de ejemplo (salida generada por el programa), y los resultados promediados de AL MENOS 20 corridas independientes en
las que se usen los mismos parametros (porcentaje de cruza y mutacion, tamano de la poblacion y maximo numero de generaciones)
pero diferente semilla para generar numeros aleatorios. En el reporte
debera aparecer la mejor solucion obtenida, la media de aptitud, la
peor solucion obtenida y la desviacion estandar de las 20 corridas
en cada caso.
efectuadas. Debera mostrarse el valor de y de
Asimismo, se incluira la grafica de convergencia correspondiente a la
solucion que este en la mediana de los resultados obtenidos (de las 20
corridas). En esta grafica se mostrara en el eje de las el numero de
generaciones (de cero al maximo permisible) y en el eje de las se
mostrara la aptitud promedio de cada generacion.
DFE
DFE R E
137
R
G (6.6)
G
u
_
donde D FE GzE
Q
*oa z D X FE GzE
_
R
;>iG R G y:
(6.7)
donde: U>iVUfE_=U+ V;TUjG
U +
gu_ l R ++ .j+U + U + +j > +U ..UU
+ + +
(6.8)
C
C
C
C
Muestreo determinstico.
138
C
C
E E DFE
Una comparacion de resultados entre las dos implementaciones. Usando los resultados producidos en el punto anterior, se debera analizar
lo que ocurrio en cada caso y concluir si la representacion hizo alguna diferencia en el desempeno del algoritmo genetico (por ejemplo,
si acelero la convergencia hacia el o ptimo, si ayudo a encontrar una
mejor solucion, etc.).
140
Captulo 7
Tecnicas de Cruza
7.1 Introduccio n
En los sistemas biologicos, la cruza es un proceso complejo que ocurre entre parejas de cromosomas. Estos cromosomas se alinean, luego se fraccionan en ciertas
partes y posteriormente intercambian fragmentos entre s.
En computacion evolutiva se simula la cruza intercambiando segmentos de
cadenas lineales de longitud fija (los cromosomas).
Aunque las tecnicas de cruza basicas suelen aplicarse a la representacion binaria, e stas son generalizables a alfabetos de cardinalidad mayor, si bien en algunos
casos requieren de ciertas modificaciones.
Comenzaremos por revisar las tres tecnicas basicas de cruza:
C
C
Cruza de un punto
Punto de cruza
Punto de cruza
1 0 1 0 1 1 0 1
1 1 1 0 1 1 1 0
1 0 1 0 1 1 1 0
1 1 1 0 1 1 0 1
Descendientes
O(*11*0*0*) = 4
O(****1***) = 1
Ejemplo:
> 5 ; R R l
R
jm$;
DeJong [137] fue el primero en implementar una cruza de puntos, como una
generalizacion de la cruza de un punto.
El valor
es el que minimiza los efectos disruptivos (o destructivos) de
la cruza y de ah que sea usado con gran frecuencia.
No existe consenso en torno al uso de valores para que sean mayores o
iguales a 3.
Los estudios empricos al respecto [137, 74] proporcionan resultados que no
resultan concluyentes respecto a las ventajas o desventajas de usar dichos valores.
En general, sin embargo, es aceptado que la cruza de dos puntos es mejor que
la cruza de un punto.
Asimismo, el incrementar el valor de se asocia con un mayor efecto disruptivo de la cruza.
L R
143
Puntos de Cruza
Puntos de Cruza
1 0 1 1 0 1 0 1
1 1 1 0 1 1 1 0
1 0 1 0 1 1 0 1
1 1 1 1 0 1 1 0
Descendientes
Padre 1
1
Padre 2
1
Padre 1
1
Hijo 1
Padre 2
Hijo 2
144
R jV
R iV
Copiar los bits de cada padre hacia sus hijos, de uno en uno.
En el momento en que se encuentra un signo de admiracion en cualquiera
de los padres, se efectua la cruza (es decir, se invierte la procedencia de los
bits en los hijos).
145
Cromosoma:
0
cadena original
puntos de cruza
L=10
L=10
Cuando esto ocurre, los signos de admiracion se copian tambien a los hijos,
justo antes de que la cruza se efectue.
=
=
a a
c c
a
c
a
c!
a
d
a a! b b b
d d d d d!
a
c!
d d
a a
b b b
e e e
b
e
Despues de la cruza:
H1 =
H2 =
a
c
a
c
a
c
d b b b e e e e
a! d d d! b b b b
La cruza acentuada reporto buenos resultados en un pequeno conjunto de funciones de prueba [201]. Sin embargo, no hay evidencia contundente acerca de su
efectividad.
La cruza acentuada tiene una buena inspiracion biologica, porque estas marcas
de cruza efectivamente existen en la naturaleza y se co-evolucionan junto con los
cromosomas.
Distribucional
Posicional
La cruza de
puntos (
C
C
Todo parece indicar, que la cruza de puntos tiene tambien un sesgo posicional fuerte, aunque e ste vara en funcion de .
Lq
148
R jV
C
C
Programacion Genetica
Permutaciones
Representacion real
OR
AND
NOT
D1
D0
D1
D1
OR
6
OR
AND
NOT
D0
NOT
NOT
D0
D1
10
Figura 7.5: Un ejemplo con dos padres seleccionados para cruzarse, en programacion genetica.
El primer hijo se produce borrandole al primer padre el fragmento indicado
por el punto de cruza e insertando el fragmento (sub-arbol) correspondiente del
segundo padre. El segundo hijo se produce de manera analoga.
Por ejemplo, considere los 2 padres siguientes mostrados en la figura 7.5. Las
expresiones S de estos 2 padres son:
(OR (NOT D1) (AND D0 D1)) y
(OR (OR D1 (NOT D0)) (AND (NOT D0) (NOT D1)))
Si el punto de cruza del primer padre es 2, y el del segundo es 6, entonces los
hijos resultantes seran los indicados en la figura 7.6.
7.5.1.1 Observaciones sobre la cruza para programacion genetica
C
C
Los padres son seleccionados mediante alguna de las tecnicas que vimos
antes (p.ej., la ruleta).
Suele limitarse la profundidad maxima de un a rbol.
150
OR
OR
AND
AND
NOT
NOT
D0
D1
D0
NOT
OR
D1
D1
NOT
D1
D0
Figura 7.6: Los 2 hijos resultantes de la cruza entre los padres de la figura 7.5
C
C
Order Crossover
Position-Based Crossover
Order-Based Crossover
Cycle Crossover
Otras
151
P1 = 9 8 4 5 6 7 1 3 2 10
P2 = 8 7 1 2 3 10 9 5 4 6
P1 = h k c e f d b l a i g j
P2 = a b c d e f g h i j k l
Posiciones:
1 2 3 4 5 6 7 8 9 10 11 12
Ejemplo de un ciclo:
Tomamos al azar una posicion de cualquier padre. En este caso, tomaremos la
posicion 1:
C
C
H1 = 8 X X X X X X 12 1 9 X 10
Remover de P2 los valores del ciclo:
P2= X 2 3 4 5 6 7 X X X 11 X
Rellenar H1 usando los valores restantes de P2.
H1 = 8 2 3 4 5 6 7 12 1 9 11 10
C
C
C
C
Un punto
Dos puntos
Uniforme
Intermedia
157
Aritmetica simple
Aritmetica total
jV GV{jG OiV
iV{iGAjVSjG TV
jViGV{jGV
iV{jGAjVSjGjV
P1=
P2=
TVUjGliV GAiViGjVjG?iVUjG?iVS
iViG"WV Gl VjG/SjVUiG.TVWGjV
TVUjG"WV Gl VjGjVjG?iVUjGAjV
iViGliV GAiViG/SjVUiG.TVWGAiVS
GVVVG
GVVV G
G
u
GVVVG
G
u
u egjG'l
GVVVG
u GVVV'G u l hu
u GVVV'G u hu
si
si
si
r
R
p
(7.1)
R # "" !! R !% $ ##
R ! $ # # R # ""! !
159
(7.2)
g v
! G !
l
esta en el rango
iViGWViGV GAjVS
VjGjiViG/UjV GWVS
g v
# G #
l
&
y cada valor
'
esta en el rango
gqjiG?*l
R .V
mR UiV
'
r
R
R
R
R
X z V z V;
R
(7.3)
R
z jV= R X z z R jjV>S
Por lo que: u egqjV>SjGTV;ol
Como los rangos para la cuarta variable son los mismos que para la tercera,
los calculos son identicos.
Es decir: u R ehgqjV>SjGVTl
R
Supongamos que u
jVS; y u jV{
H1 = iVjGWViG?iV (iG"WV
H2 = VWGjV GAjVSjGV
Haciendo k =3, tenemos:
,
, por lo que:
u ehgjG'l
160
P1 =
P2 =
VjG"WV G.TViGjVS
TVWGjjViG!UiViG"WVS
TVTUiGVUSjGAjVWGjV
TV{;jG?iVU+iGV{UjGAiV
)(
2. Calcular .
donde:
si
1+;=<?>A@
de lo contrario
LNM *PO o 0 .
)] [`V ?O ] a
) (( ] VYV^0_0_[b
V OQ] ]
Ejemplo de SBX:
P1 =
P2 =
161
(7.4)
q
q
Order-based Crossover.
Seleccion: Debera implementarse la seleccion mediante torneo binario determinstico, usando barajeo de la poblacion.
< L [ O
tama
no de la matriz ( )
matriz de distancias (dist[n][n])
matriz de flujos (flujo[n][n])
El objetivo es minimizar el costo total, definido por:
FvC vF C
w
z
x
T
y
*ut { wt|8yT~{ }kG S a S a 1h"?S r S Ua a S r S aUa
(7.5)
costo
a * <?eg>g>g>%e [ O
donde: r S (
L ) se refiere a la permutacion codificada en
el algoritmo genetico. Se le sugiere escribir una funcion (independiente) que calcule la aptitud de una permutacion a partir de las matrices
de distancias y flujos. Si lee los datos del archivo ajuste.dat, y proporciona la permutacion: 2 3 4 0 1, el costo debe ser 50 (valor o ptimo).
Los costos o ptimos para los demas archivos son los siguientes:
tai10.dat
tai12.dat
tai15.dat
164
Captulo 8
Mutacion
La mutacion se considera como un operador secundario en los algoritmos geneticos
canonicos. Es decir, su uso es menos frecuente que el de la cruza.
En la practica, se suelen recomendar porcentajes de mutacion de entre 0.001
y 0.01 para la representacion binaria.
Algunos investigadores, sin embargo, han sugerido que el usar porcentajes
altos de mutacion al inicio de la busqueda, y luego decrementarlos exponencialmente, favorece el desempeno de un AG [79].
(donde es la longitud de la cadena
Otros autores sugieren que
cromosomica) es un lmite inferior para el porcentaje o ptimo de mutacion [7].
El papel que juega la mutacion en el proceso evolutivo, as como su comparacion con la cruza, sigue siendo tema frecuente de investigacion y debate en
la comunidad de computacion evolutiva. En este captulo estudiaremos diferentes
tecnicas de mutacion que se han propuesta en la literatura especializada.
C
yv *
a)
P=
10
b)
P=
10
1. Seleccionar
genes al azar.
2) 5 4 10
5) 10 4 5
3) 5 10 4
Individuos generados:
P1= 9 4 2 1 10 7 6 5 3 8
P2= 9 5 2 1 4 7 6 10 3 8
P3= 9 5 2 1 10 7 6 4 3 8
P4= 9 10 2 1 5 7 6 4 3 8
P5= 9 10 2 1 4 7 6 5 3 8
De entre ellas, se selecciona a la mejor. En este caso, supondremos que es P4:
P= 9 10 2 1 5 7 6 4 3 8
167
OR
OR
5
AND
A0
AND
A0
A1
A0
NOT
A1
A1
&
V * c C ge >>U>Ue v j
V * c C ge >U>>Ue eg>U>>Ue T j
W / e[ 2
[ / e [ 2
a
y la variable esta en el rango S e
donde:
/ es 2
R = flip(0.5)
regresa un valor en el rango
si R=Cierto
si R=Falso
este cerca de cero se incrementa conforme (generacion actual) crece. Esto hace
que este operador explore de manera mas global el espacio de busqueda al inicio
(cuando es pequena) y de manera mas local en etapas posteriores.
CGF_ IU
/ e s 2 * Ys / O
[ E 2
donde:
r es un numero aleatorio real entre 0 y 1, T es el numero maximo de
generaciones y es un parametro que define el grado de no uniformidad de la
mutacion (Michalewicz [161] sugiere usar
).
* @
Ejemplo:
V * c 0h>Ad?efT>R@heg[ O >R0Qe<?>AiZj
* [_0Q>< ,
* * fT>R@ ,
1 * l?>A@ ,
*
R = Falso,
* <?@>A<0,f ,
* @ @ ,.
** [ / e [ W 2 *
fT>A@_[ /:@QefT>R@ 0Z2 fT>A@_[ /:@QelQ>R@Z2
CGFY I
/:@Q* elQ>R@Z2 * l?>R@?/ O [`<?* >A0f E O 2 * l?>fZiZp&fkdk@
fT>A@[`l?>fkiZp&fkdZ@ [ >Ap&iZp&fkdk@
V * c C ge >U>U>e T j
V * c C eg>>U>Ue e>>U>e v j
donde:
169
S e%_ a
* _
Si flip(0.5)=TRUE
de lo contrario
Ejemplo:
V * c O >A@Qe0Q>l?eg[o<?>A@Qed?>ikj
* [o<?>A@ ,
* [od?>A< ,
* O > d
P
* o[ d?><
V * c C ge >>U>Ue e>>U>e v j
V * c C ge >U>>Ue eg>U>>Ue T j
donde:
}
* L / e%_2
se usa una distribucion uniforme y [LB, UB] definen los rangos mnimos y
maximos de la variable .
Ejemplo:
V * c @Q>d?eg[ O >AdQemQ>i?ep?> O j
* @Q>d , * <?>< , _ *O <?>A@
}
* L /<?>A<Qe O <?>A@Z2 * fT>Ad
170
( * /0132 n4 9 4
1;=<?>R@
Si
de lo contrario
&
* O Z< < W
Z P
donde
es el ndice de distribucion para la mutacion y toma cualquier
valor no negativo. Deb sugiere usar:
( = generacion actual)
3. El valor de la posicion mutada se determina usando:
* W ( ~
V * c 0h>Ad?efT>R@heg[ O >R0Qe<?>AiZj
1 * *<?>AmZ0 ,
t=20
* * [ O >A0 ,
*O [_0Q>W < , *uO _ l?><
0&<
<Z<
( *PO [S0T/ O [b<?>AmZ0Z2 a 4 9
4
( * <?><Z<&fkm&iZ<&fkdf
~ * [ * l?>A< W 0Q>A< * ?i >A<
* [ O >A0 W <?><Z<&f"m&i&<&fkdv/i?>A<Z2 * [ O > O l O mZ@lZl
Ejemplo:
171
q
q
Wolfgang Banzhaf, Peter Nordin, Robert E. Keller, and Frank D. Fancone, Genetic Programming. An Introduction, Morgan Kaufmann Publishers, San Francisco, California, 1998.
John R. Koza, Genetic Programming. On the Programming of Computers by Means of Natural Selection, The MIT Press, Cambridge,
Massachusetts, 1992.
173
Z
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
W X
0 0
0 0
0 1
0 1
1 0
1 0
1 1
1 1
0 0
0 0
0 1
0 1
1 0
1 0
1 1
1 1
Y F
0 1
1 1
0 0
1 1
0 0
1 0
0 1
1 1
0 1
1 0
0 1
1 0
0 0
1 1
0 0
1 0
174
Captulo 9
Ajuste de Parametros
9.1 Introduccio n
Los parametros principales de un AG son:
q
q
Tamano de poblacion
Porcentaje de cruza
Porcentaje de mutacion
@&< a O <Z<
<?>lZ< O
<?><Z<
individuos
q
q
Observando el desempeno de diferentes operadores de cruza, De Jong concluyo que, aunque el incrementar el numero de puntos de cruza afecta su
disrupcion de esquemas desde una perspectiva teorica, esto no parece tener
un impacto significativo en la practica.
Grefenstette [116] uso un AG para optimizar los parametros de otro (un metaAG).
El meta-AG fue usado para evolucionar unos 50 conjuntos de parametros de
un AG que se uso para resolver las funciones de De Jong.
Cada individuo codificaba seis parametros:
1. Tamano de la poblacion
2. Porcentaje de Cruza
3. Porcentaje de Mutacion
4. Intervalo generacional (porcentaje de la poblacion que se reemplaza en cada
generacion)
/r 2
/r 2
30 individuos
0.95
0.01
Elitista
1.0 (100%)
1 (basado en la
mnima de
la primera generacion)
/r 2
177
;<?> O
o ptimo de poblacio n
9.3 Tamano
Goldberg [103] realizo un estudio teorico del tamano ideal de la poblacion de
un AG en funcion del numero esperado de nuevos esquemas por miembro de
la poblacion. Usando una poblacion inicial generada aleatoriamente con igual
probabilidad para el cero y el uno, Goldberg derivo la siguiente expresion:
Tam Poblacion =
donde: L = longitud de la cadena (binaria).
Esta expresion sugiere tamanos de poblacion demasiado grandes para cadenas
de longitud moderada.
Considere los siguientes ejemplos:
O >Alk@ EAD : 4 I
178
L = 30,
L = 40,
L = 50,
L = 60,
Tam
Tam
Tam
Tam
Poblacion = 130
Poblacion = 557
Poblacion = 2389
Poblacion = 10244
Mientras un AG calcula explcitamente las aptitudes de los miembros de una poblacion, al mismo tiempo estima implcitamente las
aptitudes promedio de una cantidad mucho mayor de esquemas, calculando implcitamente las aptitudes promedio observadas de los esquemas que tienen instancias en la poblacion.
un el teorema de los esquemas (que veremos mas adelante), un AG procesa
/ Seg
2 esquemas. A partir de esta idea, Goldberg concluye entonces que a mayor
valor de (tamano de la poblacion), mejor desempeno tendra el AG, y de ah
deriva su expresion para calcular el tamano o ptimo de una
poblacion.
d
esquemas en una repreEl problema con este argumento es que solo hay
/
2 esquemas si es
sentacion binaria, por
lo que no se pueden procesar
* d
20-30 individuos
0.75-0.95
0.005-0.01
0&<Z<
<?><k@
0&<
<?><Z<k0
q
q
9.5 Auto-adaptacion
En general, es poco probable poder determinar a priori un conjunto o ptimo de
parametros para un AG cualquiera aplicado a un problema en particular. Algunos
investigadores creen que la mejor opcion es la auto-adaptacion.
Ejemplo de Adaptacion en Lnea
Srinivas y Patnaik [210] propusieron un esquema para adaptar las probabilidades de cruza y mutacion de un algoritmo genetico. La propuesta se basa en
la deteccion de que el algoritmo genetico ha convergido. Para ello, verifican que
diferencia existe entre la aptitud maxima de la poblacion y la aptitud promedio.
Da tal forma, se hacen variar los porcentajes de cruza y mutacion en funcion de
esta diferencia de valores (aptitud maxima y aptitud promedio de la poblacion).
Las expresiones propuestas son:
* C8 / \K [ ( 2
vy M
* D / \K [ ( 2
y?
Sin embargo, con estas expresiones los porcentajes de curza y mutacion se incrementan conforme el algoritmo genetico converge y produce un comportamiento
altamente disruptivo en la vecindad del o ptimo, de manera que el algoritmo puede
no converger jamas.
Para evitar este problema, estas expresiones deben modificarse de manera que
se preserven las buenas soluciones.
La propuesta es ahora la siguiente:
* C / \ K [ 2 / \ K [ ( 2e C ; O >A<
yTM
181
* D / \ K [ 2 / ~ [ ( 2 e D ; O ><
yT
C y D deben ser menores que 1.0 para hacer que los valores de yM y yT
donde
poblacion.
Estas expresiones hacen que el porcentaje de cruza ( ) y de mutacion ( )
disminuya cuando los individuos tienen una aptitud alta y que aumenten en caso
contrario. Notese sin embargo que y
se haran cero al alcanzarse la aptitud
si
y
si
. Para
maxima. Tambien adviertase que
evitar valores mayores a 1.0 para y , se imponen las restriccioes siguientes:
yvM
e Z ; O > <
y M yT
yM yT
y M * C
yvM yT
yvM * e
y? *& e
yv
* ( yT
* D * (
; (
; (
donde
.
Debido a que
y
se haran cero cuando el individuo sea el mejor en la
poblacion, su propagacion puede llegar a ser exponencial, produciendo convergencia prematura. Para evitar eso, los autores proponen usar un porcentaje de
mutacion por omision (0.005) en estos casos.
Las expresiones finales son:
* C / ~ [
* e (
* D / \K [
*& e (
C
donde: e D ,
yvM
vy M
yT
yT
2 / \ [ ( 2 e (
2 / ~ [ ( 2 e (
D *&* <Q>R@
C * *uO >A<
Q* <?>A@
Con estos valores, se usan soluciones con una aptitud inferior al promedio
hara
para buscar la region donde reside el o ptimo global. Un valor de
182
D * ?< >R@
C *
* O A> <
(
\K
~
O {
*
y XO W GC F Fk% E C I
donde:
* / r e y? 2
al nuevo genotipo:
/ r e y 2
La mutacion de la variable r esta dada
| por:
| si y
r
O [ r si y
r
donde: es un valor aleatorio (distribucion uniforme) muestreado de nuevo para
cada posicion .
183
de porcentajes de
y * / y C ege y 2
* /r ey 2
|
O { u
*
C
G
F
K
y O W K Fk% E C I eG * O ge Ne >
yT
/ 2 * Fk R
)
?y
* tamano de la poblacion, * longitud cromosomica, * gendonde:
)
eracion actual, e e son constantes definidas por el usuario (dependientes del
problema).
Notese que en todas estas propuestas se usa el mismo porcentaje de mutacion
para todos los individuos de la poblacion en la generacion .
Back y Schutz (1996) propusieron un porcentaje de mutacion que se decrementa usando:
yT / 2 * 0 W F D
185
<; ; *
donde:
,
longitud cromosomica,
el numero maximo de generaciones.
La variabilidad es:
generacion actual y
es
/
2
Ty
O
*
/
2
Ty r T0 / / r 2 WO ~2 [
q
q
q
q
Ajuste adaptativo de parametros (probabilidad de cruza y mutacion, longitud del genotipo y tamano de la poblacion).
El mecanismo de adaptacion puede estar completamente separado del mecanismo de busqueda del AG. Este tipo de esquema no acoplado no es muy atractivo, porque implica un control centralizado, superimpuesto al mecanismo de
busqueda del AG.
Otra posibilidad es que el mecanismo de busqueda del AG sea usado parcialmente por el mecanismo adaptativo. En este caso, se dice que el AG y el
mecanismo adaptativo estan ligeramente acoplados (loosely coupled).
Si la adaptacion es conducida por las fuerzas internas de la busqueda evolutiva, podemos hablar de un acoplamiento fuerte. En este caso, se origina un
acoplamiento de los 2 espacios de busqueda sobre los que opera el AG (el espacio
de las soluciones y el de las variables de decision).
|
| D x x|
|8y O | vF C
w xy / [` 2e
*
W
C
D
e
/
e
2
G
D
donde
r
r
(9.1)
O & W C / r C e r D 2 x
| C r
*
*
x| donde: [`lkO @Q>A@&dZl; r O ;=lk@Q>A@&dZlQe @&<Z<?Oe Ze y: O (9.2)
< l kd 0
S a* [o[odkdk00 [[odkl0 <[_dZ0 [ol dk0 dk[_0 dk0 [o[ dkO l0 [[ O ll
dk0 dZ0 kd 0
(9.3)
189
/r 2
=numero de unos en ,
4. Considere la siguiente funcion de aptitud:
donde es un cromosoma de longitud 4. Suponga que el AG ha corrido
durante tres generaciones, con las siguientes poblaciones:
generacion 0:
generacion 1:
generacion 2:
190
Captulo 10
Manejo de Restricciones
Hasta ahora hemos estudiado solo problemas sin restricciones. Sin embargo, en
la practica normalmente tenemos problemas con restricciones de diferentes tipos
(igualdad, desigualdad, lineales y no lineales), tales como:
Sujeto a:
L :: k / r 2
x
;=< *O e0Qeg>>g>%e L
Pero el algoritmo genetico opera como una tecnica de optimizacion sin restricciones, por lo que tenemos que disenar algun mecanismo que permita incorporar
la informacion pertinente sobre la violacion de restricciones en la funcion de aptitud. Este captulo habla precisamente de diferentes esquemas para hacer esto.
donde:
x
L /
x
*
x
x
*2 / 2
xy x
t C / 2D
191
q
q
Puede penalizarsele simplemente por no ser factible, sin usar ninguna informacion sobre que tan cerca se encuentra de la region factible.
Richardson et al. [187] definieron algunas de las reglas basicas para disenar
una funcion de penalizacion:
1. Las penalizaciones que son funciones de la distancia a la zona factible son
mejores que aquellas que son solo funciones del numero de restricciones
violadas.
2. Para un problema con pocas variables y pocas restricciones, una penalizacion que sea solo funcion del numero de restricciones violadas no producira ninguna solucion factible.
3. Pueden construirse buenos factores de penalizacion a partir de 2 factores:
el costo de cumplimiento maximo y el costo de cumplimiento esperado.
El primero de ellos se refiere al costo de hacer factible a una solucion infactible.
4. Las penalizaciones deben estar cerca del costo de cumplimiento esperado,
pero no deben caer frecuentemente por debajo de e l. Entre mas preciso
sea el factor de penalizacion, mejores resultaran las soluciones producidas.
Cuando una penalizacion frecuentemente subestime el costo de cumplimiento, el proceso de busqueda fallara.
Existen, sin embargo, varios problemas para definir una funcion de penalizacion:
1. No es obvio combinar los 2 factores de los que hablan Richardson et al.
[187] en una funcion de penalizacion.
192
2. Definir los valores o ptimos del factor de penalizacion es una tarea virtualmente imposible a menos que conozcamos el problema a fondo, en cuyo
caso puede disenarse una funcion de penalizacion a la medida, pero hacerlo
resultara de cualquier forma innecesaria ya que el o ptimo podra determinarse por metodos analticos exactos.
3. El costo del cumplimiento esperado normalmente tiene que estimarse mediante metodos alternativos (por ejemplo, estimando el grado de violacion
de las restricciones) que pueden ser difciles de implementar.
A continuacion revisaremos rapidamente diversas variantes de la funcion de
penalizacion que se han propuesto en la literatura, comentando brevemente sobre
sus desventajas.
x x
| |
* / 2 W 8| y C / 2
x | L
t
donde:
son los coeficientes de penalizacion utilizados y
siendo los niveles de violacion definidos por el usuario.
10.1.2.1 Analisis
* O e 0Qeg>g>g>e ,
L /:0 WPO 2
x
x
|8y x
L / 2 * / 2 W / 2 t C ] / 2 ]
)
donde , y son constantes definidas por el usuario. Los valores sugeridos
* <?>A@ , *uO y ) *uO o 0 .
por los autores para las constantes son:
10.1.3.1 Analisis
x
x
|
/ 2 * / 2 W
D C |y C / 2 D
L
t
donde: representa el horario de enfriamiento
y es una funcion que debe ser
{
definida
por el x usuario.
x Michalewicz
*5O y
* <Q>A<Z<&<Z<Z< O , con incrementos
y Attia sugieren usar:
C * <Q> O .
10.1.4.1 Analisis
El principal problema de esta tecnica es la definicion del horario de enfriamiento.
|8y |
L / 2 * / 2 W / 2 t C / 2 D
siempre factible. El caso # 2 ocurre cuando dicho individuo no fue nunca factible.
Esta tecnica lo que hace entonces es disminuir la penalizacion cuando el mejor
individuo resulta consistentemente factible y aumentar la penalizacion cuando resulta infactible. Si estos cambios son intermitentes (es decir, el mejor individuo
es a veces factible y a veces no), entonces la penalizacion no se cambia.
Obviamente, es necesario definir el valor inicial .
10.1.5.1 Analisis
El principal problema de esta tecnica es como elegir el factor inicial de penalizacion y el intervalo generacional (o sea, ) de manera que el monitoreo de
factibilidad produzca resultados razonables.
195
Una muy grande o muy pequena puede hacer que la funcion de penalizacion
nunca cambie, en cuyo caso la tecnica se reduce a una penalizacion estatica tradicional.
Finalmente, tampoco esta claro como definir buenos valores de y .
)C )D
L / 2 * W / |y 2 C |
Si la solucion es factible
(10.2)
/
2
de lo contrario
t
es el valor de la funcion objetivo de la peor solucion factible de la
donde
se
poblacion. Si no hay ninguna solucion factible en la poblacion, entonces
hace igual a cero.
Deb [66] usa torneo binario aplicando las siguientes reglas:
196
q
q
Funciones de penalizacion.
Algoritmos de reparacion.
Ejemplos
q
q
* / / r 2e C / r 2egNe / r 282
x se quiere encontrar r tal que
donde
/ r 2;=< , *uO ee y / r 2; / s 2 , s factible.
q
q
Esquema Poblacional. Consiste en dividir a la poblacion en subpoblaciones, donde cada una de ellas enfocara sus esfuerzos en optimizar uno de
los objetivos del problema (VEGA [199]).
x r
/ r 2 ; / r 2
No
Un
punto es una solucion no dominada si no hay
dominancia.
y para al menos un valor ,
para
tal que:
.
r x x
/r 2 /r 2
P
* O ge Ne
/ D2
10.2.1 COMOGA
Propuesto por Surry et al. [216]. Combina las jerarquas de Pareto con la propiedad
de VEGA de favorecer soluciones extremas en un AG no generacional.
q
q
w
z
x
T
y
{
/ r( 2 *
r /<Qe / r ( 22
Entre dos individuos no factibles, se prefiere aquel que viole en menor cantidad las restricciones del problema.
WuO
/ /r 2
/ L
if
else if
else
<k2
*<k2
|
* / 2
then L
r
*
[
then
L
200
q
q
q
q
q
q
q
q
Aptitud.
Factibilidad.
Candidato 1
Candidato 2
Sr
Seleccion
puramente
probabilistica
Cuatro
Criterios de
Comparacion
q
q
203
r r
204
q
q
CMEA (Contrained Method-Based Evolutionary Algorithm) de Ranjithan et al. [179]. Utiliza conceptos de programacion matematica con restricciones para problemas de optimizacion multiobjetivo.
Manejo de restricciones con incertidumbre o ruido para Optimizacion
Multiobjetivo de Hughes [132], jerarquiza de manera integrada (tomando
en cuenta restricciones y prioridades) a la poblacion con funciones simples
basadas en probabilidades.
Estas tecnicas solo se han probado en optimizacion multiobjetivo con restricciones y no para problemas de optimizacion global.
fique alguna propuesta al respecto para problemas de optimizacion en espacios continuos. Se recomienda leer:
Slawomir Koziel and Zbigniew Michalewicz, A Decoder-based Evolutionary Algorithm for Constrained Parameter Optimization Problems, In T. Back, A. E. Eiben, M. Schoenauer, and H.-P. Schwefel,
editors, Proceedings of the 5th Parallel Problem Solving from Nature
(PPSN V), pages 231240, Amsterdam, September 1998. SpringerVerlag.
Slawomir Koziel and Zbigniew Michalewicz, Evolutionary Algorithms,
Homomorphous Mappings, and Constrained Parameter Optimization,
Evolutionary Computation, Vol. 7, No. 1, pp. 1944, 1999.
2. Investigue el funcionamiento de una tecnica conocida como memoria conductista (behavioral memory), analizando sus ventajas y desventajas, as
como las posibles dificultades para implementarla (si es que hubiese alguna). Lea:
Marc Schoenauer and Spyros Xanthakis, Constrained GA Optimization, In Stephanie Forrest, editor, Proceedings of the Fifth International Conference on Genetic Algorithms, pages 573580. Morgan
Kauffman Publishers, San Mateo, California, July 1993.
Xidong Jin and Robert G. Reynolds, Using Knowledge-Based Evolutionary Computation to Solve Nonlinear Constraint Optimization
Problems: a Cultural Algorithm Approach, In 1999 Congress on
Evolutionary Computation, pages 16721678, Washington, D.C., July
1999. IEEE Service Center.
Chan-Jin Chung and Robert G. Reynolds, A Testbed for Solving Optimization Problems using Cultural Algorithms, In Lawrence J. Fogel, Peter J. Angeline, and Thomas Back, editors, Evolutionary Programming V: Proceedings of the Fifth Annual Conference on Evolutionary Programming, Cambridge, Massachusetts, 1996. MIT Press.
206
Captulo 11
Software
En general, podemos clasificar el software para computacion evolutiva en 3 grandes
grupos:
q
q
2. Sistemas de proposito general: Proporcionan un rico conjunto de herramientas para programar cualquier tipo de AG y aplicarlo a lo que se desee. En
algunos casos, incluso permiten que el usuario experto modifique partes del
codigo de acuerdo a sus propias necesidades.
Disponibilidad: http://www.aic.nrl.navy.mil/pub/galist/src/BUGS.tar.Z
Nombre: Genesis
Descripcion: Implementacion de un AG que tiene gran valor historico por
haber sido el primer programa de su tipo liberado en el dominio publico.
Lenguaje: C para Unix.
Tambien cuenta con una serie de funciones objetivo, incluyendo las funciones de De Jong, funciones continuas de alto grado de complejidad, una
instancia del problema del viajero, funciones binarias y una funcion fractal.
Finalmente, tiene tambien utileras para monitorear resultados tales como
vaciados de mapas de bit de la poblacion, varianza de las variables objeto y
de los porcentajes de mutacion, etc.
Lenguaje: C para Unix.
Autor: Thomas Back ([email protected])
Disponibilidad: http://www.aic.nrl.navy.mil/pub/galist/src/GENEsYs-1.0.tar.Z
Nombre: DGenesis
Descripcion: Implementacion de un AG distribuido desarrollada a partir
de GENESIS 5.0. Corre en una red de estaciones de trabajo operando con
Unix. Cada subpoblacion es manejada por un proceso Unix y la comunicacion entre ellas se efectua usando sockets de Berkeley Unix.
Lenguaje: C para Unix.
Autor: Erick Cantu Paz ([email protected])
Disponibilidad: http://www.aic.nrl.navy.mil/pub/galist/src/dgenesis-1.0.tar.Z
Nombre: GECO (Genetic Evolution through Combination of Objects)
Descripcion: Ambiente de trabajo orientado a objetos para implementar
prototipos de algoritmos geneticos. Usa el CLOS (Common LISP Object
System) y cuenta con abundante documentacion y algunos ejemplos de uso.
Lenguaje: Common LISP para Macintosh o Unix.
[od W f
Disponibilidad: http://fame.gmu.edu/dduane/thesis
Nombre: GENOCOP (Genetic Algorithm for Numerical Optimization for
COnstrained Problems)
Descripcion: Paquete de optimizacion numerica para funciones con cualquier
cantidad de restricciones lineales (igualdades y desigualdades).
Lenguaje: C para Unix.
Autor: Zbigniew Michalewicz ([email protected])
Disponibilidad: http://www.aic.nrl.navy.mil/pub/galist/src/genocop.tar.Z
Nombre: GPC++
Descripcion: Biblioteca de clases en C++ para desarrollar aplicaciones de
programacion genetica. Esta biblioteca define una jerarqua de clases y
uno de sus componentes integrales es la capacidad de producir funciones
definidas automaticamente.
Lenguaje: C++ para Unix/MSDOS.
Lenguaje: Smalltalk
Autor: Tony White ([email protected])
Disponibilidad: ENCORE (The EvolutioNary COmputation REpository
network)
URL: http://www.cs.bham.ac.uk/Mirrors/ftp.de.uu.net/EC/clife/
Nombre: PGAPack
Descripcion: Biblioteca de proposito general para desarrollar AGs paralelos. Incluye:
Capacidad de invocacion desde FORTRAN o C.
Soporte de redes de estaciones de trabajo, arquitecturas en paralelo y
uniprocesadores.
Tipos de datos binarios, enteros, reales y caracteres (nativos).
Soporte de nuevos tipos de datos.
Interfaz facil de usar.
Niveles multiples de acceso para usuarios expertos.
Facilidades extensivas de depuracion.
Gran cantidad de ejemplos.
Detallada gua del usuario.
Soporte de diferentes tipos de seleccion, cruza y mutacion.
Lenguaje: C para Unix.
Disponibilidad: ftp://ftp.di.unito.it/pub/MLprog/REGAL3.2
Nombre: SCS-C (Simple Classifier System in C)
Descripcion: Version en C del Sistema Clasificador Simple proporcionado
en el libro de Goldberg.
Lenguaje: C para Unix
Autor: Jrg Heitkoetter ([email protected])
Disponibilidad: ENCORE
Nombre: ActiveGA
Descripcion: Un OLE que usa un algoritmo genetico para solucionar un
problema dado. Algunas de sus funciones incluidas son:
Seleccion de torneo o ruleta.
Parametros del algoritmo genetico definidos por el usuario.
Invisible durante tiempo de ejecucion.
Ejemplos en Excel, Visual BASIC y Visual C++.
Los usuarios avanzados pueden usar el API incluido para desarrollar sus
propias aplicaciones, las cuales pueden ser monitoreadas en tiempo real usando el EvolverWatcher.
Precio: $349 dolares
Nombre: PC-Beagle
Descripcion: Programa que examina una base de datos con ejemplos y
usa tecnicas de aprendizaje de maquina para crear un conjunto de reglas de
decision que clasifiquen los ejemplos.
213
El sistema contiene 6 componentes principales, de los cuales uno usa algoritmos geneticos.
Precio: 69.
Nombre: MicroGA
Descripcion: Herramienta que permite la integracion de algoritmos geneticos
en cualquier pieza de software. Se trata de un ambiente de programacion en
C++ que viene en codigo fuente con documentacion y 3 ejemplos completos.
215
216
Captulo 12
Fundamentos Teoricos
Aunque los algoritmos geneticos son simples de describir y programar, su comportamiento puede ser muy complicado, y todava existen muchas preguntas abiertas acerca de como funcionan y sobre el tipo de problemas en los que son mas
adecuados.
La teora tradicional de los AGs (formulada originalmente por Holland en
1975 [127]) asume que, en un nivel muy general de descripcion, los AGs trabajan descubriendo, enfatizando y recombinando buenos bloques constructores
de soluciones en una manera altamente paralelizada. La idea basica aqu es que
las buenas soluciones tienden a estar formadas de buenos bloques constructores
(combinaciones de bits que confieren una aptitud alta a las cadenas en las que
estan presentes).
Holland [127] introdujo la nocion de esquemas para formalizar la nocion
de bloques constructores. Tal vez la forma mas facil de visualizar un espacio de busqueda es considerando todas las cadenas y esquemas de longitud 3.
Graficamente, podemos ver el espacio de busqueda como un cubo donde los
puntos son esquemas de orden 2 y los planos son esquemas de orden 1 (ver
figura 12.1). Todo el espacio de busqueda esta cubierto por un esquema de orden cero (***).
Este resultado puede generalizarse a espacios de dimensiones, donde hablaramos
de hiperplanos. De tal manera, podemos pensar que un AG corta a traves de diferentes hiperplanos en busca de los mejores bloques constructores.
X2
0*0
*10
010
1**
110
01*
*11
1*0
*00
11*
011
111
000
X1
100
0*1
00*
10*
001
101
1*1
*01
**1
X3
C=10
L=2
H1=1*
H2=*0
es una instancia de
H3=10
H4=**
esquemas difer-
0.
0.
En todos los demas casos, el numero es menor o igual a
caso en el que una poblacion de cadenas de bits contenga
Hay algun
0 esquemas diferentes?
exactamente
Cuantos esquemas hay si todas las cadenas son identicas?
218
; O.
Como acabamos de ver, cuando todas las cadenas de una poblacion son iguales,
hay instancias de exactamente
esquemas diferentes.
Esto significa que, en una cierta generacion, mientras el AG esta evaluando
explcitamente las aptitudes de las
cadenas en la poblacion, esta tambien estimando implcitamente las aptitudes promedio de un numero mucho mayor de
esquemas [167].
La aptitud promedio de un esquema se define como la aptitud promedio de
todas las instancias posibles de ese esquema.
Supongamos que generamos aleatoriamente una poblacion de tamano .
En promedio la mitad de las cadenas seran instancias de 1***...* y la mitad
seran instancias de 0***...*.
cadenas que son instancias de 1***...*
Si evaluamos las (aproximadamente)
obtendremos un estimado de la aptitud promedio de ese esquema.
Este valor es un estimado porque las instancias evaluadas en poblaciones de
tamanos tpicos son solo una pequena muestra de todas las instancias posibles.
As como los esquemas no se representan o evaluan explcitamente por el AG,
los estimados de las aptitudes promedio de los esquemas no se calculan o almacenan explcitamente por el AG. Sin embargo, el comportamiento del AG, en
terminos del incremento y decremento en numeros de instancias de esquemas dados en la poblacion, puede describirse como si realmente estuviera calculando y
almacenando estos promedios.
L0
n* f como el entero
/ <Z< OZO 2 * d ).
r
219
cadenas posibles:
Aptitud
8
9
10
11
12
apt. prom
13
14
15
* ! D *OZO >A@
* pk0
Aptitud
0
1
2
3
4
apt. prom
5
6
7
* D"! ! * d?>R@
* 0&i
1~/ e 2
/ e2
/ e u
W O 2 2
/
W=O
220
/r 2 ( / 2
/r 2
r ( / 2
/ r 2,+ / # e 2
* / 1\$ / # e 2 ( / 282 / # e 2
1/ e 2
\M / 2
I2
E
O
'
v
F
3
C
[ V .M -0/ 1
M / # 2 `
pueden
De tal forma, multiplicamos la fraccion de la cadena que # ocupa por la probabilidad de cruza para obtener un lmite superior de la probabilidad de que el
esquema sera destrudo.
El valor es un lmite superior porque algunas cruzas dentro de las posiciones
definidas de un esquema no lo destruiran (p. ej. si dos cadenas identicas se
cruzan). Al sustraer este valor de 1 obtenemos un lmite inferior.
NOTA: La probabilidad de supervivencia bajo cruza es alta, para esquemas con
baja longitud de definicion.
/ 2
I
[ V 2 E'
3 / # 2 * / O b
O
[ V
Q/ 2
NOTA: La probabilidad de supervivencia bajo mutacion es mas alta para esquemas de bajo orden.
Combinando estos 3 efectos (seleccio6 n, cruza y mutacion), tenemos:
A esta expresion se le conoce como el Teorema de los Esquemas [127], y describe el crecimiento de un esquema de una generacion a la siguiente. El Teorema
de los Esquemas frecuentemente se interpreta de tal forma que implica que los
esquemas cortos y de bajo orden cuya aptitud promedio se mantiene por encima
de la media, recibiran un numero de muestras que crece exponencialmente con el
tiempo.
La razon por la que se dice que los esquemas cortos y de bajo orden reciben un
numero de muestras que se incrementa exponencialmente con el tiempo es porque
el numero de muestras de esos esquemas que no son perturbados y permanecen
222
1/ e 2 ( / 2
q
q
Aproximadamente se procesan
por cada generacion.
12.5 Decepcio n
Hemos hablado anteriormente sobre un problema que ha preocupado a los teoricos
de la computacion evolutiva: la decepcion.
Se llama decepcion a la condicion donde la combinacion de buenos bloques
constructores llevan a una reduccion de aptitud, en vez de un incremento. Este
fenomeno fue sugerido originalmente por Goldberg [105] para explicar el mal
224
Aptitud
70
50
49
1
30
2
3
80
Las cadenas con mayor numero de ceros tienen mayor aptitud, pero el o ptimo
global es la cadena de todos unos. En este caso, el AG tendera a favorecer durante
la seleccion a las cadenas con mas ceros y encontrara la cadena de todos ceros (un
o ptimo local) en vez de llegar al o ptimo global.
q
q
Como dan lugar los operadores de bajo nivel (seleccion, cruza y mutacion)
al comportamiento macroscopico de los AGs?
En que tipo de problemas es mas probable que los AGs tengan un buen
desempeno?
En que tipo de problemas es mas probable que los AGs tengan un mal
desempeno?
225
q
q
para un AG?
La panoramica actual es que la competencia entre los esquemas procede aproximadamente de particiones de esquemas de bajo orden a particiones de esquemas
de orden alto. Bethke [22] infirio que sera difcil para un AG encontrar el o ptimo
de una funcion de aptitud si las particiones de bajo orden contenan informacion
erronea acerca de las particiones de orden mas alto.
Consideremos un ejemplo, un tanto extremo, de lo dicho en el punto anterior.
Llamemos al esquema H ganador si su aptitud estatica promedio es la mas alta
en su particion. Supongamos que cualquier esquema cuyos bits definidos sean to, y hagamos
dos unos es un ganador, excepto por el esquema de longitud
que
sea un ganador.
En principio, sera difcil para un AG encontrar
, porque toda particion
de bajo orden da informacion equivocada sobre donde es mas probable encontrar
el o ptimo. A este tipo de funcion de aptitud se le llama con decepci o n total.
Afortunadamente, nadie ha podido encontrar un problema del mundo real que
exhiba decepcion total. Solo se han encontrado problemas reales con decepcion
parcial.
Tambien es posible definir funciones de aptitud con menores cantidades de
decepcion (es decir, algunas particiones dan informacion correcta acerca de la
localizacion del o ptimo). Bethke [22] uso la Transformada de Walsh (similar a
la transformada de Fourier) para disenar funciones de aptitud con varios grados
de aptitud. Posteriormente, un gran numero de investigadores han profundizado
en estos estudios, y hoy en da la decepcion es uno de los problemas centrales
de los teoricos en AGs. Debido a que los AGs se han usado extensamente para
la optimizacion de funciones, es importante que los que desarrollan aplicaciones
con ellos sepan al menos sobre este fenomeno para poder prevenirlo y atacarlo en
caso de que se presente.
Varios investigadores han cuestionado la relevancia del analisis de los esquemas en la comprension del funcionamiento verdadero de los AGs [117, 154, 177].
Por ejemplo, Grefenstette [117] afirma que mucho del trabajo efectuado en
teora de los AGs ha asumido un version mas fuerte de lo que e l llama la Hip o tesis
Estatica de los Bloques Constructores (HEBC):
OZOZOZO >U>U> O
<Z<&<Z<?>U>><
<Z<Z<&<?>>U><
Dada cualquier particion de esquemas de bajo orden y reducida longitud de definicion, se espera que un AG converja al hiperplano (en
esa particion) con la mejor aptitud promedio estatica (el ganador esperado).
227
Esta formulacion es mas fuerte que la original, puesto que dice que el AG
convergera a los verdaderos ganadores de cada competencia entre particiones
cortas y de bajo orden en vez de que converja a esquemas con la mejor aptitud
observada.
La HEBC no es lo que propuso Holland [127], y nunca se ha demostrado
o validado empricamente, pero implcitamente involucra la premisa de que las
funciones de aptitud con decepcion seran difciles para un AG.
Grefenstette proporciona 2 razones posibles por las que la HEBC puede fallar:
1. Convergencia Colateral: Una vez que la poblacion comienza a converger
hacia algun punto, las muestras de algunos esquemas dejaran de ser uniformes.
1/ 2
OZOZO >U>U>
0
r
si
.
/ r 2 * , O si r < >U>>
< de lo contrario
O
La varianza de >>U> es alta, as que el AG converge a las subregiones
de aptitud elevada de este esquema. Esto sesga a todas las muestras subsecuentes de este esquema, impidiendo que se puede obtener un estimado
preciso de su aptitud estatica.
Esto tiene relacion directa con la importancia de la decepcion en el comportamiento de los AGs, porque las funciones de aptitud con decepcion se definen
completamente en terminos de las aptitudes estaticas promedio de los esquemas.
228
orden intermedio o alto. Sin embargo, algunas cosas extranas sucedieron. Uno
de los hillclimbers que usaron (haban de 3 tipos) supero por mucho al algoritmo
genetico (encontro la solucion 10 veces mas rapido que el AG).
Tras efectuar un analisis de la funcion en la que el AG tuvo problemas, se
determino que una de las causas fueron los hitchhikers, que limita seriamente
el paralelismo implcito del AG restringiendo los esquemas muestreados en ciertos lugares. Estos genes parasitos limitan el efecto de la cruza para recombinar
bloques constructores, y hacen que converjan hacia esquemas equivocados en diversas particiones. Sin embargo, este fenomeno no debe resultar demasiado sorprendente si se considera que se ha observado en la genetica real. Para lidiar con
este problema se propuso un Algoritmo Genetico Idealizado, y se concluyeron
varias cosas importantes en torno a como debe disenarse un algoritmo genetico
convencional para evitar el hitchhiking:
1. La poblacion tiene que ser suficientemente grande, el proceso de seleccion
debe ser suficientemente lento, y el porcentaje de mutacion debe ser suficientemente alto para asegurar que no haya ninguna posicion que permanezca fija con un solo valor en ninguna cadena.
2. La seleccion tiene que ser suficientemente fuerte como para preservar los
esquemas deseados que se han descubierto, pero tambien tiene que ser suficientemente lenta (o, de manera equivalente, la aptitud relativa de los esquemas deseables no traslapados tiene que ser suficientemente pequena) para
prevenir que ocurra algun hitchhiking significativo en algunos esquemas
altamente aptos que pueda eliminar esquemas deseables de otras partes de
la cadena.
3. El porcentaje de cruza tiene que ser tal que el tiempo en que ocurra una
cruza que combine dos esquemas deseados sea pequeno con respecto al
tiempo de descubrimiento de los esquemas deseados.
Estos mecanismos no son compatibles entre s. Por ejemplo, un alto porcentaje
de mutacion esta en contraposicion con una seleccion fuerte. Por lo tanto, debe
cuidarse de que haya algun equilibrio de estos puntos a la hora de aplicarlos.
El terorema de los esquemas hace predicciones en torno al cambio esperado
en las frecuencias de los esquemas de una generacion a la siguiente, pero no hace
predicciones directamente sobre la composicion de la poblacion, la velocidad de
convergencia de la poblacion o la distribucion de aptitudes de la poblacion con respecto al tiempo. Como un primer paso para tener una mejor comprension del
230
de Funciones Deceptivas
12.11 Diseno
Problema deceptivo mnimo
231
{G{
CGC
{C
C
CGC
{G{
es la aptitud
(9 maxima9 posible (optimo global).
Ahora procederemos a introducir el elemento deceptivo usando la idea siguiente: buscaremos que en nuestro problema uno de los esquemas suboptimos de
orden 1 (o los dos) sea mejor que los esquemas de orden 1 del o ptimo.
Para poner el problema en una perspectiva mas adecuada, vamos a normalizar
todas las aptitudes con respecto al complemento del o ptimo global:
{ 9
{
9
{GC {C
{G{C
{GC {
* * *
Podemos re-escribir ahora la{Gcondici
on de
{
{ globalidad{ en forma normalizada:
{GC {C {G{ 9 {GC {C {G{C 9 {GC {C {GC {
{G{
W C C W CGC
{G{ 0 { { 0
W{G{ C C W{G{ CGC
232
O W {G{C
OW
{GC { W {CG{C
W WO
W=O [
/ < 2 / O 2
/ <Z2 / O 2
En estas expresiones estamos ignorando todos los demas alelos de las cadenas cromosomicas que no sean las 2 posiciones definidas antes indicadas y las
expresiones anteriores implican un promedio sobre todas las cadenas contenidas
en el subconjunto de similitud. De tal forma que deben cumplirse las siguientes
expresiones:
CGC
/<Z<k2
W / < O 2 / O <k2
0
/<Z<k2 W / O <Z2 / < O 2
W / ZO O 2
W0 / OZO 2
0
/ < 2 / O 2
C
TIPO I: {G{
TIPO II:
{G{
{ ( O )
C ( ; O )
233
atractor
aptitud
01
00
11
TIPO I:
f 01> f 00
10
Figura 12.2: Representacion grafica de la clase de problemas deceptivos de Tipo
I.
Graficamente, podemos representar estos dos problemas en las figuras 12.2 y
12.3, respectivamente.
Estos 2 tipos de problemas son deceptivos y puede demostrarse que ninguno
de ellos puede expresarse como una combinacion lineal de los valores alelicos del
individuo.
Ninguno de estos casos puede expresarse como:
D x x
w
x
y
/r C er D 2 * W r
C
/ 2]
/ r 2 * L g
< / 2
Los Algoritmos Geneticos son usados1?> a menudo para resolver problemas de opti<; =
mizaci
asumiendo que
3:
A@ para todo
> 1
1 on del tipo:
; =
C
B
y
.
:
* <?e O
234
atractor
aptitud
01
00
TIPO II:
f 00> f 01
11
10
k/ 2
*HGIKJ
donde ,
y son las matrices de transicion de los operadores de Cruza,
Mutacion y Seleccion respectivamente.
Cuando se usa mutacion uniforme se tiene que:
x|
* L
x|
en donde
es la probabilidad de mutacion del AGS, #
es la distancia de
I
Hamming entre los estados y , y
. De lo anterior conclumos que
es
positiva.
235
Por otra parte, dado que el operador de seleccion lo que hace es proporcionarnos
pares de individuos con fines de que ya sea que pasen intactos a la poblacion siguiente o que con una cierta probabilidad mediante el operador de cruza puedan dar
lugar a otros dos individuos nuevos, la matriz de transicion de este operador lo
que hace es dejar ordenados a los individuos tal y como se iran tomando para
dar lugar a la poblacion siguiente.
El uso de un operador de seleccion proporcional o de torneo [196] determina la existencia de una probabilidad estrictamente positiva de que la poblacion
quede intacta, lo cual asegura que los elementos de la diagonal
de la matriz de
J
transicion del operador son positivos, por lo que se concluye que la matriz es
columna-permisible.
xRx
es
>
3: E
Definicion 12.12.1 Sea R
una sucesion de variables aleatorias representando la mejor aptitud dentro de la poblaci o n representada por el estado en el paso . Un algoritmo gen e tico converge al o ptimo global
si y solo si:
6TS.U
6
:
* r3: / 2 ] ; =
donde
1>
:VR
>
*PO
(12.1)
converge
V
U
{ X12.12.1
{
U
Teorema
Sea
P
una
matriz
estoc
a
stica
primitiva.
Entonces
S.U
W
* Y L , donde
V
cuando
a una
matriz
estoc
a
stica
positiva
estable
@
L
*ZL V *ZL V tiene entradas diferentes de cero y es u nica indeU
x
6
x
/ / 282 ] u
* O ge >>U>Ue L >
r
6
estado en6 el que
Demostraci
on Sea
D cualquier
3: E
6
L6
[
U
y la probabilidad
de que el AGS
este en tal estado
en el paso . Claramente,
>
>
L
L
:VR B
:VR
. Por el teorema 12.12.1 la probabili
L U
dad de que el AGS este en 6Tel
. Por lo tanto:
S.U estado6 converge a
:
:VR
; O [
*
>
x <
; O [ L O
/2
C I
0 t 0 Et
0t
{
* / E / 2e E C / 2e E D / 2 eg>>U>Ue E / 82 2
t
237
*
E / 2 es elE su per]individuo
de> la poblaci
o
n
(estado)
, ahora bien, sean
1
*
O
k / 3r : / / 282
eg>U>>Ue L 2 ]; = el mejor individuo de la poblacion
entonces:
*
fhg
g
F
cd
d
de
..
Fp\_jj
Fp\lk
j
cd
d
..
.
de
\ knm j
\ knm k
..
.
de
fhg
\lkk
cd
\_jj
\lk
j
..
.
..
\ kom knm
fhg
g
F_\Ckok
F_\ knm j
..
.
..
Fp\ ok m k
F_\ knm knm
La estructura mostrada de la matriz F
se debe a que, como ya se menciono, las
poblaciones estan ordenadas de manera descendente de acuerdo a la calidad de su
super individuo, de tal manera los espacios en blanco representan ceros puesto que
no es posible pasar de un estado a otro con un super individuo de menor calidad.
De lo anterior se concluye que F_\joj
F puesto que tales matrices corresponden con las poblaciones que tienen como super individuo al o ptimo .
Por otra parte, haciendo las siguientes definiciones:
*
cde
Fp\lk
j
..
.
f g
iHr
*
cde
F_\Ckok
..
.
F_\ k m j
Fp\ k m k
concluimos que la matriz F
es reducible:
238
..
F_\ k m k m
f g
Ps F
q
t
rvu
* <
x yTFv{ C G x F x <
r q G r
U
F
* :
S.U
F
*
s
U
es una matriz
estoca stica estable con F
* <
L
*xY L
Gxw
es
*
s
U
U
L
, donde
L
satisface:
<
G U
* xU L
y
<
{
F
<
O ;
es u nica
para
* <
* < O <
D *
O o o O
* Y < O
*O < O < O o
* O
C
* < oO o Z< <k ,, (b)
(e)
* <Q>A<Z<&d
M * <?>lk@
239
240
Captulo 13
Operadores Avanzados
Ademas de los operadores tradicionales de cruza y mutacion que hemos estudiado previamente, existen otros, mas especficos, que aunque no suelen usarse con
mucha frecuencia en la practica, es importante conocer. Este captulo se dedicara
al estudio de ellos.
Padre 1 (diploide):
A:10110101
011110011110010010101001
B:00000101
001001110011110010101001
Padre 2 (diploide)
C:00000111000000111110
000010101011
D:11111111000010101101
010111011100
Hijo (diploide):
10110101001001110011110010101001
00000111000000111110010111011100
13.2 Inversio n
Holland [127] propuso formas de adaptar la codificacion de su algoritmo genetico
original, pues advirtio que el uso de cruza de un punto no trabajara correctamente
en algunos casos.
El operador de inversion es un operador de reordenamiento inspirado en una
operacion que existe en genetica. A diferencia de los AGs simples, en genetica la
funcion de un gene es frecuentemente independiente de su posicion en el cromosoma (aunque frecuentemente los genes en un a rea local trabajan juntos en una
red regulatoria), de manera que invertir parte del cromosoma retendra mucha (o
toda) la semantica del cromosoma original.
Para usar inversion en los AGs, tenemos que encontrar la manera de hacer que
la interpretacion de un alelo sea la misma sin importar la posicion que guarde en
una cadena. Holland propuso que a cada alelo se le diera un ndice que indicara
su posicion real que se usara al evaluar su aptitud.
Por ejemplo, la cadena 00010101 se codificara como:
>
>
Esta nueva cadena tiene la misma aptitud que la anterior porque los ndices
siguen siendo los mismos. Sin embargo, se han cambiado los enlaces alelicos.
La idea de este operador es producir ordenamientos en los cuales los esquemas
beneficos puedan sobrevivir con mayor facilidad.
Por ejemplo, supongamos que en el ordenamiento original el esquema 00**01**
es muy importante. Tras usar este operador, el esquema nuevo sera 0010****.
Si este nuevo esquema tiene una aptitud mas alta, presumiblemente la cruza
de un punto lo preservara y esta permutacion tendera a diseminarse con el paso de
las generaciones.
243
Debe advertirse que el uso de este operador introduce nuevos problemas cuando
se combina con la cruza de un punto. Supongamos, por ejemplo, que se cruzan
las cadenas:
>
>
>
>
Estas nuevas cadenas tienen algo mal. La primera tiene 2 copias de los bits 1
y 6 y ninguna copia de los bits 3 y 5. La segunda tiene 2 copias de los bits 3 y 5 y
ninguna copia de los bits 1 y 6.
Como podemos asegurarnos de que este problema no se presente?
Holland propuso 2 soluciones posibles:
1. Permitir que se realice la cruza solo entre cromosomas que tengan los ndices
en el mismo orden. Esto funciona pero limitara severamente la cruza.
2. Emplear un enfoque amo/esclavo: escoger un padre como el amo, y reordenar temporalmente al otro padre para que tenga el mismo ordenamiento
que su amo. Usando este tipo de ordenamiento se produciran cadenas que
no tendran redundancia ni posiciones faltantes.
La inversion se uso en algunos trabajos iniciales con AGs, pero nunca mejoro
dramaticamente el desempeno de un AG. Mas recientemente se ha usado con un
e xito limitado en problemas de ordenamiento tales como el del viajero.
Sin embargo, no hay todava un veredicto final en torno a los beneficios que
este operador produce y se necesitan mas experimentos sistematicos y estudios
teoricos para determinarlos.
Adicionalmente, cualquier beneficio que produzca este operador debe sopesarse con el espacio extra (para almacenar los ndices de cada bit) y el tiempo
extra (para reordenar un padre antes de efectuar la cruza) que se requiere.
244
13.3 Micro-Operadores
En la Naturaleza, muchos organismos tienen genotipos con multiples cromosomas. Por ejemplo, los seres humanos tenemos 23 pares de cromosomas diploides.
Para adoptar una estructura similar en los algoritmos geneticos necesitamos extender la representacion a fin de permitir que un genotipo sea una lista de k pares
de cadenas (asumiendo que son diploides).
Pero, para que tomarnos estas molestias?
Holland [127] sugirio que los genotipos con multiples cromosomas podran
ser u tiles para extender el poder de los algoritmos geneticos cuando se usan en
combinacion con 2 operadores: la segregacion y la traslocacion.
13.3.1 Segregacion
Para entender como funciona este operador, imaginemos el proceso de formacion
de gametos cuando tenemos mas de un par cromosomico en el genotipo. La cruza
se efectua igual que como vimos antes, pero cuando formamos un gameto, tenemos que seleccionar aleatoriamente uno de los cromosomas haploides.
A este proceso de seleccion aleatoria se le conoce como segregacion. Este
proceso rompe cualquier enlace que pueda existir entre los genes dentro de un
cromosoma, y es u til cuando existen genes relativamente independientes en cromosomas diferentes.
13.3.2 Traslocacion
Puede verse como un operador de cruza intercromosomico. Para implementar este
operador en un algoritmo genetico necesitamos asociar los alelos con su nombre
genetico (su posicion), de manera que podamos identificar su significado cuando
se cambien de posicion de un cromosoma a otro mediante la traslocacion.
El uso de este operador permite mantener la organizacion de los cromosomas
de manera que la segregacion pueda explotar tal organizacion.
La segregacion y la traslocacion no se han usado mucho en la practica, excepto
por algunas aplicaciones de aprendizaje de maquina [198, 208].
246
Captulo 14
Aplicaciones Exitosas de la
Computacion Evolutiva
En este capitulo revisaremos brevemente algunas aplicaciones exitosas de la computacion evolutiva a problemas del mundo real. La intencion es mostrar el potencial de estas tecnicas en la solucion de problemas de norme complejidad.
de Peptidos
14.1 Diseno
Un equipo de Unilever Research ha usado algoritmos geneticos combinados con
redes neuronales para disenar nuevos peptidos bactericidas para usarse en limpiadores
anti-bacterianos y preservativos de alimentos.
Las redes neuronales se utilizaron para predecir la actividad bactericida en
los peptidos, y posteriormente se combinaron con algoritmos geneticos para optimizar peptidos virtuales. El resultado fue la generacion de mas de 400 bactericidas
virtuales potencialmente activos, de los cuales 5 fueron sintetizados.
una mejora relativamente pequena puede traer enormes ahorros a la larga, ya que
su impacto es acumulativo.
El uso de algoritmos geneticos en este problema produjo retornos netos substancialmente mejores que los producidos previamente por cualquier planeador
humano o por cualquier otra tecnica de optimizacion.
14.3 Prediccio n
La empresa holandesa Cap Gemini y la empresa britanica KiQ Ltd han desarrollado de forma conjunta un sistema llamado Omega,el cual usa algoritmos
geneticos para resolver problemas de mercadotecnia, credito y aplicaciones financieras relacionadas.
Omega usa como punto de partida un portafolio de comportamiento previo de
un cliente, ya partir de e l genera un modelo matematico que puede usarse posteriormente para predecir comportamientos de clientes que se encuentren fuera de los
portafolios conocidos. Este software puede utilizarse para evaluar solicitudes de
credito, generar listas de correo (para publicidad), modelar lealtad de los clientes
a un producto, y para detectar fraudes.
Recientemente, un banco holandes comparo Omega contra su sistema de asignacion de credito tradicional (basado en sistemas expertos), encontrando que Omega
era substancialmente superior tanto en cantidad (ofreca mas prestamos) como en
calidad (se reduca el riesgo en los creditos) de los prestamos evaluados.
de un Sistema de Suspensi o n
14.4 Diseno
Investigadores del KanGAL, el Laboratorio de Algoritmos Geneticos de Kanpur, en la India, han utilizado esta tecnica para disenar un sistema de suspension
para un automovil que es mas comodo que el previamente utilizado por una empresa automotriz reconocida mundialmente.
Utilizando un modelo tridimensional de un automovil, estos investigadores
optimizaron el diseno de los amortiguadores y los resortes de rigidez del vehculo.
Las simulaciones efectuadas muestran que el sistema generado por el algoritmo
genetico hace que los pasajeros sufran menor aceleracion vertical, de manera que
se disfruta de un mayor confort que con los sistemas utilizados previamente por
el fabricante de automoviles en cuestion.
248
Combinando las demas variantes del problema (p.ej. ubicacion de las estaciones de bombeo, etc.) se estimo que el tamano del espacio de busqueda
era de aproximadamente |(}~" . Este numero es superior a la cantidad de
a tomos en el universo.
Antes de intentar resolver este problema, se recurrio a un analisis que incluyo
lo siguiente:
{
hasta el ano 2011, y hubieron de extrapolarse los resultados para el ano 2031. El
costo estimado de la extension y reforzamiento de la red de agua potable fue de
$150 millones de dolares.
Usando la informacion disponible, se procedio entonces a utilizar GAnet, que
es una biblioteca de clases para desarrollar algoritmos geneticos. GAnet incluye
rutinas para simular redes hidraulicas y permite el manejo de restricciones duras
y blandas.
{
GAnet propuso lo siguiente:
{
{
Se le recomienda consultar:
1
Hay varios criterios para definir convergencia nominal. Uno que suele adoptarse es el de la
similitud genotpica. Cuando la mayora de los individuos en la poblacion son muy similares al
nivel genotipo, puede decirse que se alcanzo convergencia nominal
252
{
Mitsuo Gen and Runwei Cheng, Genetic Algorithms & Engineering
Optimization, Wiley Series in Engineering Design and Automation.
{
John Wiley & Sons, New York, 2000.
Lawrence Davis (editor), Handbook of Genetic Algorithms, Van Nostrand Reinhold, New York, New York, 1991.
Thomas Back, David B. Fogel & Zbigniew Michalewicz (editor), Handbook of Evolutionary Computation, Institute of Physics Publishing and
Oxford University Press, New York, 1997.
3. Investigue sobre posibles aplicaciones de la computacion evolutiva a problemas de su comunidad. Identifique posibles problemas y la forma en que
e stos se resolveran usando algoritmos geneticos.
253
254
Captulo 15
AGs Paralelos
15.1 Nociones de Paralelismo
Podemos definir el procesamiento en paralelo como la ejecucion concurrente (o
simultanea) de instrucciones en una computadora. Dicho procesamiento puede
ser en la forma de eventos que ocurran [152]:
1. durante el mismo intervalo de tiempo
2. en el mismo instante
3. en intervalos de tiempo traslapados
La motivacion mas obvia del paralelismo es el incrementar la eficiencia de
procesamiento.
Existen muchas aplicaciones que demandan grandes cantidades de tiempo de
procesamiento y que, por ende, resultan beneficiadas de contar con arquitecturas
en paralelo.
Una de las frecuentes confusiones respecto al paralelismo es que se cree que
al contar con una computadora que tenga procesadores trabajando en el mismo
problema, e ste podra resolverse veces mas rapido. Esto es falso.
Al usar varios procesadores para una misma tarea, debemos tomar en cuenta
que { existiran:
De estos 2 lmites puede inferirse facilmente que no resulta u til agregar mas y
mas procesadores, si lo que queremos es hacer mas rapida a una computadora.
La eficiencia de un sistema de computo se mide en terminos de sus capacidades tanto en hardware como en software. A dicha medida de eficiencia se le
conoce como rendimiento total (throughput) y se define como la cantidad de
procesamiento que puede realizarse en un cierto intervalo de tiempo.
Una tecnica que ha conducido a incrementos notables del rendimiento total de
un sistema de computo es el proceso de encauzamiento (pipelining).
Este proceso de encauzamiento es analogo a una lnea de ensamblaje en una
planta industrial. Una funcion a ejecutarse por una computadora es dividida en
sub-funciones mas pequenas, y se disena hardware separado (llamado etapa) para
cada una de estas subfunciones. Estas etapas estan conectadas entre s, de manera
que forman un solo cauce (o pipeline) que realiza la funcion original.
256
CPU
maestro
Poblacion
S
...
...
Seleccion
Cruza
Mutacion
Aptitud
Estructura de Interconexion
Cada EP
tiene una
memoria
local
EP
EP
Pob1
Pob2
...
EP
Elementos de
procesamiento
Pob3
Poblaciones o
demes
A los AGs de grano grueso se les suele llamar tambien AGs distribuidos,
porque suelen implementarse en computadoras MIMD con memoria distribuida.
Asimismo, algunos autores los llaman tambien AGs de isla, haciendo alusion a
un modelo poblacional usado en genetica en el cual se consideran demes relativamente aislados. A este modelo se le conoce como modelo de isla.
Los
AGs de grano grueso son muy populares debido a varias razones:
{
Son una extension muy simple de los AGs seriales. Simplemente se toman
unos cuantos AGs convencionales (seriales), se corre cada uno de ellos en
un procesador diferente y, a ciertos intervalos de tiempo, se intercambian
{ unos cuantos individuos entre ellos.
Aunque no se tenga acceso a una arquitectura paralela, puede implementarse un AG de grano grueso a traves de una simulacion efectuada en una
red de estaciones de trabajo, o incluso en una computadora con un solo
procesador haciendo la simulacion mediante software (usando por ejemplo
{ MPI o PVM).
Se requiere relativamente de poco esfuerzo para convertir un AG serial en
un AG de grano grueso. La mayor parte de la programacion permanece
igual, y solo se requieren ciertas rutinas adicionales para implementar la
migracion.
Los
parametros que requieren los AGs de grano grueso son:
{
De entre estos parametros, algunos como la topologa, juegan un papel preponderante en el desempeno del AG. La topologa determina que tan rapido (o
que tan lentamente) se disemina una buena solucion hacia los otros demes.
Si se usa una topologa dispersamente conectada (con un diametro grande), las
soluciones se diseminaran mas lentamente y los demes estaran mas aislados entre
s, permitiendo la aparicion de soluciones diferentes, favoreciendo probablemente
la diversidad.
La topologa juega tambien un papel preponderante en el costo de las migraciones. Por ejemplo, una topologa densamente conectada puede promover una
mejor mezcla de individuos, pero a un costo computacional mas alto.
Se sabe, por ejemplo, que una topologa densa tiende a encontrar soluciones
globales con un menor numero de evaluaciones de la funcion de aptitud que si se
usa una topologa dispersa.
Tambien es posible usar topologas din a micas, en las que los demes no estan
limitados a poder comunicarse solo con un cierto conjunto predefinido de demes,
sino que enva sus migrantes a aquellos demes que satisfacen ciertos criterios.
La idea de este esquema es que puedan identificarse los demes donde los migrantes tienen mayores probabilidades de producir algun efecto. Usualmente, se
usa la diversidad como el criterio principal para definir que tan adecuado es un
cierto deme.
Es importante mantener en mente la idea de que una topologa es una estructura logica que puede diferir de la estructura de hardware disponible. Es decir,
la topologa de un AG paralelo no necesariamente debe coincidir con la de nuestra computadora. El problema de hacer esto, sin embargo, es que los costos de
comunicacion resultantes pueden ser muy elevados.
Relacionado con las topologas se encuentra el concepto de vecindario.
El vecindario se refiere al a rea dentro de la cual puede moverse un migrante
de un cierto deme.
Asociado al vecindario se encuentra el concepto de radio de seleccion, que se
refiere a la cantidad de vecinos entre los cuales se puede efectuar la seleccion. Es
comun usar un radio de seleccion de cero, o sea, efectuar la seleccion solo dentro
del mismo deme, aunque cualquier otro valor es valido.
Es comun usar vecindarios compactos en computacion evolutiva, motivados
por el hecho de qe en la naturaleza, las poblaciones estan limitadas geograficamente.
En AGs paralelos, es facil definir vecindarios compactos, y de ah que sean
tan populares en computacion evolutiva.
261
262
264
Unidad de
control
UC
EP
EP
Mem
Mem
...
...
EP
Mem
Elementos de
Procesamiento
Memoria
{ de toroide.
Esta arquitectura (SIMD) suele usarse para AGs de grano fino (o sea, para
266
2. Probabilidad de migracion: cual es la probabilidad de aceptar a un migrante en un cierto deme (suelen usarse valores altos, p.ej. 0.8)?
Los puntos importantes relacionados con la migracion son 2:
1. A quien importar en una poblacion?
2. A quien reemplazar en una poblacion?
Existen
varios criterios para llevar a cabo estas 2 operaciones:
{
UC
UC
UC
Estructura
de
Interconexion
UC
. . .
UC
UC = Unidad de Control
Global
Migracion
Local
Figura 15.10: Una topologa que suele usarse con las arquitecturas MIMD es la
de a rbol.
268
Busqueda
local
Busqueda
global
1
direccion
de la
mutacion
Mas
disruptiva
Menos
disruptiva
{ busqueda.
Otra posibilidad para una arquitectura MIMD es usar una topologa de anillo
como la mostrada en la figura 15.11.
En este tipo de topologa, la busqueda puede hacerse mas local cambiando la
precision de la representacion.
Otra posibilidad es usar una topologa de grafo con z interconexiones, o una
topologa de estrella, como las que se muestran en la figura 15.12.
269
IS
15.2.6 Metricas
Otro punto interesante relacionado con los AGs paralelos son las m e tricas.
Normalmente,
se consideran 2 de las metricas usadas con AGs simples:
{
Velocidad de convergencia: Tiempo (generaciones) en alcanzar el o ptimo.
|. X
l
= Longitud cromosomica.
= numero de demes.
no de cada deme.
n=,tama
= diversidad.
{ mas.
{
Una
alternativa viable es:
{ Escoger varios esquemas de antemano.
Hacer que la propagacion de esquemas sea la fraccion maxima de demes en
la cual aparece un esquema.
271
272
Captulo 16
Tecnicas Evolutivas Alternativas
En este captulo discutiremos brevemente algunos de los paradigmas emergentes
dentro de la computacion evolutiva. Nuestra discusion se centrara fundamentalmente
{ en las tecnicas siguientes:
{ Evolucion Diferencial
{ Modelos Probabilsticos
Evolucion Simulada
A menor bondad de un cierto elemento, mayor sera su probabilidad de ser seleccionado. Se usa un parametro adicional para compensar las posibles imprecisiones
de la medida de bondad.
Finalmente, el paso de asignacio n intenta asignar los elementos seleccionados
a mejores posiciones.
Ademas de los 3 pasos antes mencionados, se fijan algunos parametros de
entrada para el algoritmo en un paso preliminar denominado inicializaci o n.
Para finalizar, vale la pena mencionar que hace algun tiempo, en la lista de
distribucion GA-Digest se discutieron ampliamente los temas de investigacion
considerados como mas importantes en los anos por venir. Tras un intenso debate, se concluyo que las 3 preguntas mas importantes que debieran atacarse por
los investigadores de computacion evolutiva en los proximos anos para lograr la
madurez del a rea son las siguientes:
1. A que tipo de problemas deben aplicarse los algoritmos evolutivos?
2. Como podemos mejorar nuestra comprension del funcionamiento de los
algoritmos evolutivos?
3. Que nuevas ideas pueden aplicarse a la computacion evolutiva a fin de
extender el paradigma (p.ej., inspiracion biologica)?
277
Indice
Analtico
a cido desoxirribonucleico, 83
a rboles, 105
ActiveGA, 213
adaptacion
mecanismos, 185
adenina, 83
ADN, 83
AG de grano fino, 263
problemas, 263
AG de grano grueso
parametros, 260
AG de isla, 260
AG desordenado, 103
aplicaciones, 104
AG distribuido, 260
AG panmtico, 259
AG paralelo
esquemas hbridos, 263
AGs de grano grueso, 259
AGs paralelos
hbridos, 263
metricas, 270
ajuste de parametros, 175
alelo, 75, 84, 91, 97
algoritmo
analisis, 24
complejidad, 24
algoritmo cultural, 80
algoritmo evolutivo de estado uniforme,
131
algoritmo genetico, 60, 74
278
paisaje de, 91
arquitectura masiva en paralelo, 263
arquitecturas
paralelas, 265
asncrono
AG paralelo, 259
auto-adaptacion, 276
estrategia evolutiva, 72
codificacion real, 99
coevolucio n, 276
Combinacion
Teora de la, 46
competencia, 51, 88
complejidades de algoritmos, 25
computacion evolutiva
aplicaciones, 247
crticas, 79
futuro, 276
las 3 grandes preguntas, 277
orgenes, 52
paradigmas, 67
programacion de horarios, 249
computadora IAS, 56
concavidad, 35
Conrad, Michael, 61
constructor
bloque, 97
constructores
hipo tesis de, 223
convergencia
en AGs paralelos, 270
convergencia colateral, 228
convexidad, 35
Cope, Edward Drinker, 44
corte, 104
Cramer, Nichael Lynn, 62
Creacionismo, 41
Cromosomica
Teora, 50
cromosoma, 75, 84, 89, 96
Crosby, J. L., 53
cruza, 93, 141
comportamiento deseable, 149
de dos puntos, 141
de un punto, 141
efecto de, 221
programacion genetica, 149
representacion real, 157
279
sesgos, 147
uniforme, 141
cruza acentuada, 145
cruza aritmetica simple
representacion real, 159
cruza aritmetica total
representacion real, 160
cruza biolo gica, 141
cruza con barajeo, 148
cruza de dos puntos, 143
representacion real, 158
cruza de un punto
analisis, 143
problemas, 141
cruza intermedia
representacion real, 159
cruza para permutaciones, 151
cruza simple, 158
cruza uniforme, 145, 149
representacion real, 158
cruza vs. mutacion, 173
cultural
algoritmo, 80
cycle crossover, 155
descenso empinado, 27
descentralizada
arquitectura, 267
desvo genetico, 66, 88
determinstico, 25
DeVries, Hugo, 50
DGenesis, 209
dimensionalidad
maldicio n de la, 104
dinamica evolutiva, 64
diploide, 85
ejemplo, 243
diploides, 241
diseno de peptidos, 247
dispersa
busqueda, 80
distribucio n geometrica
seleccion, 134
distribucional
sesgo, 147
diversidad, 270
metricas, 271
divisio n protegida, 108
dominancia, 241
ecosistemas artificiales, 61
efecto Baldwin, 64
efecto de la cruza, 221
efecto de la mutacion, 222
efecto de la seleccion, 221
ejecucion, 110
El Origen de las Especies, 44
El origen de las especies, 46
elitismo, 93
elitismo global, 129
encapsulamiento, 110
encauzamiento
proceso, 256
ENCORE, 212
Engineering Design Centre, 251
280
engrama, 89
epstasis, 53, 89, 92, 98
escalamiento sigma, 116, 122
escalando la colina, 35
ESCaPaDE, 210
especiacion, 88, 92
especie, 88
esperma, 84
esquema, 54, 94, 217
longitud de definicion, 142
orden, 142
velocidad de propagacion, 270
esquema candidato, 104
esquemas
cantidad de, 96
teorema de, 221
esquemas diferentes, 218
estado uniforme
algoritmo evolutivo, 131
estancamiento, 55
estimation of distribution algorithms, 274
estrategia evolutiva, 70
algoritmo, 70
aplicaciones, 73
auto-adaptacion, 72
comparada con la programacion evolutiva, 73
ejemplo, 70
recombinacio n panmtica, 73
recombinacio n sexual, 73
regla de 1/5, 71
regla de 1/7, 72
estrategia evolutiva de dos miembros, 70
estrategia evolutiva multi-miembro, 71
estrategias de produccion
optimizacion, 247
estrategias evolutivas, 58
estructurado
algoritmo genetico, 111
etapa, 256
evolucion, 51
evolucion diferencial, 273
comparacion con un algoritmo genetico,
274
evolucion simulada, 275
Evolucionismo, 41
Evolutionary Operation (EVOP), 54
evolutiva
programacion, 54
Evolver, 213
EVOP, 54
Ewan Associates, 250
Exeter
Universidad, 250
exploracion, 94
explotacion, 94
expresiones-S, 112
fase primordial, 104
fase yuxtaposicional, 104
fenotipo, 45, 85, 91
fertilidad, 87
Flynn, Michael J., 257
Fogel, Lawrence J., 68
FORTRAN, 210, 252
Fraser, Alexander S., 52
frecuencia
de exportacion, 269
Friedberg, R. M., 54
Fujiki, C., 62
GAcal, 250
GALOPPS, 209
Galton, Francis, 48
GAME, 112
gameto, 85
GAnet, 250
GANNET, 211
GAser, 250
GECO, 209
gene, 75, 84, 89, 97
281
Haeckel, Ernst, 44
Hamming
distancia, 269
riscos, 98
haploide, 85
haploides, 241
heurstica
definicio n, 33
heurstica greedy, 249
Hicklin, J. F., 62
KanGAL, 248
KiQ Ltd, 248
Koza, John, 105
Koza, John R., 62
Kuhn-Tucker
condiciones, 36
Lamarck, 43
282
MISD, 257
modelos probabilsticos, 274
MPI, 260
muerte
pena de, 193
muestreo determinstico, 121
Multiple Instruction Stream, Multiple Data
Stream, 257
Multiple Instruction Stream, Single Data
Stream, 257
multiprocesador, 263
Mutacion
Teora de la, 50
mutacion, 51, 93, 165
efecto de, 222
porcentajes o ptimos, 165
programacion genetica, 167
representacion real, 168
mutacion de lmite, 169
mutacion heurstica, 166
mutacion no uniforme, 168
mutacion por desplazamiento, 166
mutacion por insercion, 165
mutacion por intercambio recproco, 166
mutacion uniforme, 170
mutacion vs. cruza, 173
mutaciones espontaneas, 50
mutaciones variables, 185
metricas, 270
en AGs paralelos, 270
MacReady, William, 224
maldicion de la dimensionalidad, 104
Malthus, Thomas Robert, 46
Markov, cadenas de, 56
matching, 269
Mendel
leyes de la herencia, 48
Mendel, Johann Gregor, 44, 48, 50, 51
merge crossover, 157
mesh, 266
messy GA, 103
metamerismo, 276
Michalewicz, Zbigniew, 133, 211
micro algoritmo genetico, 180
micro-operadores, 245
MicroGA, 214
migracion, 88, 92, 259, 266
parametros, 267
probabilidad, 267
vecindario de, 266
MIMD, 257, 267
Minsky
conjetura, 256
Neo-Darwiniano
paradigma, 51
Neo-Darwinismo, 51
nicho, 92
nicho ecolo gico, 88
no convexidad, 35
No Free Lunch Theorem, 224
notacion big-O, 24
notacion del IEEE, 100
NP, 25
NP completos
283
problemas, 26
nucleo tidos, 83
Omega, 248
On the Variation of Animals and Plants
under Domestication, 48
operador de interseccion, 157
Optimal Solutions, 250
optimizacion
tecnicas clasicas, 27
optimizacion combinatoria, 38
orden
de un esquema, 142
order crossover, 152
order-based crossover, 154
ovarios, 84
OX, 153
peptidos
optimizacion, 247
paisaje de aptitud, 91
Pangenesis
Teora de la, 48
paralelismo, 92, 276
motivacion, 255
nociones, 255
paralelismo implcito, 54, 179, 219, 258
paralelizacio n explcita, 258
paralelizacio n global, 258
parameter-based mutation, 171
partially mapped crossover, 153
Pattee, Howard H., 61
PC-Beagle, 213
pena de muerte, 193
penalizacion
adaptativa, 195
algoritmo genetico segregado, 196
basada en factibilidad, 196
dinamica, 194
estatica, 193
funcio n de, 191
284
ejecucion, 110
encapsulamiento, 110
funciones, 106
mutacio n, 108, 167
permutacion, 108
simplificacion, 110
terminales, 106
PVM, 260
problemas, 97
representacion de punto fijo, 101
representacion entera, 102
representacion real
cruza, 157
mutacion, 168
reproduccion, 51, 88
asexual, 88
operadores de, 93
sexual, 88
reproduccion sexual, 85
caso diploide, 87
caso haploide, 85
restricciones, 191
restricciones explcitas, 37
restricciones implcitas, 37
Reynolds, Robert G., 80
riscos de Hamming, 98, 101
Russell Wallace, Alfred, 45, 46
Quadstone, 247
radio de seleccion, 261
Ray, Thomas S., 64
Rechenberg, Ingo, 58, 70
recocido simulado, 35, 125, 194
recombinacion panmtica
estrategia evolutiva, 73
recombinacion respetuosa aleatoria, 149
recombinacion sexual, 53
estrategia evolutiva, 73
red de agua potable, 249
redes neuronales
hbridos con AGs, 247
Reed, J., 56
REGAL, 212
regla de e xito 1/5, 71
regla de e xito 1/7, 72
rendimiento total, 256
reordenamiento, 93
representacion
a rboles, 105
algoritmo genetico, 95
de longitud variable, 103
gramaticas, 112
hbrida, 112
jerarquica, 111
matricial, 112
permutaciones, 112
recomendaciones, 113
tendencias futuras, 112
representacion binaria, 96
sncrono
AG paralelo, 259
Saint-Hilaire, Etienne
Geoffroy, 43
Savic, Dragan, 250
SBX, 161
Schaffer
estudio, 180
Schwefel, Hans-Paul, 58, 71
SCS-C, 213
segregacion, 53, 245
segregado
algoritmo genetico, 196
seleccion, 51, 87
blanda, 87
de estado uniforme, 115
dura, 87
efecto, 221
extintiva, 115
metodos dinamicos, 135
metodos estaticos, 135
285
sistema de suspension
optimizacion, 248
sistemas clasificadores, 55, 131
Smalltalk, 212
sobrante estocastico, 117
con reemplazo, 119
sin reemplazo, 119
sobre-especificacion, 103
software, 207
bibliotecas, 207
cajas de herramientas, 207
especfico, 207
orientado a las aplicaciones, 207
orientado a los algoritmos, 207
sistemas de proposito general, 208
sistemas educativos, 207
somatoplasma, 44
stagnation, 55
steepest descent, 27
StruMap, 249
sub-especificacion, 103
subpoblacion, 92
sustitucion reducida, 148
Sutton, Walter, 50
tabu
busqueda, 34
Tac Tix, 56
tamano o ptimo de poblacion, 178
teora
a reas abiertas de investigacion, 225
teora cromosomica de la herencia, 50
teorema de los esquemas, 220, 222
crticas, 223
terminales, 106
throughput, 256
Tierra, 64
Toombs, R., 56
topologa, 261
de anillo, 269
286
de estrella, 270
de grafo, 270
densa, 261
dispersa, 261
topologa dinamica, 261
torneo
seleccion mediante, 126
toroide, 266
traslocacion, 245
Turing, Alan Mathison, 52
union, 104
Unilever Research, 247
universal estocastica, 119
Universidad de Exeter, 250
Universidad de Plymouth, 251
variables de decision, 37
varianza
elevada de la aptitud, 228
variedad requisito, 93
vecindario, 261
migracion, 266
vecindarios compactos, 261
vectoriales
instrucciones, 257
velocidad
de convergencia, 270
de propagacion de los esquemas, 270
viabilidad, 87
vida artificial, 56
von Neumann, John, 56
Walsh
transformada, 227
Weismann, August, 44
derrumba la teora Lamarckista, 44
teora del germoplasma, 44
Weissman, August, 51
Whitley
Darrell, 129
287
288
Bibliografa
[1] David H. Ackley. A Connectionist Machine for Genetic Hillclimbing. Kluwer
Academic Publishers, Boston, Massachusetts, 1987.
[2] C. A. Anderson, K. F. Jones, and J. Ryan. A two-dimensional genetic algorithm
for the ising problem. Complex Systems, 5:327333, 1991.
[3] Peter J. angeline and Jordan B. Pollack. Competitive Environments Evolve Better
Solutions for Complex Tasks. In Stephanie Forrest, editor, Proceedings of the Fifth
International Conference on Genetic Algorithms. Morgan Kaufmann Publishers,
San Mateo, California, July 1993.
[4] Hendrik James Antonisse. A Grammar-Based Genetic Algorithm. In Gregory E.
Rawlins, editor, Foundations of Genetic Algorithms, pages 193204. Morgan Kaufmann Publishers, San Mateo, California, 1991.
[5] Wirt Atmar. Notes on the Simulation of Evolution. IEEE Transactions on Neural
Networks, 5(1):130148, January 1994.
[6] Thomas Back. Self-adaptation in genetic algorithms. In F.J. Varela and P. Bourgine,
editors, Proceedings of the First European Conference on Artificial Life, pages
263271, Cambridge, Massachusetts, 1992. MIT Press.
[7] Thomas Back. Optimal Mutation Rates in Genetic Search. In Stephanie Forrest,
editor, Proceedings of the Fifth International Conference on Genetic Algorithms,
pages 28. Morgan Kaufmann Publishers, San Mateo, California, July 1993.
[8] Thomas Back. Selective Pressure in Evolutionary Algorithms: A Characterization of Selection Mechanisms. In Proceedings of the First IEEE Conference on
Evolutionary Computation, pages 5762, Orlando, Florida, 1994. IEEE.
[9] Thomas Back. Evolutionary Algorithms in Theory and Practice. Oxford University
Press, New York, 1996.
289
[10] Thomas Back, David B. Fogel, and Zbigniew Michalewicz, editors. Handbook of
Evolutionary Computation. Institute of Physics Publishing and Oxford University
Press, New York, 1997.
[11] Thomas Back and Frank Hoffmeister. Extended Selection Mechanisms in Genetic
Algorithms. In Richard K. Belew and Lashon B. Booker, editors, Proceedings of
the Fourth International Conference on Genetic Algorithms, pages 9299. Morgan
Kaufmann Publishers, San Mateo, California, July 1991.
[12] Thomas Back, Frank Hoffmeister, and Hans-Paul Schwefel. A Survey of Evolution
Strategies. In R. K. Belew and L. B. Booker, editors, Proceedings of the Fourth International Conference on Genetic Algorithms, pages 29, San Mateo, California,
1991. Morgan Kaufmann Publishers.
[13] James Edward Baker. Adaptive Selection Methods for Genetic Algorithms. In
John J. Grefenstette, editor, Proceedings of the First International Conference
on Genetic Algorithms, pages 101111. Lawrence Erlbaum Associates, Hillsdale,
New Jersey, July 1985.
[14] James Edward Baker. Reducing Bias and Inefficiency in the Selection Algorithm.
In John J. Grefenstette, editor, Genetic Algorithms and Their Applications: Proceedings of the Second International Conference on Genetic Algorithms, pages
1422. Lawrence Erlbaum Associates, Hillsdale, New Jersey, July 1987.
[15] James Mark Baldwin. Development and Evolution: Including Psychophysical Evolution, Evolution by Orthoplasy and the Theory of Genetic Modes. Macmillan, New
York, 1902.
[16] Nils Aall Barricelli. Esempi numerici di processi di evoluzione. Methodos, pages
4568, 1954.
[17] Nils Aall Barricelli. Symbiogenetic evolution processes realized by artificial methods. Methodos, IX(3536):143182, 1957.
[18] Nils Aall Barricelli. Numerical Testing of Evolution Theories. Part I: Theoretical
Introduction and Basic Tests. Acta Biotheoretica, 16(12):6998, 1962.
[19] Nils Aall Barricelli. Numerical Testing of Evolution Theories. Part II: Preliminary
Tests of Performance, Symbiogenesis and Terrestrial Life. Acta Biotheoretica,
16(34):99126, 1964.
[20] James C. Bean. Genetics and random keys for sequencing and optimization. ORSA
Journal on Computing, 6(2):154160, 1994.
290
291
[33] Bill P. Buckles and Frederick E. Petry, editors. Genetic Algorithms. Technology
Series. IEEE Computer Society Press, 1992.
[34] T. N. Bui and B. R. Moon. On multidimensional encoding/crossover. In Larry J.
Eshelman, editor, Proceedings of the Sixth International Conference on Genetic
Algorithms, pages 4956, San Fracisco, California, 1995. Morgan Kauffman Publishers.
[35] G. H. Burgin. On playing two-person zero-sum games against non-minimax players. IEEE Transactions on Systems Science and Cybernetics, SSC-5:369370,
1969.
[36] A. W. Burks. Computation, behavior and structure in fixed and growing automata.
In M. C. Yovits and S. Cameron, editors, Self-Organizing Systems, pages 282309.
Pergamon Press, New York, 1960.
[37] Eduardo Camponogara and Sarosh N. Talukdar. A Genetic Algorithm for Constrained and Multiobjective Optimization. In Jarmo T. Alander, editor, 3rd Nordic
Workshop on Genetic Algorithms and Their Applications (3NWGA), pages 4962,
Vaasa, Finland, August 1997. University of Vaasa.
[38] W. D. Cannon. The Wisdom of the Body. Norton and Company, New York, 1932.
[39] Erick Cantu-Paz. A Survey of Parallel Genetic Algorithms. Technical Report
97003, Illinois Genetic Algorithms Laboratory, University of Illinois at UrbanaChampaign, Urbana, Illinois, May 1997.
[40] R. Caruana and J. D. Schaffer. Representation and Hidden Bias: Gray vs. Binary
Coding for Genetic Algorithms. In Proceedings of the Fifth International Conference on Machine Learning, pages 132161, San Mateo, California, 1988. Morgan
Kauffman Publishers.
[41] Munirul M. Chowdhury and Yun Li.
Messy Genetic Algorithm
Based New Learning Method for Fuzzy Controllers.
In Proceedings of the IEEE International Conference on Industrial Technology,
page http://eeapp.elec.gla.ac.uk/chy/publications.html,
Shangai, China, December 1996. IEEE Service Center.
[42] Carlos A. Coello Coello, Alan D. Christiansen, and Arturo Hernandez Aguirre.
Automated Design of Combinational Logic Circuits using Genetic Algorithms.
In D. G. Smith, N. C. Steele, and R. F. Albrecht, editors, Proceedings of the International Conference on Artificial Neural Nets and Genetic Algorithms ICANNGA97, pages 335338, Norwich, England, April 1997. University of East Anglia, Springer-Verlag.
292
[43] Carlos A. Coello Coello, Alan D. Christiansen, and Arturo Hernandez Aguirre.
Using a New GA-Based Multiobjective Optimization Technique for the Design of
Robot Arms. Robotica, 16(4):401414, 1998.
[44] Carlos A. Coello Coello, Filiberto Santos Hernandez, and Francisco Alonso Farrera. Optimal Design of Reinforced Concrete Beams using Genetic Algorithms.
Expert Systems with Applications : An International Journal, 12(1):101108, January 1997.
[45] Carlos A. Coello Coello. Constraint-handling using an evolutionary multiobjective
optimization technique. Civil Engineering and Environmental Systems, 17:319
346, 2000.
[46] Carlos A. Coello Coello. Treating Constraints as Objectives for Single-Objective
Evolutionary Optimization. Engineering Optimization, 32(3):275308, 2000.
[47] Michael Conrad. Evolutionary learning circuits. Journal of Theoretical Biology,
46:167188, 1974.
[48] Michael Conrad. Algorithmic specification as a technique for computing with informal biological models. BioSystems, 13:303320, 1981.
[49] Michael Conrad. Natural selection and the evolution of neutralism. BioSystems,
15:8385, 1982.
[50] Michael Conrad, R. R. Kampfer, and K. G. Kirby. Neuronal dynamics and evolutionary learning. In M. Kochen and H. M. Hastings, editors, Advances in Cognitive
Science: Steps Towards Convergence, pages 169189. American Association for
the Advancement of Science, New York, 1988.
[51] Michael Conrad and H. H. Pattee. Evolution experiments with an artificial ecosystem. Journal of Theoretical Biology, 28:393409, 1970.
[52] Michael Conrad and M. M. Rizki. The artificial worlds approach to emergent
evolution. BioSystems, 23:247260, 1989.
[53] Michael Conrad and M. Strizich. Evolve II: A computer model of an evolving
ecosystem. BioSystems, 17:245258, 1985.
[54] F. N. Cornett. An Application of Evolutionary Programming to Pattern Recognition. Masters thesis, New Mexico State University, Las Cruces, New Mexico,
1972.
293
[55] Nareli Cruz Cortes. Uso de emulaciones del sistema inmune para manejo de restricciones en algoritmos evolutivos. Masters thesis, Universidad Veracruzana,
Xalapa, Mexico, 2000.
[56] Nichal Lynn Cramer. A Representation for the Adaptive Generation of Simple Sequential Programs. In John J. Grefenstette, editor, Proceedings of the First International Conference on Genetic Algorithms and Their Applications, pages 183187.
Lawrence Erlbaum Associates, Hillsdale, New Jersey, 1985.
[57] J. L. Crosby. Computers in the study of evolution. Science Progress Oxford,
55:279292, 1967.
[58] Charles Robert Darwin. The Variation of Animals and Plants under Domestication.
Murray, London, second edition, 1882.
[59] Charles Robert Darwin. On the Origin of Species by Means of Natural Selection Or
the Preservation of Favoured Races in the Struggle for Life. Cambridge University
Press, Cambridge, UK, sixth edition, 1964. Originally published in 1859.
[60] Dipankar Dasgupta and Douglas R. McGregor. Nonstationary Function Optimization using the Structured Genetic Algorithm. In Proceedings of Parallel Problem Solving from Nature (PPSN 2), pages 145154, Brussels, September 1992.
Springer-Verlag.
[61] Dipankar Dasgupta and Douglas R. McGregor. A more Biologically Motivated
Genetic Algorithm: The Model and some Results. Cybernetics and Systems: An
International Journal, 25(3):447469, May-June 1994.
[62] Lawrence Davis. Job Shop Scheduling with Genetic Algorithms. In John J. Grefenstette, editor, Proceedings of the First International Conference on Genetic Algorithms, pages 136140. Lawrence Erlbaum Associates, Hillsdale, New Jersey, July
1985.
[63] Lawrence Davis. Adapting Operator Probabilities In Genetic Algorithms. In
J. David Schaffer, editor, Proceedings of the Third International Conference on
Genetic Algorithms, pages 6169, San Mateo, California, 1989. Morgan Kaufmann
Publishers.
[64] Lawrence Davis, editor. Handbook of Genetic Algorithms. Van Nostrand Reinhold,
New York, New York, 1991.
[65] Kalyanmoy Deb. GeneAS: A Robust Optimal Design Technique for Mechanical
Component Design. In Dipankar Dasgupta and Zbigniew Michalewicz, editors,
Evolutionary Algorithms in Engineering Applications, pages 497514. SpringerVerlag, Berlin, 1997.
294
[66] Kalyanmoy Deb. An Efficient Constraint Handling Method for Genetic Algorithms. Computer Methods in Applied Mechanics and Engineering, 1999. (in
Press).
[67] Kalyanmoy Deb and Ram Bhushan Agrawal. Simulated Binary Crossover for Continuous Search Space. Complex Systems, 9:115148, 1995.
[68] Kalyanmoy Deb and David E. Goldberg. An Investigation of Niche and Species
Formation in Genetic Function Optimization. In J. David Schaffer, editor, Proceedings of the Third International Conference on Genetic Algorithms, pages 4250,
San Mateo, California, June 1989. George Mason University, Morgan Kaufmann
Publishers.
[69] D. Dumitrescu, B. Lazzerini, L.C. Jain, and A. Dumitrescu. Evolutionary Computation. CRC Press, Boca Raton, Florida, 2000.
[70] B. Dunham, D. Fridshal, and J. H. North. Design by natural selection. Synthese,
15:254259, 1963.
[71] B. Dunham, H. Lewitan, and J. H. North. Introduction of artificial data to enable
natural selection scoring mechanism to handle more complex cases. IBM Technical
Disclosure Bulletin, 17(7):2193, 1974.
[72] B. Dunham, H. Lewitan, and J. H. North. Simultaneous solution of multiple problems by natural selection. IBM Technical Disclusure Bulletin, 17(7):21912192,
1974.
[73] N. Eldredge and S. J. Gould. Punctuated Equilibria: An Alternative to Phyletic
Gradualism. In T. J. M. Schpf, editor, Models of Paleobiology, pages 8215. W. H.
Freeman, San Francisco, California, 1972.
[74] Larry J. Eshelman, Richard A. Caruana, and J. David Schaffer. Biases in the
Crossover Landscape. In J. David Schaffer, editor, Proceedings of the Third International Conference on Genetic Algorithms, pages 1019, San Mateo, California,
1989. Morgan Kaufmann Publishers.
[75] Larry J. Eshelman and J. David Schaffer. Preventing Premature Convergence in
Genetic Algorithms by Preventing Incest. In Richard K. Belew and Lashon B.
Booker, editors, Proceedings of the Fourth International Conference on Genetic
Algorithms, pages 115122, San Mateo, California, July 1991. Morgan Kaufmann
Publishers.
295
[76] Larry J. Eshelman and J. Davis Schaffer. Real-coded Genetic Algorithms and
Interval-Schemata. In L. Darrell Whitley, editor, Foundations of Genetic Algorithms 2, pages 187202. Morgan Kaufmann Publishers, San Mateo, California,
1993.
[77] Jose Ribeiro Filho. The GAME system (Genetic Algorithms Manipulation Environment). In IEE Colloquium on Applications of Genetic Algorithms, pages 2/1
2/4, London, UK, 1994. IEE.
[78] Michael J. Flynn. Very High-Speed Computing Systems. Proceedings of the IEEE,
54:19011909, 1966.
[79] Terence C. Fogarty. Varying the Probability of Mutation in the Genetic Algorithm.
In J. David Schaffer, editor, Proceedings of the Third International Conference on
Genetic Algorithms, pages 104109, San Mateo, California, 1989. Morgan Kaufmann Publishers.
[80] David B. Fogel. Evolutionary Computation. Toward a New Philosophy of Machine
Intelligence. The Institute of Electrical and Electronic Engineers, New York, 1995.
[81] David B. Fogel, editor. Evolutionary Computation. The Fossil Record. Selected
Readings on the History of Evolutionary Algorithms. The Institute of Electrical
and Electronic Engineers, New York, 1998.
[82] David B. Fogel and L. C. Stayton. On the Effectiveness of Crossover in Simulated
Evolutionary Optimization. BioSystems, 32:171182, 1994.
[83] Lawrence J. Fogel. On the organization of intellect. PhD thesis, University of
California, Los Angeles, California, 1964.
[84] Lawrence J. Fogel. Artificial Intelligence through Simulated Evolution. John Wiley,
New York, 1966.
[85] Lawrence J. Fogel. Artificial Intelligence through Simulated Evolution. Forty Years
of Evolutionary Programming. John Wiley & Sons, Inc., New York, 199.
[86] Lawrence J. Fogel, A. J. Owens, and M. J. Walsh. On the Evolution of Artificial
Intelligence. In Proceedings of the 5th National Sympsium on Human Factors in
Engineering, pages 6376. IEEE, San Diego, California, 1964.
[87] Lawrence J. Fogel, A. J. Owens, and M. J. Walsh. Artificial Intelligence through a
Simulation of Evolution. In M. Maxfield, A. Callahan, and L. J. Fogel, editors, Biophysics and Cybernetic Systems: Proceedings of the Second Cybernetic Sciences
Symposium, pages 131155. Spartan Books, Washington, D.C., 1965.
296
[88] B.R. Fox and M.B. McMahon. Genetic Operators for Sequencing Problems. In
Gregory J. E. Rawlins, editor, Foundations of Genetic Algorithms, pages 284300.
Morgan Kaufmann, San Mateo, California, 1991.
[89] A. S. Fraser. Simulation of Genetic Systems by Automatic Digital Computers I.
Introduction. Australian Journal of Biological Sciences, 10:484491, 1957.
[90] A. S. Fraser. Simulation of Genetic Systems by Automatic Digital Computers II.
Effects of Linkage on Rates of Advance Under Selection. Australian Journal of
Biological Sciences, 10:492499, 1957.
[91] A. S. Fraser. Simulation of Genetic Systems by Automatic Digital Computers VI.
Epistasis. Australian Journal of Biological Sciences, 13:150162, 1960.
[92] Alexander S. Fraser. The evolution of purposive behavior. In H. von Foerster, J. D.
White, L. J. Peterson, and J. K. Russell, editors, Purposive Systems, pages 1523.
Spartan Books, Washington, D.C., 1968.
[93] Alexander S. Fraser and D. Burnell. Computer Models in Genetics. McGraw-Hill,
New York, 1970.
[94] R. M. Friedberg. A Learning Machine: Part I. IBM Journal of Research and
Development, 2(1):213, 1958.
[95] R. M. Friedberg, B. Dunham, and J. H. North. A Learning Machine: Part II. IBM
Journal of Research and Development, 3:282287, 1959.
[96] G. J. Friedman. Digital simulation of an evolutionary process. General Systems:
Yearbook of the Society for General Systems Research, 4:171184, 1959.
[97] George J. Friedman. Selective Feedback Computers for Engineering Synthesis and
Nervous System Analogy. Masters thesis, University of California at Los Angeles,
February 1956.
[98] C. Fujiki. An evaluation of Hollands genetic operators applied to a program generator. Masters thesis, University of Idaho, Moscow, Idaho, 1986.
[99] Mitsuo Gen and Runwei Cheng. Genetic Algorithms & Engineering Optimization.
Wiley Series in Engineering Design and Automation. John Wiley & Sons, New
York, 2000.
[100] John S. Gero, Sushil J. Louis, and Sourav Kundu. Evolutionary learning of novel
grammars for design improvement. AIEDAM, 8(3):8394, 1994.
297
298
[113] David E. Goldberg and Jr. Robert Lingle. Alleles, Loci, and the Traveling Salesman Problem. In John J. Grefenstette, editor, Proceedings of the First International Conference on Genetic Algorithms and Their Applications, pages 154159.
Lawrence Erlbaum Associates, Hillsdale, New Jersey, 1985.
[114] David E. Goldberg and Philip Segrest. Finite Markov Chain Analysis of Genetic
Algorithms. In John J. Grefenstette, editor, Genetic Algorithms and Their Applications: Proceedings of the Second International Conference on Genetic Algorithms,
pages 18. Lawrence Erlbaum Associates, Hillsdale, New Jersey, July 1987.
[115] J. Grefenstette, R. Gopal, B. Rosmaita, and D. Gucht. Genetic algorithms for
the travelling salesman problem. In John J. Grefenstette, editor, Proceedings of
an International Conference on Genetic Algorithms and Their Applications, pages
160168, Hillsdale, New Jersey, 1985. Lawrence Erlbaum Associates.
[116] John J. Grefenstette. Optimization of Control Parameters for Genetic Algorithms.
IEEE Transactions on Systems, Man, and Cybernetics, SMC16(1):122128, Janury/February 1986.
[117] John J. Grefenstette. Deception Considered Harmful. In L. Darrell Whitley, editor,
Foundations of Genetic Algorithms 2, pages 7591. Morgan Kaufmann, San Mateo,
California, 1993.
[118] Frederic Gruau. Neural Network Synthesis using Cellular Encoding and the Genetic Algorithm. PhD thesis, Ecole Normale Superieure de Lyon, Lyon, France,
1994.
[119] D. Halhal, G. A. Walters, D. Ouazar, and D. A. Savic. Water Network Rehabilitation with a Structured Messy Genetic Algorithm. Journal of Water Resources
Planning and Management, ASCE, 123(3), May/June 1997.
[120] Jurgen Hesser and Reinhard Manner. Towards an Optimal Mutation Probability for
Genetic Algorithms. In H.-P. Schwefel and R. Manner, editors, Parallel Problem
Solving from Nature. 1st Workshop, PPSN I, pages 2332. Springer-Verlag. Leture
Notes in Computer Science Volume 496, Berlin, 1991.
[121] J. F. Hicklin. Application of the genetic algorithm to automatic program generation.
Masters thesis, University of Idaho, Moscow, Idaho, 1986.
[122] W. D. Hillis. Co-evolving parasites improves simulated evolution as an optimization procedure. In C. Langton, C. Taylor, J. Farmer, and S. Rasmussen, editors,
Artificial Life II, pages 313324. Addison-Wesley, Reading, Massachusetts, 1992.
299
300
[136] J. Joines and C. Houck. On the use of non-stationary penalty functions to solve
nonlinear constrained optimization problems with GAs. In David Fogel, editor,
Proceedings of the first IEEE Conference on Evolutionary Computation, pages
579584, Orlando, Florida, 1994. IEEE Press.
[137] A. K. De Jong. An Analysis of the Behavior of a Class of Genetic Adaptive Systems.
PhD thesis, University of Michigan, 1975.
[138] Kenneth A. De Jong. Genetic Algorithms are NOT Function Optimizers. In L. Darrell Whitley, editor, Foundations of Genetic Algorithms 2, pages 517. Morgan
Kaufmann Publishers, San Mateo, California, 1993.
[139] Kenneth A. De Jong, William M. Spears, and Diana F. Gordon. Using Markov
Chains to Aanalyze GAFOs. In L. Darrell Whitley and Michael D. Vose, editors,
Foundations of Genetic Algorithms 3, pages 115137. Morgan Kaufmann Publishers, San Mateo, California, 1994.
[140] Joe L. Blanton Jr. and Roger L. Wainwright. Multiple Vehicle Routing with Time
and Capacity Constraints using Genetic Algorithms. In Stephanie Forrest, editor, Proceedings of the Fifth International Conference on Genetic Algorithms,
pages 452459, San Mateo, California, 1993. University of Illinois at UrbanaChampaign, Morgan Kauffman Publishers.
[141] Isamu Kajitani, Tsutomu Hoshino, Masaya Iwata, and Tetsuya Higuchi. Variable
length chromosome GA for Evolvable Hardware. In Proceedings of the 1996 IEEE
International Conference on Evolutionary Computation, pages 443447, Nagoya,
Japan, May 1996. Nagoya University, IEEE Service Center.
[142] S. Kirkpatrick, Jr. C. D. Gelatt, and M. P. Vecchi. Optimization by Simulated
Annealing. Science, 220:671680, 1983.
[143] Ralph Michael Kling. Optimization by Simulated Evolution and its Application to
Cell Placement. PhD thesis, University of Illinois at Urbana-Champaign, Urbana,
Illinois, 1990.
[144] John R. Koza. Hierarchical genetic algorithms operating on populations of computer programs. In N. S. Sridharan, editor, Proceedings of the 11th International
Joint Conference on Artificial Intelligence, pages 768774. Morgan Kaufmann,
San Mateo, California, 1989.
[145] John R. Koza. Genetic Programming. On the Programming of Computers by Means
of Natural Selection. The MIT Press, Cambridge, Massachusetts, 1992.
301
[146] John R. Koza. Genetic Programming II: Automatic Discovery of Reusable Programs. The MIT Press, Cambridge, Massachusetts, 1994.
[147] John R. Koza, Forrest H. Bennet III, David Andre, and Martin A. Keane. Genetic
Programming III: Darwinian Invention and Problem Solving. Morgan Kaufmann
Publishers, San Francisco, California, 1999.
[148] K. Krishnakumar. Mico-genetic algorithms for stationary and non-stationary function optimization. SPIE Proceedings: Intelligent Control and Adaptive Systems,
1196:289296, 1989.
[149] Ting Kuo and Shu-Yuen Hwang. A Genetic Algorithm with Disruptive Selection.
In Stephanie Forrest, editor, Proceedings of the Fifth International Conference on
Genetic Algorithms, pages 6569. Morgan Kaufmann Publishers, San Mateo, California, July 1993.
[150] Jean Baptiste Lamarck, editor. Zoological Philosophy: An Exposition with Regard to the Natural History of Animals. Chicago University Press, Chicago, 1984.
(Publicado originalmente en 1809 en frances, como Philosophie Zoologique).
[151] Christopher G. Langdon, editor. Artificial Life. Addison-Wesley Publishing Company, Reading, Massachusetts, 1989.
[152] Gideon Langholz, Joan Francioni, and Abraham Kandel. Elements of Computer
Organization. Prentice Hall, Englewood Cliffs, New Jersey, 1989.
[153] B. R. Levin. Simulation of genetic systems. In N. E. Morton, editor, Computer Applications in Genetics, pages 3848. University of Hawaii Press, Honolulu, 1969.
[154] Andrew J. Mason. Crossover non-linearity ratios and the genetic algorithm : Escaping the blinkers of schema processing and intrinsic parallelism. Technical Report
535b, School of Engineering, University of Auckland, Private Bag 92019 NewZealand, September 1993.
[155] Keith E. Mathias and L. Darrel Whitley. Transforming the search space with Gray
coding. In J. D. Schaffer, editor, Proceedings of the IEEE International Conference
on Evolutionary Computation, pages 513518. IEEE Service Center, Piscataway,
New Jersey, 1994.
[156] Keith E. Mathias and L. Darrell Whitley. Changing Representations During Search:
A Comparative Study of Delta Coding. Evolutionary Computation, 2(3):249278,
1994.
302
303
[169] Melanie Mitchell, Stephanie Forrest, and John H. Holland. The Royal Road for Genetic Algorithms: Fitness Landscapes and GA Performance. In Francisco J. Varela
and Paul Bourgine, editors, Toward a Practice of Autonomous Systems: Proceedings of the First European Conference on Artificial Life. MIT Press, Cambridge,
Massachusetts, 1992.
[170] Tom M. Mitchell. The Need for Biases in Learning Generalizations. Technical
Report CBM-TR-117, Department of Computer Science, Rutgers University, 1980.
[171] Angel Kuri Morales. A Comprehensive Approach to Genetic Algorithms in Optimization and Learning. Volume 1 : Foundations. Centro de Investigacion en
ComputacionInstituto Politecnico Nacional, Mexico City, 1999.
[172] Pedro Larra naga and Jose A. Lozano, editors. Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Kluwer Academic Publishers,
New York, 2001.
[173] A. Newell, J.C. Shaw, and H.A. Simon. The processes of creative thinking. In
H.E. Gruber, G. Terrell, and M. Wertheimer, editors, Contemporary approaches to
creative thinking, pages 63119. Atherton Press, New York, 1962.
[174] I.M. Oliver, D.J. Smith, and J.R.C. Holland. A Study of Permutation Crossover
Operators on the Traveling Salesman Problem. In John J. Grefenstette, editor, Genetic Algorithms and Their Applications: Proceedings of the Second International
Conference on Genetic Algorithms, pages 224230. Lawrence Erlbaum Associates,
Hillsdale, New Jersey, July 1987.
[175] C.C. Palmer. An approach to a problem in network design using genetic algorithms.
PhD thesis, Polytechnic University, Troy, New York, 1994.
[176] I. C. Parmee and G. Purchase. The development of a directed genetic search technique for heavily constrained design spaces. In I. C. Parmee, editor, Adaptive
Computing in Engineering Design and Control-94, pages 97102, Plymouth, UK,
1994. University of Plymouth.
[177] C. Peck and A.P. Dhawan. A Review and Critique of Genetic Algorithm Theories.
Evolutionary Computation, 3(1):3980, 1995.
[178] Nicholas J. Radcliffe. Forma Analysis and Random Respectful Recombination. In
Richard K. Belew and Lashon B. Booker, editors, Proceedings of the Fourth International Conference on Genetic Algorithms, pages 222229. Morgan Kaufmann
Publishers, San Mateo, California, July 1991.
304
305
306
[200] J. David Schaffer, Richard A. Caruana, Larry J. Eshelman, and Raharshi Das. A
Study of Control Parameters Affecting Online Performance of Genetic Algorithms
for Function Optimization. In J. David Schaffer, editor, Proceedings of the Third
International Conference on Genetic Algorithms, pages 5160, San Mateo, California, 1989. Morgan Kaufmann Publishers.
[201] J. David Schaffer and Amy Morishima. An Adaptive Crossover Distribution Mechanism for Genetic Algorithms. In John J. Grefenstette, editor, Genetic Algorithms
and Their Applications: Proceedings of the Second International Conference on
Genetic Algorithms, pages 3640. Lawrence Erlbaum Associates, Hillsdale, New
Jersey, July 1987.
[202] Hans-Paul Schwefel. Kybernetische evolution als strategie der experimentellen
forschung in der stromungstechnik. Dipl.-Ing. thesis, 1965. (in German).
[203] Hans-Paul Schwefel. Numerische Optimierung von Computer-Modellen mittels
der Evolutionsstrategie. Birkhauser, Basel, Alemania, 1977.
[204] Hans-Paul Schwefel. Numerical Optimization of Computer Models. Wiley, Chichester, UK, 1981.
[205] Greg W. Scragg. Computer Organization. A Top-Down Approach. McGraw-Hill,
New York, 1992.
[206] Anthony V. Sebald and Jennifer Schlenzig. Minimax design of neural net controllers for highly uncertain plants. IEEE Transactions on Neural Networks,
5(1):7382, January 1994.
[207] O. G. Selfridge. Pandemonium: A paradigm for learning. In Proceedings of the
Symposium on Mechanization of Thought Processes, pages 511529, Teddington,
England, 1958.
[208] S.F. Smith. A learning system based on genetic adaptive algorithms. PhD thesis,
University of Pittsburgh, 1980.
[209] William M. Spears and Kenneth A. De Jong. An Analysis of Multi-Point Crossover.
In Gregory E. Rawlins, editor, Foundations of Genetic Algorithms, pages 301315.
Morgan Kaufmann Publishers, San Mateo, California, 1991.
[210] M. Srinivas and L. M. Patnaik. Adaptive probabilities of crossover and mutation in genetic algorithms. IEEE Transactions on Systems, Man and Cybernetics,
24(4):656667, April 1994.
307
[211] M. Srinivas and L. M. Patnaik. Adaptive Probabilities of Crossover and Mutation in Genetic Algorithms. IEEE Transactions on Systems, Man and Cybernetics,
24(4):656667, April 1994.
[212] Edward J. Steele, Robyn A. Lindley, and Robert V. Blanden. Lamarcks Signature.
How Retrogenes are Changing Darwins Natural Selection Paradigm. Perseus
Books, Reading, Massachusetts, 1998.
[213] Rainer Storn and Kenneth Price. Differential Evolution: A Simple and Efficient
Adaptive Scheme for Global Optimization over Continuous Spaces. Technical Report TR-95-012, International Computer Science Institute, Berkeley, California,
March 1995.
[214] Rainer Storn and Kenneth Price. Differential EvolutionA Fast and Efficient
Heuristic for Global Optimization over Continuous Spaces. Journal of Global Optimization, 11:341359, 1997.
[215] Patrick D. Surry and Nicholas J. Radcliffe. Real Representations. In Richard K.
Belew and Michael D. Vose, editors, Foundations of Genetic Algorithms 4, pages
343363. Morgan Kaufmann, San Mateo, California, 1997.
[216] Patrick D. Surry, Nicholas J. Radcliffe, and Ian D. Boyd. A Multi-Objective Approach to Constrained Optimisation of Gas Supply Networks : The COMOGA
Method. In Terence C. Fogarty, editor, Evolutionary Computing. AISB Workshop.
Selected Papers, Lecture Notes in Computer Science, pages 166180. SpringerVerlag, Sheffield, U.K., 1995.
[217] Gilbert Syswerda. Uniform Crossover in Genetic Algorithms. In J. David Schaffer,
editor, Proceedings of the Third International Conference on Genetic Algorithms,
pages 29, San Mateo, California, 1989. Morgan Kaufmann Publishers.
[218] Gilbert Syswerda. Schedule Optimization using Genetic Algorithms. In Lawrence
Davis, editor, Handbook of Genetic Algorithms, chapter 21, pages 332349. Van
Nostrand Reinhold, New York, New York, 1991.
[219] Alan Mathison Turing. Computing Machinery and Intelligence. Mind, 59:94101,
1950.
[220] G. Vignaux and Z. Michalewicz. Genetic algorithms for the transportation problem.
Methodologies for Intelligent Systems, 4:252259, 1989.
[221] Michael D. Vose. Generalizing the Notion of Schema in Genetic Algorithms. Artificial Intelligence, 50(3):385396, 1991.
308
[222] Michael D. Vose. The Simple Genetic Algorithm. Foundations and Theory. The
MIT Press, Cambridge, Massachusetts, 1999.
[223] Hugo De Vries. Species and Varieties: Their Origin by Mutation. Open Court,
Chicago, 1906.
[224] August Weismann, editor. The Germ Plasm: A Theory of Heredity. Scott, London,
UK, 1893.
[225] A. Wetzel. Evaluation of the effectiveness of genetic algorithms in combinational
optimization. University of Pittsburgh, Pittsburgh (unpublished), 1983.
[226] D. Whitley and J. Kauth. GENITOR: A different Genetic Algorithm. In Proceedings of the Rocky Mountain Conference on Artificial Intelligence, pages 118130,
Denver, Colorado, 1988.
[227] D. Whitley, S. Rana, and R. Heckendorn. Representation Issues in Neighborhood
Search and Evolutionary Algorithms. In D. Quagliarella, J. Periaux, C. Poloni, and
G. Winter, editors, Genetic Algorithms and Evolution Strategies in Engineering
and Computer Science. Recent Advances and Industrial Applications, chapter 3,
pages 3957. John Wiley and Sons, West Sussex, England, 1998.
[228] Darrell Whitley. The GENITOR Algorithm and Selection Pressure: Why RankBased Allocation of Reproductive Trials is Best. In J. David Schaffer, editor,
Proceedings of the Third International Conference on Genetic Algorithms, pages
116121. Morgan Kaufmann Publishers, San Mateo, California, July 1989.
[229] D. H. Wolpert and W. G. Macready. No Free Lunch Theorems for Search. Technical Report SFI-TR-95-02-010, Santa Fe Institute, New Mexico, 1995.
[230] David H. Wolpert and William G. Macready. No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation, 1(1):6782, April 1997.
[231] Alden H. Wright. Genetic Algorithms for Real Parameter Optimization. In Gregory
J. E. Rawlins, editor, Foundations of Genetic Algorithms, pages 205218. Morgan
Kaufmann Publishers, San Mateo, California, 1991.
[232] Jin Wu and Shapour Azarm. On a New Constraint Handling Technique for MultiObjective Genetic Algorithms. In Lee Spector, Erik D. Goodman, Annie Wu, W.B.
Langdon, Hans-Michael Voigt, Mitsuo Gen, Sandip Sen, Marco Dorigo, Shahram
Pezeshk, Max H. Garzon, and Edmund Burke, editors, Proceedings of the Genetic
and Evolutionary Computation Conference (GECCO2001), pages 741748, San
Francisco, California, July 2001. Morgan Kaufmann Publishers.
309
[233] J. Yoo and P. Hajela. Enhanced GA Based Search Through Immune System Modeling. In 3rd World Congress on Structural and Multidisciplinary Optimization,
Niagara Falls, New York, May 1999.
310