Resumen

En esta tesis, se presentan diferentes técnicas que tienen como objetivo el mejorar la eficiencia de los algoritmos evolutivos para problemas de optimización multi-objetivo. Por eficiencia, nos referimos a reducir el número de evaluaciones de la función objetivo realizadas por el algoritmo evolutivo multi-objetivo al resolver problemas de dimensionalidad moderada (de hasta 30 variables de decisión). Cuando tratamos de resolver un problema multiobjetivo, es muy importante hacer una buena exploración al inicio y encontrar rápidamente soluciones prometedoras. Después, se necesita una explotación de las buenas soluciones para acelerar la convergencia y, finalmente, encontrar el frente de Pareto verdadero del problema. Además, se necesita un mecanismo para retener a las soluciones no dominadas con una buena distribución a lo largo del frente de Pareto. En esta tesis, lidiamos con cada uno de estos problemas: la exploración, la explotación y la distribución de las soluciones.

En primer lugar, se propone un nuevo algoritmo evolutivo multi-objetivo basado en evolución diferencial y la teoría de los conjuntos borrosos, para mostrar cómo es que la hibridación de un algoritmo evolutivo con una alta velocidad de convergencia como lo es la evolución diferencial y un optimizador local basado en la teoría de los conjuntos borrosos, pueden ser una alternativa eficiente para construir un algoritmo robusto capaz de resolver problemas multi-objetivo con y sin restricciones. El algoritmo propuesto adopta el uso de un archivo externo con el fin de retener a las soluciones no dominadas encontradas durante el proceso evolutivo. Además, se utiliza el concepto de dominancia- € Pareto-adaptativa para obtener una buena distribución de las mejores soluciones. La idea principal del algoritmo es la de utilizar la evolución diferencial como el motor de búsqueda, intentando extender las buenas propiedades de convergencia mostradas en optimización global para el caso multi-objetivo. Después, la teoría de los conjuntos borrosos se adopta en una segunda etapa, con el fin de generar más soluciones no dominadas en la vecindad de aquellas soluciones no dominadas que produjo la primera etapa. Nuestro algoritmo híbrido es validado utilizando diferentes funciones de prueba estándar y medidas de desempeño que son utilizadas en la literatura especializada. Nuestros resultados finales son comparados con respecto a otros dos algoritmos que son representativas del estado del arte: NSGA-II, y SPEA2.

En segundo lugar, proponemos un algoritmo multi-objetivo usando el algoritmo basado en cúmulos de partículas para problemas multi-objetivo (MOPSO, por sus siglas en inglés), acoplado a un método de aproximación para explorar el espacio de búsqueda de manera eficiente. Con el fin de determinar el mejor método de aproximación, se llevo a cabo un pequeño estudio comparativo entre tres métodos: una red neuronal artificial (ANN), una red con funciones de base (RBF), y una máquina de vectores de soporte (SVM). El que mejor desempeño obtuvo de este estudio fueron las máquinas de vectores de soporte, que fue por tanto, la opción adoptada en nuestro algoritmo final. Además, se realizó un estudio comparativo entre los diferentes esquemas de selección del líder en el algoritmo MOPSO, con tal de encontrar el tipo de selección más adecuada. Sin embargo, los resultados de este algoritmo indican que las soluciones alcanzadas en un inicio no fueron lo eficientemente buenas en cuanto a su distribución, aunque sí respecto a su cercanía al frente de Pareto verdadero. En virtud de ello, decidimos agregar una segunda fase al algoritmo hibridizándolo con los conjuntos borrosos, que actúan como optimizadores locales con el objetivo de mejorar esa distribución de soluciones y producir una mejor aproximiación del frente de Pareto verdadero. Se demuestra que nuestro algoritmo híbrido sólo requiere de 2000 evaluaciones de la función de aptitud para resolver problemas de prueba con hasta 30 variables.

Por último, proponemos un mecanismo que puede ser visto como una variante de la dominancia- €, al cual llamamos dominancia- € Pareto-adaptativa (pa€ -dominancia). Nuestra propuesta intenta superar la principal limitación de la dominancia-€ , es decir, la pérdida de soluciones no dominadas que se encuentran en los extremos de la hiper-malla construida por el archivo externo, debido a la forma en que ésta selecciona a las soluciones dentro de cada caja.

In this thesis, we present different techniques that aim to improve the efficiency of the multi-objective evolutionary algorithms. By efficiency, we refer to reducing the number of fitness function evaluations performed by a multi-objective evolutionary algorithm when solving problems of moderate dimensionality (up to 30 decision variables). When solving a multi-objective problem, it is very important to do a good exploration at the beginning of the search and find quickly promising solutions. After that, an exploitation of those good solutions is needed to accelerate the convergence and finally get to the true Pareto front of the multi-objective problem. Additionally, a mechanism to keep the nondominated solutions is normally used to retain a well-distributed set of solutions along the Pareto front. We present here mechanisms that tackle each of these problems: exploration, exploitation and distribution.

First, we propose a new multi-objective evolutionary algorithm (MOEA) based on differential evolution and rough sets theory to show how the hybridization of a fast multi-objective evolutionary algorithm and a local search method based on the use of rough sets, is an efficient alternative to obtain a robust algorithm able to solve difficult unconstrained and constrained multiobjective optimization problems. The proposed approach adopts an external archive in order to retain the nondominated solutions found during the evolutionary process. Additionally, the approach also incorporates the concept of pao-dominance to get a good distribution of the solutions retained. The main idea of the approach is to use differential evolution (DE) as our main search engine, trying to translate its good convergence properties exhibited in single-objective optimization to the multi-objective case. Rough sets theory is adopted in a second stage of the search in order to improve the spread of the nondominated solutions that have been found so far. Our hybrid approach is validated using standard test functions and performance measures commonly adopted in the specialized literature. Our results are compared with respect to two approaches that are representative of the state-of-the-art in the area: NSGA-II, and SPEA2.

Secondly, we propose an approach in which a multi-objective particle swarm optimizer (MOPSO) is coupled to a surrogate method in order to explore the search space in an efficient manner. In order to determine which is the most appropriate surrogate method to be adopted, a small compara tive study among three surrogate methods is conducted: an artificial neural network (ANN), a radial basis function (RBF) and a support vector machine (SVM). The best performer in this comparative study was the support vector machine, which was, therefore, adopted for our approach. Also, we perform a comparative study among different leader selection schemes in a MOPSO, in order to determine the most appropriate approach to be adopted for solving the sort of problems of our interest. However, our results indicated that the spread of solutions achieved by our surrogate-based MOEA was poor. Thus, we decided to introduce a second phase to the algorithm in which it is hybridized with the rough sets in order to improve the spread of solutions and reach the true Pareto front. In this case, the rough sets act as a local search approach which is able to generate solutions in the neighborhood of the nondominated solutions previously generated. We show that our proposed hybrid approach only requires 2,000 fitness function evaluations in order to solve test problems with up to 30 decision variables.

Finally, we propose a mechanism that can be seen as a variant of odominance, which we call Pareto-adaptive o-dominance (pao-dominance). Our proposed approach overcomes the main limitations of o-dominance: the loss of several nondominated solutions from the hypergrid adopted in the archive because of the way in which solutions are selected within each box.