Tesis

´
CENTRO DE INVESTIGACION Y DE ESTUDIOS
´
AVANZADOS DEL INSTITUTO POLITECNICO NACIONAL
´
DEPARTAMENTO DE INGENIER´ ELECTRICA
IA
´
´
SECCION DE COMPUTACION

Un estudio de las Estrategias Evolutivas para
problemas Multiobjetivo.

Tesis que presenta
Adriana Lara L´pez
o

para obtener el Grado de
Maestra en Ciencias

en la especialidad de
Ingenier´ El´ctrica,
ıa e
Opci´nComputaci´n.
o
o
Codirectores de la Tesis
Dr. Carlos A. Coello Coello
Dr. Alin Carsteanu

Mexico, D.F.

Julio de 2003

ii
.

Resumen
En esta tesis se establece la teor´ para el estudio de Estrategias Evolutivas
ıa
en el contexto de la optimizaci´n multi-objetivo. Se analiza el trabajo previo
o
en convergencia hacia el Frente de Pareto de Algoritmos Evolutivos realizado por
G¨nterRudolph, Alexandru Agapie, David Van Veldhuizen y Thomas H¨nne, para
u
a
crear pruebas de convergencia asint´tica propias de las Estrategias multiobjetivo
o
(1 + 1), (µ + λ) y (µ, λ).
Se hace un an´lisis de los operadores principales de las Estrategias Evolutivas,
a
para comprender mejor el funcionamiento de algunas de sus variantes en relaci´n
o
a la convergencia de los algoritmos.
Sepropone, por ultimo, un mecanismo de auto-adaptaci´n para la Estrategia
´
o
Evolutiva multimiembro y se estudia su velocidad de convergencia, as´ como varios
ı
aspectos te´ricos propios de la implementaci´n y comportamiento del algoritmo.
o
o

Abstract
In this thesis we establish the theory for the study of Evolution Strategies in the
context of the multi-objective optimization. Weanalyze the previous work on the
convergence toward the Pareto Front performed by G¨nter Rudolph, Alexandru
u
Agapie, David Van Veldhuizen and Thomas H¨nne, to make the specific asynthotic
a
proofs for the convergence of Evolution Strategies (1 + 1), (µ + λ) and (µ, λ).
We show an study of the main operators of Evolution Strategies to better
understand the behavior of the variants of thesealgorithms mainly in terms of
convergence.
Finally, we propose a self-adaptation mechanism for the multi-member Evolution Strategy and we study its velocity of convergence and several theoretical
aspects of its implementation and performance.

.

Agradecimientos
A mi amado esposo Jes´s, por ser mi apoyo constante.
u
A mis compa˜eros y amigos del CINVESTAV: Eloy, Ricardo Landa, Joselito,
nJulio, Lorena, Ricardo Quiroz, Juan Manuel, Mireya, Omar y Miguel, por acompa˜arme durante todo el viaje. A Margarita, Nareli, Goyo, Lalo y Efr´n, por
n
e
darme su amistad.
A mis asesores Dr. Alin Carsteanu y Dr. Carlos Coello por hacer posible esta
tesis.
A todos quienes como Gerardo de la Fraga, Guillermo Morales y Oscar Olmedo
me brindaron consejos acad´micos y personales que atesorar´por siempre.
e
e
A mis dos familias, por su amor y por extra˜arme en algunas fiestas.
n
Se agradece la beca terminal de maestr´a recibida a trav´s del proyecto COı
e
NACYT titulado “Nuevos Paradigmas en Optimizaci´n Evolutiva Multiobjetivo”
o
(Ref. 34201-A) cuyo responsable es el Dr. Carlos A. Coello Coello.

.

´
Indice General
1 Optimizaci´n y problemas multi-objetivo
o
1.1T´cnicas cl´sicas de optimizaci´n . . . . .
e
a
o
1.1.1 Optimizaci´n lineal . . . . . . . . .
o
1.1.2 Complejidad computacional . . . .
1.1.3 Heur´
ısticas . . . . . . . . . . . . . .
1.1.4 Principales complicaciones . . . . .
1.2 Problemas multi-objetivo . . . . . . . . . .
1.2.1 Conjuntos parcialmente ordenados
1.3 Sumario . . . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
..
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

3
3
3
7
8
9
12
14
18

2 Computaci´n evolutiva...