PDF de programación - Thesis: Diseño de un algoritmo evolutivo multiobjetivo paralelo

CENTRO DE INVESTIGACI ·ON Y DE ESTUDIOS AVANZADOS

DEL IPN

Departamento de Ingenier·a El·ectrica

Secci·on de Computaci·on

Dise no de un algoritmo evolutivo multiobjetivo paralelo

Tesis que presenta

Antonio L·opez Jaimes*

para obtener el grado de

Maestro en Ciencias

en la especialidad de
Ingenier·a El·ectrica,
Opci·on Computaci·on

Dirigida por el

Doctor Carlos A. Coello Coello

M·exico, D.F.

Febrero de 2005

*Quisiera agradecer por la beca terminal otorgada por medio del proyecto CONACyT 31892-A, cuyo responsable

es el Dr. Arturo D·az P·erez

II

LOS MENDIGOS
¡Hab·a mendigos! Unos imploraban el amor. Otros, la estima.
Otros la gloria. Despreciaban a los que ped·an pan o dinero.
Algunos ped·an una idea por el amor de los dioses, o un verso
bien hecho o un estilo ((original)).

Paul VAL ·ERY

Resumen

La mayor·a de los problemas del mundo real involucran la optimizaci ·on simult·anea de va-
rios objetivos (generalmente en conicto entre s· y expresados en distintas unidades de medida).
Estos problemas son llamados multiobjetivo o multicriterio (POMs). La investigaci ·on de opera-
ciones ha desarrollado un n ·umero considerable de t·ecnicas para resolver estos problemas. Sin
embargo, dada la complejidad de la mayor·a de los problemas de optimizaci·on multiobjetivo
del mundo real (p. ej., alta dimensionalidad, discontinuidad, multimodalidad), estas t·ecnicas
presentan varias limitantes o no resultan pr·acticos para resolverlos.

Uno de los enfoques alternativos m·as exitosos para resolver ecazmente estos problemas es
el uso de los algoritmos evolutivos multiobjetivo (AEMO). No obstante, uno de los puntos d·ebiles
de estos algoritmos es su alto consumo de recursos computacionales, lo cual motiva, de mane-
ra natural, el uso del paralelismo. La paralelizaci ·on de los AEMOs es un campo relativamente
nuevo, y como consecuencia, existen pocas publicaciones al respecto. En la mayor·a de estas
publicaciones no se discuten detalladamente los aspectos relacionados con el desarrollo y la im-
plementaci·on de los AEMOs paralelos (pAEMOs). Asimismo, no se ha considerado una selecci ·on
justicada de los problemas de prueba y de las m·etricas para evaluar tanto la ecacia como la
eciencia de los pAEMOs.

En esta tesis se presenta un nuevo AEMO paralelo competitivo con respecto a los AEMOs re-
presentativos del estado del arte desde el punto de vista de la efectividad y la eciencia. El algo-
ritmo propuesto, denominado algoritmo gen·etico multiobjetivo con m·ultiples resoluciones (MRMOGA,
’Multiple Resolution Multi-Objective Genetic Algorithm’), est·a basado en el modelo de islas con nodos
heterog·eneos y se construy·o sobre un c ·umulo de computadoras. El algoritmo se caracteriza por
codicar las soluciones con una resoluci·on distinta en cada isla. De esta manera se consigue
dividir el espacio de b ·usqueda en regiones disjuntas del espacio de las variables de decisi ·on.

Para evaluar la efectividad del algoritmo propuesto se utilizaron m·etricas conocidas para
evaluar AEMOs secuenciales, a saber: el conteo de aciertos, la distancia generacional invertida, el es-
paciamiento y la cobertura de conjuntos. Para evaluar la eciencia se utilizaron las siguientes m·etri-
cas conocidas en la computaci·on paralela: aceleraci·on, eciencia y fracci·on serial. Los resultados del
algoritmo propuesto se compararon con los obtenidos por una versi ·on paralela del NSGA-II.

Con base en los resultados obtenidos podemos armar que el esquema de MRMOGA para
dividir el espacio de b ·usqueda mediante distintas resoluciones mejora considerablemente la e-
cacia y la eciencia de un pAEMO. Adem·as, el algoritmo propuesto tiene una gran capacidad
exploratoria ya que, con respecto al algoritmo de referencia, en todas las funciones de prue-
ba encontr·o soluciones que se extienden mejor a lo largo del frente de Pareto real. Asimismo,
MRMOGA demostr·o una capacidad inusualmente buena para resolver POMs con restricciones,
incluso para aquellos problemas reconocidos por su dicultad.

