Departamento de Computación

En el mundo real existe una gran cantidad de problemas de optimización para los cuales los métodos de programación matemática no pueden garantizar que la solución obtenida sea óptima y, en muchos de ellos, ni siquiera pueden aplicarse. Es estos problemas las metaheurísticas se vuelven una alternativa viable. De entre las diversas metaheurísticas disponibles en la actualidad, los algoritmos evolutivos se cuentan entre los más populares debido a su simplicidad conceptual y su eficacia. En el mundo real, los problemas de optimización multiobjetivo se presentan con mucha frecuencia. En ellos hay que optimizar dos o más funciones objetivo que se encuentran normalmente en conflicto entre sí. La solución de problemas multiobjetivo usando metaheurísticas (sobre todo, algoritmos evolutivos) es un tema que ha adquirido gran popularidad en los últimos años.
En este documento presentamos dos algoritmos evolutivos multiobjetivo híbridos, basados en optimización mediante cúmulos de partículas (PSO) y búsqueda dispersa: el primero se caracteriza por tener un mecanismo de selección basado en optimización global, el segundo algoritmo se caracteriza por contar con un mecanismo de selección basado en exploraciones de diversas regiones dentro de la población secundaria. Ambos algoritmos se hibridizan con la búsqueda dispersa, a fin de aprovechar los mecanismos de diversificación de esta metaheurística. La motivación de esta hibridación es aprovechar las características que nos brinda cada uno de los algoritmos a combinarse. PSO ofrece una rápida convergencia al adoptar un nuevo criterio de selección de líderes propuesto en esta tesis. Por su parte la búsqueda dispersa nos brinda una mayor diversificación de soluciones para generar las partes faltantes del frente de Pareto.
Las dos propuestas realizadas son evaluadas utilizando funciones de prueba estándar. Los resultados obtenidos se comparan con respecto al NSGA-II y el SPEA2, que son algoritmos representativos del estado del arte en el Área. Nuestra propuesta muestra tener una mejor convergencia y dispersión de soluciones en la mayoría de las funciones realizando tan solo 4,000 evaluaciones de la función de aptitud.

Abstract

In the real world, there is a large number of optimization problems for which mathematical programming techniques cannot guarantee that the solution obtained is optimum and, in many of them, such methods are not even applicable. It is precisely in these problems in which the use of metaheuristics is a viable choice. From the many metaheuristics currently available, evolutionary algorithms are among the most popular due to their conceptual simplicity and their efficacy. In the real world, multiobjective optimization problems appear very often. In them, we aim to optimize two or more objective functions which are normally in conflict with each other. The solution of multiobjective optimization problems using metaheuristics (particularly, evolutionary algorithms) is a topic that has become very popular in the last few years. In this document, we present two hybrid multiobjective evolutionary algorithms, based on particle swarm optimization (PSO) and scatter search: the first has a selection mechanism based on global optimization, the second algorithm consists of a selection mechanism based on explorations of diverse regions within the secondary population. Both algorithms are hybridized with scatter search, so the diversification mechanisms of this metaheuristic are exploited. The motivation for this hybridization is to exploit the features that these two metaheuristics can provide when combining them. PSO offers a fast convergence when adopting a new leader selection criterion proposed in this thesis. On the other hand, scatter search provides us with a greater diversity of solutions, which are used to fill the gaps in the generated Pareto fronts. The two proposed approaches are evaluated using standard test functions and metrics. Our results are compared with respect to the NSGA-II and SPEA2, which are algorithms representative of the state-of-the-art in the area. Our proposed approach exhibits a better convergence and spread of solutions in most of the test functions adopted, while performing only 4,000 fitness function evaluations.