PDF de programación - Un Algoritmo Evolutivo Multiobjetivo basado en Hipervolumen en GPUs

Centro de Investigación y de Estudios Avanzados

del Instituto Politécnico Nacional

Unidad Zacatenco

Departamento de Computación

Un Algoritmo Evolutivo Multiobjetivo basado en

Hipervolumen en GPUs

Tesis que presenta

Edgar Manoatl Lopez

para obtener el Grado de

Maestro en Ciencias

en Computación

Director de la Tesis

Dr. Carlos Artemio Coello Coello

México, D.F.

Noviembre 2013

ii

Resumen

El hipervolumen (o métrica S) se ha vuelto extremadamente popular hoy en día en
el área de optimización multi-objetivo. Debido a sus buenas propiedades matemáticas,
se ha utilizado no sólo como indicador de desempeño para comparar los resultados
finales de los algoritmos evolutivos multi-objetivo (AEMOs), sino también como cri-
terio de selección de los optimizadores multi-objetivo. Sin embargo, calcular el valor
exacto del hipervolumen es sumamente costoso (computacionalmente hablando); de
hecho, es un problema NP-duro. Los mejores algoritmos conocidos para este fin, cal-
culan el valor del hipervolumen en un tiempo de ejecución que es polinomial conforme
al número de puntos, pero que crece exponencialmente con el número de objetivos.
Por lo tanto, ya que el tiempo computacional es crucial para el redimiendo de los algo-
ritmos evolutivos, el alto costo del hipevolumen limita su uso, especialmente cuando
el número de objetivos de un problema es elevado. No obstante, una ventaja del hiper-
volumen es que la clasificación de soluciones que produce es invariante al escalamiento
lineal de las funciones objetivo, por lo que su uso sería prometedor para problemas de
optimización con muchos objetivos si su costo computacional no lo hiciese prohibitivo.
En esta tesis se propone un nuevo enfoque para utilizar el hipervolumen como
criterio de selección mediante el uso de Unidades de Procesamiento Gráfico (GPUs
por sus siglas en inglés), el cual calcula de una manera más rápida la contribución al
hipervolumen de un punto específico. Llevamos a cabo una implementación altamente
paralela de nuestro enfoque y demostramos su rendimiento cuando se utiliza con el
S-Metric Selection Evolutionary Multi-Objective Algorithm (SMS-EMOA). Los resul-
tados muestran que el enfoque alcanza una aceleración de hasta 883x con respecto a
su versión secuencial, haciendo posible el uso del hipervolumen exacto en problemas
de hasta nueve objetivos.

iii

iv

Abstract

The hypervolume (or S-metric) has become extremely popular nowadays within
multi-objective optimization. Because of its good mathematical properties, it has been
used not only as a performance indicator to compare the final results obtained by
multi-objective evolutionary algorithms (MOEAs), but also as a selection criterion
in multi-objective optimizers. However, computing the exact hypervolume value is
very expensive (computationally speaking); in fact, it is an NP-hard problem. The
best algorithms known today for this task compute the hypervolume value in an
execution time that is polynomial with respect to the number of points, but that grows
exponentially with the number of objectives. Therefore, and since the computational
time is crucial to the performance of evolutionary algorithms, the high cost of the
hypervolume limits its use, particularly when the number of objectives of a problem
is high. Nevertheless, an advantage of the hypervolume is that the classification of
solutions that it produces, is invariant to the linear scaling of the objective functions,
which would make it an attractive choice for dealing with optimization problems
having many objectives, if its computational cost did not turn it prohibitive.

In this thesis, we propose a new approach for the use of the hypervolume as
a selection criterion, based on the use of Graphical Processing Units (GPUs). The
proposed approach computes in a faster manner the hypervolume contribution of
a specific point. We also provide a highly parallel implementation of our approach
and show its performance using the S-Metric Selection Evolutionary Multi-Objective
Algorithm (SMS-EMOA). Our results indicate that our proposed approach can reach
a speedup of up to 883x with respect to its sequential version, which makes possible
the use of exact hypervolume contributions for problems having up to nine objectives.

v

vi

Agradecimientos

La realización de esta tesis marca un objetivo más en mi lista de metas, la cual
no habría sido posible sin la presencia de perseverancia, responsabilidad, constancia
y todos esos valores que sirven como guía para lograr un objetivo.

Me gustaría agradecer a mis padres por el amor y apoyo incondicional que me han
brindado durante toda mi vida. También a todos mis seres queridos, por todo lo que
han compartido conmigo y por ser el motor que me impulsa cada día. De igual forma,
quiero agradecer a todos los que se han cruzado en mi camino y me han brindado su
cariño en algún momento de mi vida.

