Departamento de Computación

En la industria, normalmente encontramos problemas donde la meta es optimizar simultáneamente dos o más funciones objetivo que usualmente están en conflicto entre sí, tales como minimizar el tiempo y el costo de producción. A ´estos se les conoce como Problemas de Optimización Multi-objetivo (POMs). Diversas técnicas de programación matemática han sido propuestas para resolver esta clase de problemas. Sin embargo, dichas técnicas no se desempeñan bien en instancias con muchos óptimos locales y usualmente están diseñadas para POMs con características particulares. Los Algoritmos Evolutivos Multi-Objetivo (AEMOs) son una alternativa que se ha vuelto popular en años recientes para resolver POMs. Los AEMOs operan con soluciones potenciales (llamadas individuos) que exploran el espacio de búsqueda usando operadores inspirados en la evolución natural (selección, recombinación y mutación). La mayor parte de los AEMOs pueden clasificarse en tres categorías de acuerdo a su mecanismo de selección: basados en Pareto, basados en indicadores y basados en descomposición. A pesar de que estos mecanismos son predominantes en la literatura especializada, tienen varias desventajas como un desempeño pobre o costoso en problemas con muchos objetivos o sensibilidad a los parámetros adoptados. Por lo tanto, hay una necesidad de crear mecanismos de selección más eficaces que puedan superar estas limitaciones y proporcionar soluciones robustas y eficientes. En esta tesis se proponen dos nuevos mecanismos de selección alternativos que no se encuentran en ninguna de las tres clases indicadas previamente. Estos mecanismos se incorporan en AEMOs modernos y los algoritmos resultantes son validados con respecto a AEMOs del estado del arte. Los resultados experimentales obtenidos de dicha comparación indican que los mecanismos propuestos permiten resolver problemas con una amplia variedad de características y con más de tres objetivos. Empleando el conocimiento obtenido de los mecanismos de selección propuestos, se proponen posteriormente dos nuevos indicadores para evaluar el desempeño de los AEMOs. El análisis experimental de dichos indicadores muestra que son capaces de evaluar correctamente algunas características cruciales de las aproximaciones generados por un AEMO.

Abstract

In industry, we normally face problems in which the goal is to simultaneously optimize two or more objective functions which are often in conflict with each other, such as minizing both production time and cost. These are the so-called Multi-objective Optimization Problems (MOPs). A variety of mathematical programming techniques have been proposed to solve such problems. However, such techniques do not have a good performance in instances with many local optimal and are usually designed to deal with MOPs having particular features. Multi-Objective Evolutionary Algorithms (MOEAs) are a choice for solving MOPs that has become increasingly popular in recent years. MOEAs operate with potential solutions (called individuals) which explore the search space using operators inspired on natural evolution (selection, recombination and mutation). Most MOEAs can be classified into one of the three following categories based on their selection mechanism: Pareto-based, indicator-based and decomposition-based. Although these mechanisms are predominantly used in the specialized literature, they have several disadvantages, such as a poor or computationally expensive performance in problems having many objectives or high sensitivity to the values of their parameters. Therefore, there is a need to propose new selection mechanisms with a higher efficacy and that can overcome these limitations, thus providing robust and efficient solutions. In this thesis, we propose two new alternative selection mechanisms that do not belong to any of the three previously indicated classes. Such mechanisms are incorporated into modern MOEAs and the resulting algorithms are validated with respect to state-of-the-art MOEAs. Our experimental results indicate that the proposed mechanisms can properly deal with a wide variety of features and with problems having more than three objectives. Based on the knowledge obtained from the proposed selection mechanisms, we also propose two new quality indicators to assess performance of MOEAs. The experimental analysis of such indicators shows that they can correctly assess some crucial features of the approximations generated by an MOEA.