Departamento de Computación

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 criterio 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, calculan 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 rendimiendo de los algoritmos 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 hipervolumen es que la clasificación de soluciones que produce es invariante al escalamiento lineal de las funciones objetivo, por lo que su uso será 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 resultados 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.

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.