También quiero agradecer a todas aquellas personas que de algún modo han sido
mis guías, pues sin sus enseñanzas y consejos ninguno de mis logros hubiese sido po-
sible. A todos los Drs. que me impartieron clases durante esta etapa de mi vida por
compartir sus conocimientos.

Quiero agradecer a mi asesor el Dr. Carlos A. Coello Coello por haberme dado
el honor de trabajar bajo su guía y lidiar conmigo, por transmitirme su pasión por
la investigación y con ello sembrar en mi un gran deseo de aprender, por todas sus
enseñanzas, por su apoyo y por compartir sus experiencias de vida de forma chusca.
Finalmente quiero agradecer al CINVESTAV por permitirme formar parte de esta
gran institución y al CONACyT por brindarnos un apoyo económico, permitiendo
que muchas personas como yo, podamos concluir los estudios de maestría.

vii

viii

Índice general

Índice de figuras

Índice de tablas

1. Introducción

1.1. Objetivos de la tesis
1.2. Organización de la tesis

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

2. Optimización Multi-objetivo

2.1. Problemas de optimización multi-objetivo
. . . . . . . . . . . . . . .
2.2. Vectores de referencia . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . .
2.3. Métodos tradicionales para resolver problemas multi-objetivo
2.3.1. Métodos sin preferencias . . . . . . . . . . . . . . . . . . . . .
2.3.2. Métodos a posteriori
. . . . . . . . . . . . . . . . . . . . . . .
2.3.3. Métodos a priori
. . . . . . . . . . . . . . . . . . . . . . . . .
2.3.4. Métodos Interactivos . . . . . . . . . . . . . . . . . . . . . . .
2.4. Algoritmos evolutivos . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4.1. Computación evolutiva . . . . . . . . . . . . . . . . . . . . . .
2.4.2. Principales paradigmas de la computación evolutiva . . . . . .
2.5. Algoritmos evolutivos multi-objetivo . . . . . . . . . . . . . . . . . .
Indicadores multi-objetivo . . . . . . . . . . . . . . . . . . . .
.

2.5.1.
2.5.2. Algoritmos evolutivos multi-objetivo basados en indicadores

3. Computación Paralela

3.1. Conceptos básicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2. Modelos de cómputo paralelo . . . . . . . . . . . . . . . . . . . . . .
3.3. Modelos de programación paralela . . . . . . . . . . . . . . . . . . . .
3.3.1. Modelo implícito . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.2. Modelo de memoria compartida . . . . . . . . . . . . . . . . .
3.3.3. Modelo paso de mensajes . . . . . . . . . . . . . . . . . . . . .
3.4. Arquitecturas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.5. Taxonomía de Flynn . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.6. Unidad de procesamiento gráfico . . . . . . . . . . . . . . . . . . . . .
3.6.1. Diferencias entre CPU y GPU . . . . . . . . . . . . . . . . . .

ix

X

XIII

1
2
3

5
5
7
8
8
9
9
9
10
10
12
14
17
18

23
24
25
29
29
30
30
30
31
32
33

x

ÍNDICE GENERAL

3.6.2. CUDA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.6.3. Modelo de programación . . . . . . . . . . . . . . . . . . . . .

4. Hipervolumen

4.1.
Indicador de hipervolumen . . . . . . . . . . . . . . . . . . . . . . . .
4.2. Contribución al hipervolumen . . . . . . . . . . . . . . . . . . . . . .
4.3. Características del indicador de hipervolumen . . . . . . . . . . . . .
4.4. Algoritmos para el cálculo del hipervolumen . . . . . . . . . . . . . .
4.4.1. Hipervolumen mediante inclusión-exclusión . . . . . . . . . . .
4.4.2. Hipervolumen mediante la medida de Lebesgue
. . . . . . . .
4.4.3. Algoritmo HSO . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.4. Algoritmo FPL . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.5. Cálculo del hipervolumen mediante la medida de Klee . . . . .

5. Modelo Propuesto

5.1. Descripción del modelo . . . . . . . . . . . . . . . . . . . . . . . . . .
5.1.1. Solución para dos funciones objetivo en conflicto . . . . . . . .
5.1.2. Solución para más de dos funciones objetivo en conflicto . . .
5.1.3. Ordenamiento paralelo . . . . . . . . . . . . . . . . . . . . . .

6. Experimentos

6.1. Problemas de Prueba . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2. Metodología . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2.1. Tasa de convergencia . . . . . . . . . . . . . . . . . . . . . . .
6.2.2. Espaciamiento . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2.3. Aceleración . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2.4. Eficiencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.3. Parametrización . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.4. Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7. Conclusiones y Trabajo futuro

A. Funciones de prueba

A.1. Conjunto de problemas Deb-Thiele-Laumanns-Zitzler . . . . . . . . .
A.1.1. DTLZ1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.1.2. DTLZ2 . . . . . . . . . . . . . . . . . . .