Departamento de Computación

Un gran número de problemas presentes en diversas áreas del conocimiento requieren la optimización simultánea de varios objetivos en conflicto. Estos problemas, denominados Problemas de Optimización Multiobjetivo (POMs), no poseen una solución única, sino un conjunto de soluciones que representan los distintos compromisos entre los objetivos. Los Algoritmos Evolutivos Multiobjetivo (AEMOs) se han convertido en una de las técnicas más utilizadas para lidiar con POMs, pues han mostrado gran efectividad al solucionar problemas con dos y tres objetivos. Sin embargo, a medida que aumenta el número de objetivos en conflicto, el desempeño de la mayoría de los AEMOs se deteriora drásticamente. Esto ha provocado un creciente interés en el desarrollo de AEMOs que puedan solucionar POMs con más de tres objetivos, debido a la frecuencia con que surge este tipo de problemas en la ciencia y la ingeniería. En esta tesis se propone un nuevo algoritmo evolutivo multiobjetivo para resolver problemas con más de tres objetivos. Nuestra propuesta transforma el proceso de selección de un AEMO en un problema de asignación lineal utilizando un conjunto de vectores de pesos uniformemente distribuidos y una función de costo. El problema de asignación obtenido se soluciona mediante el algoritmo de Kuhn-Munkres (conocido también como método húngaro). Para construir el conjunto de vectores de pesos proponemos un algoritmo basado en el diseño uniforme que evita las deficiencias del método simplex-lattice, el cual es comúnmente utilizado en los AEMOs basados en descomposición. En nuestra propuesta se generan las soluciones utilizando los operadores de recombinación de la evolución diferencial, debido a lo cual denominamos al AEMO propuesto evolución diferencial húngara (EDH). EDH se comparó con respecto a tres de los AEMOs con mejor desempeño registrado en la literatura especializada, dos de ellos basados en descomposición (MOEA/D y MOEA/D-DE) y uno basado en el hipervolumen (SMS-EMOA). Los resultados obtenidos en 16 problemas de prueba con 144 instancias de entre 2 y 10 objetivos, indican que nuestra propuesta supera a MOEA/D y MOEA/D-DE tanto en convergencia como en diversidad de las soluciones. Además, EDH obtiene resultados competitivos con respecto a SMS-EMOA y en varias instancias supera a éste en cuanto a diversidad de las soluciones. Asimismo, el costo computacional de EDH no depende del número de funciones objetivo, mientras que el tiempo de ejecución de SMS-EMOA crece exponencialmente con el número de objetivos.

Abstract

A large number of problems in a wide variety of domains involve simultaneous optimization of several conflicting objectives. These problems, called Multi-objective Optimization Problems (MOPs), do not have a single optimal solution, but rather a set of solution that represent the best trade-offs among all the objectives. Among the different techniques available to solve MOPs, Multi-objective Evolutionary Algorithms (MOEAs) have become very popular, mainly because of their effectiveness in problems with two and three objectives. However, as the number of conflicting objectives increases, the performance of most MOEAs severely deteriorates. This has motivated a growing interest for developing MOEAs for handling four or more objectives, due to the frequency with such problems arise in science and engineering. In this work, we propose a new multi-objective evolutionary algorithm to solve optimization problems having four or more objectives. Our proposal transforms the selection process of a MOEA into a linear assignment problem using a set of weight vectors uniformly scattered and a cost function. The Kuhn-Munkres or Hungarian algorithm is used to solve the resulting assignment problem. We propose an algorithm based on uniform design to obtain the set of weights and avoid the shortcomings of the simplex-lattice design method, which is the approach most commonly adopted in decomposition-based MOEAs. Differential evolution is used as our search engine giving rise to the so-called hungarian dfferential evolution (HDE) algorithm. Our proposed approach is compared with respect to three well-known MOEAs, two of them based on decomposition (MOEA/D and MOEA/D-DE) and one based on hypervolume (SMS-EMOA). The results obtained in 16 test problems with 144 instances having 2 to 10 objectives, indicate that HDE outperforms MOEA/D and MOEA/D-DE both in terms of convergence and diversity of the solutions obtained. Furthermore, our approach obtains competitive results with respect to SMS-EMOA and, in several instances, outperforms it in terms of the diversity of solutions. Additionally, the computational cost of EDH does not depend on the number of objective functions, whereas SMS-EMOA has an execution time which grows exponentially on the number of objectives.