Departamento de Computación

Texto completo de la Tesis            Video del evento          

Resumen

En el mundo real, la mayor parte de los problemas de optimización tienen dos o más objetivos (normalmente en conflicto) que deseamos satisfacer al mismo tiempo. Este tipo de problemas, llamados multi-objetivo, han sido abordados con diversas técnicas de programación matemática. Sin embargo, no existe ningún método de optimización que pueda garantizar la solución de cualquier problema multi-objetivo no lineal, lo que abre la puerta al uso de métodos alternativos de optimización. En los últimos 20 años, las metaheurísticas bio-inspiradas (sobre todo, los algoritmos evolutivos) han sido ampliamente utilizadas para resolver problemas de optimización multi-objetivo no lineales, debido, entre otras cosas, a su generalidad, sus pocos requerimientos de información y su uso de una población, que les permite generar varias soluciones no dominadas en una sola ejecución algorítmica. La optimización mediante cúmulos de partículas, es un tipo de metaheurística bioinspirada que simula el comportamiento de un grupo de aves que buscan comida. Este tipo de técnica ha mostrado ser un optimizador mono-objetivo muy eficiente, lo cual constituye una motivación importante para intentar extenderla a la solución de problemas multi-objetivo. En este trabajo de tesis se propone un nuevo algoritmo de optimización mediante cúmulos de partículas multi-objetivo utilizando los operadores del estándar de 2011 de esta metaheurística, llamado SPSO2011 [1]. Ésta es la versión mono-objetivo más competitiva que se conoce a la fecha del algoritmo de optimización mediante cúmulos de partículas, lo que la hace ideal para extenderla a la solución de problemas multi-objetivo. El algoritmo propuesto se basa en un método de descomposición, a fin de explotar de mejor manera los operadores del SPSO2011. El desempeño del algoritmo propuesto se compara con el de algoritmos evolutivos multi-objetivo del estado del arte (MOEA/D)[2], y con el de optimizadores multi-objetivo basados en cúmulos de partículas (SMPSO [3] y dMOPSO [4]), usando problemas de prueba e indicadores de desempeño comúnmente utilizados en la literatura especializada.

Abstract

In the real world, most optimization problems have two or more (normally conflicting) objectives that we aim to satisfy at the same time. This type of problems, called multi-objective, has been tackled using different mathematical programming techniques. However, there is no optimization method that can guarantee the solution of every nonlinear multi-objective optimization problem, which opens the door to the use of alternative optimization problems. In the last 20 years, bio-inspired metaheuristics (particularly, evolutionary algorithms) have been widely used to solve nonlinear multi-objective optimization problems, due to, among other things, their generality, their few information requirements, and their use of a population, which allows them to generate several non-dominated solutions in a single algorithmic execution. Particle swarm optimization is a type of bio-inspired metaheuristic that simulates the behavior of a group of birds seeking for food. This sort of technique has been shown to be a very efficient single-objective optimizer, which constitutes an important motivation to try to extend it to the solution of multi-objective problems. In this thesis work, we propose a new multi-objective particle swarm optimizer using the operators of the 2011 standard of this metaheuristic, called SPSO2011 [1]. This is the most competitive single-objective version known to date of particle swarm optimization, which makes it ideal to extend it to solve multi-objective problems. The proposed algorithm is based on decomposition, in order to better exploit the operators of SPSO2011. The performance of the proposed algorithm is compared with respect to that of stateof- the-art multi-objective evolutionary algorithms (MOEA/D) [2], and multi-objective particle swarm optimizers (SMPSO [3] and dMOPSO [4]) using standard test problems and performance indicators taken from the specialized literature.