Departamento de Computación

Una gran número de problemas del mundo real requieren de la optimización simultá nea de varios objetivos en conflicto. A estos se les conoce como problemas de optimización multi-objetivo y no tienen una solución única, sino un conjunto de soluciones que representan los diferentes compromisos entre los objetivos. Este es el denominado conjunto de óptimos de Pareto y a su imagen se le llama, frente de Pareto. El uso de algoritmos evolutivos y metaheurísticas bio-inspiradas para resolver problemas multi-objetivo se ha vuelto muy popular en los últimos 15 años, dando lugar a una amplia variedad de algoritmos evolutivos multi-objetivo (AEMOs). Los dos componentes principales de un AEMO son: (1) un mecanismo de selección que preserva los mejores compromisos entre los objetivos (i.e, soluciones no dominadas) y (2) un estimador de densidad que permite esparcir soluciones uniformemente a lo largo del frente de Pareto, de tal manera que sean lo mas diversas posibles. La incorporación de indicadores de desempeño como el mecanismo de selección en un AEMO es un tema que ha atraído mucho interés en años recientes. Esto debido a que los esquemas de selección basados en la optimalidad de Pareto no tienen un buen desempeño en problemas con cuatro o mas funciones objetivo. El indicador que ha sido mas utilizado para ser incorporado en el mecanismo de selección de un AEMO es el hipervolumen. Sin embargo, en el presente trabajo, exploramos el uso del indicador R2, que presenta varias ventajas con respecto al hipervolumen, de entre las cuales, la principal es su bajo costo computacional. En esta tesis, proponemos un nuevo AEMO,llamado MOMBI (Many-Objective Metaheuristic Based on the R2 Indicator), el cual jerarquiza individuos por medio de funciones de utilidad. El enfoque propuesto es comparado con NSGA-II (basado en dominancia de Pareto), MOEA/D (basado en escalarización), SMS-EMOA (basado en el hipervolumen),
p-DDE (basado en el indicador
p) y otros algoritmos de reciente creación basados en el indicador R2, utilizando diversos problemas de prueba estandar. Nuestros resultados experimentales indican que MOMBI obtiene soluciones de calidad similar a los producidos por SMS-EMOA, pero a un menor costo computacional. Adicionalmente, MOMBI supera a MOEA/D y
p-DDE en la mayoría de las instancias de prueba, particularmente cuando se trata de problemas de mas de tres funciones objetivo con frentes de Pareto complicados. De tal forma, creemos que el enfoque propuesto es una alternativa viable para resolver problemas de optimización con varios objetivos.

Abstract

A wide variety of real-world problems have several (often conflicting) objectives that need to be optimized at the same time. They are called multi-objective optimization problems (MOPs) and their solution involves finding a set of decision variables, also known as Pareto optimal set, that represents the best trade-os among all the objectives. The image of the Pareto optimal set is called the Pareto optimal front. The use of evolutionary algorithms, as well as other bio-inspired metaheuristics,for solving MOPs has become increasingly popular in the last 15 years, giving rise to a wide variety of multi-objective evolutionary algorithms (MOEAs). The two key algorithmic components of a MOEA are: (1) a selection mechanism that preserves the best possible trade-offs among the objectives (i.e., the so-called nondominated solutions) and (2) a density estimator that allows us to spread solutions along the Pareto optimal front in a uniform way, so that they are as diverse as possible. The incorporation of performance indicators as the selection mechanism of a MOEA is a topic that has attracted increasing interest in the last few years. This has been mainly motivated by the fact that Pareto-based selection schemes do not perform properly when solving problems with four or more objectives. The indicator that has been most commonly used for being incorporated in the selection mechanism of a MOEA has been the hypervolume. Here, however, we explore the use of the R2 indicator, which presents some advantages with respect to the hypervolume, the main one being its low computational cost. In this document, we propose a new MOEA called Many-Objective Metaheuristic Based on the R2 Indicator (MOMBI), which ranks individuals using utility functions. The proposed approach is compared with respect to NSGA-II (based on Pareto dominance), MOEA/D (based on scalarization), SMS-EMOA (based on hypervolume),
p-DDE (based on
p indicator), and some other recently created MOEAs based on the R2 indicator, using several benchmark problems. Our preliminary experimental results indicate that MOMBI obtains solutions of similar quality to those produced by SMS-EMOA, but at a much lower computational cost. Additionally, MOMBI outperforms MOEA/D and
p-DDE in most of the test instances adopted, particularly when dealing with high-dimensional problems having complicated Pareto optimal fronts. Thus, we believe that our proposed approach is a viable alternative for solving many-objective optimization problems.