Departamento de Computación

En muchos problemas en la industria y finanzas, se tiene el problema de minimizar más de un objetivo, i.e., estos objetivos deben ser minimizados simultaneamente. Por el momento, los métodos más utilizados para aproximar el conjunto solución (frente de Pareto) de un Problema de Optimización Multi-Objetivo (POM) son los Algoritmos Evolutivos de Optimización Multi-Objetivo (AEOM). En la presente tesis, hemos desarrollado e investigado un nuevo algoritmo evolutivo basado en un archivo (i.e. AEOM equipados con un archivo externo con el fin de garantizar convergencia del proceso de búsqueda). Para esto, nosotros proponemos dos operadores variacionales, la Shifted Polynomial Mutation (SPM) y Biased Intermediate Crossover (BIC). Estos operadores están hechos según las necesidades de los archivos que utilizamos (archivos basados en el concepto de dominancia-²). Teniendo como base aspectos teóricos y observaciones, hemos construido un nuevo algoritmo evolutivo, ELMA (Evolutionary Lipschitz Multi-Objective Algorithm). El objetivo de este algoritmo es obtener una buena aproximación, en términos de la distancia de Hausdorff, en relación con el frente de Pareto. Con el fin de evaluar nuestro algoritmo, ELMA, de forma justa, hemos desarrollado un indicador que mide, en promedio, la distancia de Hausdorff con respecto al frente de Pareto. El nuevo indicador, ¢p, esta compuesto por dos indicadores utilizados en la literatura (pequeñas variantes), Generational Distance (GD) e Inverted Generational Distance (IGD). El nuevo indicador puede ser aplicado en modelos discretos o continuos. Finalmente, comparamos nuestro algoritmo, ELMA, contra el algoritmo ²-MOEA, que es un algoritmo evolutivo basado en un archivo ampliamente utilizado. Hemos observado que la aproximación obtenida, en diferentes modelos como ZDT, por nuestro algoritmo es mejor que ²-MOEA y, además es un paso adelante en el diseño de un algoritmo evolutivo rápido y confiable.

Abstract

In many problems in industry and finance the problem arises that several objectives have to be optimized concurrently. So far, the most widely used approach to compute the solution set (the Pareto front) of such Multi-Objective Optimization roblems (MOPs) are the Multi-Objective Avolutionary Algorithms (MOEAs). In this thesis, we develop and investigate a new archive-based MOEA (i.e., a MOEA equipped with an external archive in order to guarantee convergence of the search process). For this, we will propose two new variation operators, the Shifted Polynomial Mutation (SPM) and Biased Intermediate Crossover (BIC), which are intended to meet the requeriments of the archivers we are using (archivers based on the concept of ²-dominance). Based on theoretical and empirical observations we construct the MOEA ELMA (Evolutionary Lipschitz Multi-Objective Algorithm) which is aiming, roughly speaking, for a good Hausdorff approximations of the Pareto front of the given MOP. In order to evaluate and compare ELMA in a fair way, we develop further on a new performance indicator which is measuring the averaged Hausdorff distance to the Pareto front. The new indicator, ¢p, is composed of (slight variants) of the well-know indicators Generational Distance (GD) and Inverted Generational Distance (IGD) and can be applied to both discrete or continuos model. Finally, we compare ELMA against ²-MOEA, which is a widely used archive-based MOEA and which can be viewed as the base algorithm of ELMA. It turns out that ELMA outperforms the ²-MOEA on several benchmark models such as the ZDT models, indicating that ELMA is a step forward in the design of fast and reliable MOEAs.