Técnicas de Auto-Adaptación para Algoritmos Evolutivos Multi-objetivo

Edgar Gerardo Yáñez Oropeza

            
Texto completo de la Tesis    



Resumen

En la actualidad, el uso del cómputo evolutivo se ha vuelto muy popular como herramienta para dar soluciones a diferentes problemas del mundo real. En el ámbito de los problemas multi-objetivo, existen diversas propuestas basadas en cómputo evolutivo que son muy populares en la literatura especializada. Sin embargo, las diferentes herramientas propuestas en el campo del cómputo evolutivo multi-objetivo tienen una importante desventaja: requieren un ajuste cuidadoso de sus parámetros, el cual suele realizarse de forma empírica, siendo además distinto para cada problema a resolverse. Dicho ajuste empírico de parámetros busca balancear la fase de exploración con la de explotación del algoritmo evolutivo utilizado, a fin de que éste logre los mejores resultados posibles.

El objetivo principal de esta tesis fue definir un algoritmo evolutivo multiobjetivo que no requiriera parámetros a ser definidos por el usuario. Para alcanzar dicho objetivo, fue necesario definir diferentes técnicas de autoadaptación de parámetros para un algoritmo evolutivo multi-objetivo del estado del arte, el NSGA-II. Dichas técnicas de auto-adaptación permiten que el algoritmo evolutivo defina, por sí mismo y durante su ejecución, los valores más adecuados de sus parámetros más importantes. Para analizar el desempeño del esquema propuesto, se evaluó su comportamiento usando doce problemas de prueba, tomados de la literatura especializada. Los resultados obtenidos por el esquema propuesto se compararon con respecto a los del NSGA-II original, concluyéndose que la propuesta es una alternativa viable para realizar optimización evolutiva multi-objetivo libre de parámetros.


          Abstract

Nowadays, the use of evolutionary computation (EC) techniques has become a very popular tool to solve a variety of real-world problems. Within multi-objective optimization problems, several EC-based proposals currently exist, and are very popular in the specialized literature. However, the different EC tools currently available have an important drawback: they require a careful fine-tuning of their parameters, and such fine-tuning is normally done in an empirical way, being different for each problem to be solved. Such empirical fine-tuning of parameters aim to balance the exploration and exploitation phases of the evolutionary algorithm being used, such that it achieves the best possible results.

The main goal of this thesis was to define a multi-objective evolutionary algorithm (MOEA) that does not require any user-defined parameters. In order to achieve such goal, it was necessary to define different techniques to self-adapt the parameters of a state-of-the-art MOEA, the NSGA-II. Such self-adaptation techniques allow that the MOEA defines, by itself, and during its execution, the most appropriate values for its most important parameters.

In order to assess the performance of the proposed approach, its behavior was evaluated using twelve test problems taken from the specialized literature. The results obtained by the proposed approach were compared with respect to those produced by the original NSGA-II, concluding that the proposed approach is a viable alternative to perform parameterless evolutionary multi-objective optimization.