Departamento de Computación

Sergio Jesús Alvarado García, "El punto a punto de las técnicas de búsqueda local para algoritmos de optimización multiobjetivo"

En el mundo real frecuentemente enfrentamos problemas que poseen múltiples objetivos, los cuales deben ser optimizados de manera concurrente llevándonos a los denominados problemas de optimización multiobjetivo (POMs). La dificultad de este tipo de problemas radica en que generalmente no se tiene una única solución posible, sino que por el contrario, existen un conjunto de soluciones que optimizan de diferente manera a cada uno de los objetivos. Una de las posibles y ampliamente aceptadas formas aceptadas de resolver POMs es el uso de lo que se conoce como algoritmos meméticos, v.g., algoritmos evolutivos a los que se les acoplan mecanismos de búsqueda local. El objetivo de esta tesis es el de extender un método de búsqueda local recientemente desarrollado: la búsqueda dirigida, o Directed Search (DS). Este nuevo algoritmo, inicialmente se utilizará como un método capaz de encontrar soluciones de un PMO por sí mismo, y posteriormente será utilizado en un algoritmo memético adoptando alguno de los algoritmos evolutivos multiobjetivo que se encuentran en el estado del arte a fin de producir un nuevo algoritmo memético. Una de las ideas fundamentales de este trabajo es el de utilizar el DS sin necesidad de calcular explícitamente el gradiente de las funciones objetivo. En vez de eso, se explorará el vecindario, a fin de producir un nuevo método de diferencias finitas. Como resultado, el algoritmo generado ha demostrado mejorar la convergencia de los algoritmos evolutivos multiobjetivo.

Abstract

In the real world one is often faced with problems that have multiple objectives that must be optimized concurrently leading to the so-called multiobjective optimization problems (MOPs). The main difficulty of these problems is that they do not have only one single solution, but instead consist of a set of solutions presented as different trade-os among the objectives. One possible and widely accepted way to solve MOPs numerically is to use memetic algorithms, i.e., evolutionary algorithms coupled with local search mechanisms. The goal of this thesis is to extend a recently developed local search strategy, the Directed Search (DS) method. This new method, should be first developed to work as a standalone algorithm, and will further on be integrated into state-of-the-art multi-objective evolutionary algorithms leading to a new memetic strategy. One of the main ideas of this work is to use DS without explicitly computing the objective's gradient. Instead, the neighborhood will be explored leading to a new finite difference approach. The proposed algorithm has shown to increases the convergence rate of the multiobjective evolutionary algorithms.