III

IV

Abstract

Most real-world problems involve simultaneous optimization of several objectives (usually
incommensurable and in conict with each other). These problems are called multiobjective, or
multicriteria optimization problems (MOPs). Operations Research has developed plenty of met-
hods to solve these problems. However, due to the complexity of most real-world multiobjective
optimization problems (e.g., high dimensionality, discontinuity, multimodality), these methods
have several drawbacks or become impractical to solve them.

One of the most successful approaches for solving effectively these problems is the use of
multiobjective evolutionary algorithms (MOEAs). Nevertheless, one of the drawback of these
algorithms is their high consumption of computational resources. To overcome this problem,
the parallel and distributed processing of the MOEAs is a natural solution.

Parallelization of MOEAs is a relatively new eld, so there are few publications on that sub-
ject. In general, these publications do not discuss in detail parallel MOEA (pMOEA) development
and implementation issues. Also, these publications lack a thorough rationale of the MOP test
problem selection and pMOEA performance metrics to evaluate both effectiveness and efciency.
This thesis presents a novel parallel MOEA with regard to the representative MOEAs of the
state-of-the-art in terms of effectiveness and efciency. The proposed algorithm, called Multi-
Resolution Multi-Objective Genetic Algorithm (MRMOGA), is based on the island model with he-
terogeneous nodes and is built upon a cluster of computers. This algorithm is characterized by
encoding the solutions using a different resolution for each island. In this way, the search space
is divided into disjoint regions in the variable decision space.

In order to evaluate the effectiveness of the proposed approach we use well-known metrics
used to evaluate serial MOEAs, namely: success counting, generational distance, spacing, and two
set coverage. On the other hand, efciency was evaluated using the following well-known me-
trics from parallel computing: speedup, efciency and serial fraction. The results of the proposed
algorithm were compared against those of a parallel version of the NSGA-II.

In the light of the obtained results, we can state that the MRMOGA scheme to divide the
search space with different resolutions improves considerably the effectiveness and efciency
of a parallel MOEA. In addition, the proposed algorithm has a great exploratory ability, because
in all the test functions it found solutions with a better spread along the real Pareto front than
the algorithm with respect to which it was compared. Also, MRMOGA showed an unusual good
ability to solve constrained MOPs, even for those problems recognized for their difculty.

V

VI

·Indice general

Resumen

Abstract

·Indice de guras

·Indice de tablas

·Indice de algoritmos

Lista de acr·onimos

Lista de s·mbolos

1. Introducci·on

1.1. Antecedentes y motivaci·on .
.
.
1.2. Propuesta .
.
1.3. Objetivos generales y espec·cos del proyecto .
.
.

1.3.1. Objetivo General
1.4. Estructura de la tesis .
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.

.

.

.

.

.

.

.

.

2. Computaci·on Evolutiva
.
.

Introducci·on .

.

.

.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
.

.
2.1.
.
2.2. Antecedentes hist·oricos
.
2.3. Conceptos de Computaci·on Evolutiva .
.
.
.
.
.
.

2.3.1. Representaci·on .
.
.
.
2.3.2. Operadores evolutivos .
.
.
2.4.1. Estrategias Evolutivas .
.
2.4.2. Programaci·on Evolutiva .
2.4.3. Algoritmos Gen·eticos
.

2.4. Principales paradigmas .

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.

.

.

.

.

.

.

III

V

X

XIII

XV

XIX

XXII

1
1
2
3
3
3

5
5
6
8
8
9
10
11
12
12

15
15
16
17

.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

Introducci·on .

3. Optimizaci·on multiobjetivo con algoritmos evolutivos
.
.
.

3.1.
.
3.2. Conceptos de optimizaci·on multiobjetivo .
.

3.2.1. Optimalidad de Pareto .

.
.
.

.
.
.

.
.
.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

VII

VIII

·INDICE GENERAL

3.3. Algoritmos evolutivos multiobjetivo (AEMO)
.
.
3.4. Elementos clave de los AEMOs .
3.4.1. Asignaci·on de aptitud .
.
.
.
3.4.2. Elitismo .
.
.
.
.
.
3.4.3. Diversidad poblacional
.
.
.
3.5.1. T·ecnicas a priori .
.
.
.
3.5.2. T·ecnicas progresivas .
.
.
3.5.3. T·ecnicas a posteriori .
.
.
.

3.5. Clasicaci·on de los AEMOs .
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.

.

.

.

.

.

.

.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.
.

.
.
.
.

.
.
.
.

.