Departamento de Computación

Muchos problemas de la vida real requieren de la optimización de dos o más objetivos a la vez, los cuales, están en conflicto unos con otros al mismo tiempo. Por lo general, los problemas de optimización multi-objetivo no tienen una solución única sino un conjunto de soluciones que representan los diferentes compromisos entre los objetivos. La mayoría de los algoritmos evolutivos multi-objetivo utilizan la dominancia de Pareto como criterio de selección. Si bien este mecanismo es efectivo en problemas con dos o tres objetivos, no es escalable ya que la proporción de soluciones incomparables que se generan crece rápidamente al aumentar el número de objetivos. En este trabajo de tesis se utiliza la optimización mediante cúmulos de partículas (PSO), la cual es una técnica evolutiva inspirada en el comportamiento social de los bancos de peces. Se plantea una forma de hacer que un algoritmo de cúmulo de partículas resuelva problemas de optimización multi-objetivo. Al optimizador propuesto se le integra como mecanismo de selección la métrica denominada hipervolumen, a fin de obtener a los mejores líderes o guías en su proceso de búsqueda. Nuestra propuesta obtiene buenos resultados para problemas con dos y tres objetivos y presenta resultados prometedores para problemas con muchos objetivos (cuatro o más).

Abstract

Many real-life problems require optimization the simultaneous of two or more conflicting objectives. Usually, multiobjective optimization problems do not have a single solution but a set of them, representing the trade-offs among the objetives. Most multiobjective evolutionary algorithms use Pareto dominance as their selection criterion. This mechanism is effective in problems having two or three objectives but it does not properly scale since number of incomparable solutions that this selection criterion generates rapidly grows as the number of objectives increases. In this thesis we use Particle Swarm Optimization (PSO), which is an evolutionary technique inspired in the social behavior of fish schools. We present here a way to adapt PSOs that it can solve multiobjetive optimization problems. The proposed approach adopts as its selection mechanism, a performance measure called hypervolume to find the best leaders during the search process. Our proposed approach was able to obtain good results for problems with two and three objectives and presented promising results for problems with many objectives (more than three).