Una de las técnicas más comúnmente usadas para resolver problemas de optimización multi-objetivo (POMs) son los llamados algoritmos evolutivos multi-objetivo (AEMOs), los cuales son metaheurísticas poblacionales que emulan el proceso evolutivo biológico. Los AEMOs usan el principio de “supervivencia del más apto”, de la teoría de Darwin para resolver POMs de alta complejidad. La población utilizada por los AEMOs presenta la ventaja de permitir, con una manipulación adecuada, procesar un conjunto de soluciones óptimas a cada iteración, en vez de operar con una sola a la vez, como ocurre con las técnicas de programación matemática. Sin embargo, el uso de una población hace también que los AEMOs requieran un mecanismo que les permita mantener un cierto grado de diversidad durante el proceso evolutivo. De no mantener adecuadamente la diversidad, los resultados producidos por un AEMO serán de muy baja calidad o se podría producir convergencia prematura. Esto ha motivado el desarrollo de una amplia variedad de técnicas de preservación de diversidad. Estas técnicas pueden ser clasificadas de forma general en tres categorías: (1) estimadores de densidad, (2) restricciones a la cruza y (3) poblaciones secundarias. Los POMs con cuatro o más objetivos, también conocidos como problemas de optimización con muchos objetivos, añaden nuevos desafíos a los AEMOs, principalmente debido a que el incremento en el número de objetivos conlleva un incremento exponencial en el tamaño del espacio de búsqueda. Consecuentemente, esto genera una disminución en la presión de selección en los AEMOs basados en dominancia de Pareto, y también produce un costo computacional que puede volverse prohibitivo en algunos casos (p-ej., cuando se usa un mecanismo de selección basado en el hipervolumen). Adicionalmente, existen aún diferentes áreas sin explorar en torno a la preservación de diversidad, específicamente para problemas de alta dimensionalidad. El trabajo presentado en esta tesis tiene el objetivo de contribuir al estado del arte de técnicas de preservación de diversidad en problemas de optimización con muchos objetivos. El trabajo presentado en esta tesis se concentra en dos áreas principales de investigación. La primera, concerniente al uso de restricciones a la cruza basadas en energía-s, propone una nueva y útil técnica de preservación de diversidad basada en un conjunto de estas restricciones. Nuestros resultados experimentales muestran que el uso de un indicador de diversidad (energía-s) en una técnica de preservación de diversidad (restricciones a la cruza) produce una mejora en problemas de optimización con muchos objetivos. Por otro lado, investigamos el uso de evolución gramatical para producir nuevos componentes de un AEMO. Específicamente, generamos nuevas funciones de escalarización (usadas en AEMOs basados en descomposición) y nuevas aproximaciones del hipervolumen (usadas en AEMOs basados en indicadores). Todos los componentes que generamos con este método producen mejores resultados al ser comparados contra alternativas del estado del arte. Esto indica que el uso de evolución gramatical para generar componentes de un AEMO es una área de investigación prometedora, y que es una alternativa viable para generar nuevas funciones de escalarización, aproximaciones del hipervolumen, y potencialmente, nuevas técnicas de preservación de diversidad (p.ej., nuevos estimadores de densidad).
Abstract
One of the most commonly used techniques for solve multi-objective optimization problems (MOPs) are the so-called multi-objective evolutionary algorithms (MOEAs), which are population-based metaheuristics that emulate the evolutionary process that occurs in Nature. MOEAs use the “survival of the fittest” principle from Darwin’s evolutionary theory to solve high complexity MOPs. The population adopted by MOEAs presents the advantage of allowing, with a proper manipulation, the processing of a set of optimal solutions at each iteration, instead of operating with one solution at a time, as occurs with mathematical programming techniques. However, the use of a population, also makes MOEAs to require a mechanism that allows them to keep a certain level of diversity during the evolutionary process. If diversity is not properly maintained, the results produced by a MOEA will be of very low quality or premature convergence may occur. This has motivated the development of a wide variety of techniques to maintain diversity. Such techniques can classified, in general, in three categories: (1) density estimators, (2) mating restrictions and (3) secondary populations. MOPs having four or more objectives, which are also known as manyobjective optimization problems (MaOPs), add new challenges to MOEAs, mainly because the increase in the number of objectives involves an exponential increase in the size of the search space. Consequently, this generates a decrease in the selection pressure of MOEAs based on Pareto dominance and also produces a computational cost that may become prohibitive in some cases (e.g., when using a selection mechanism based on the hypervolume). Additionally, there are still several unexplored research areas around diversity maintenance, specifically for MaOPs. The work presented in this thesis has as its main goal to contribute to the state of the art in diversity maintenance techniques in MaOPs. The work presented here focuses on two main research areas. The first is related to the use of mating restrictions adopting s-energy, in which we propose a new and useful diversity maintenance technique based on the use of a set of mating restrictions. Our experimental results show that the use of a diversity indicator (s-energy) in a diversity maintenance technique (mating restrictions) produces an improvement in MaOPs. On the other hand, we also studied the use of grammatical evolution to produce new components of a MOEA. Specifically, we generated new scalarizing functions (used in MOEAs based on decomposition) and new hypervolume approximations (used in MOEAs based on performance indicators). All the components that we generated using this approach are able to produce better results when compared with alternative approaches from the state of the art. This indicates that the use of grammatical evolution to generate components of a MOEA is a promising research area, and that this is indeed a viable choice to generate new scalarizing functions, hypervolume approximation and, potentially, new diversity maintenance techniques (e.g., new density estimators).
