Departamento de Computación

A pesar del actual uso extendido de los Algoritmos Evolutivos Multiobjetivo (AEMOs) para la resolución de Problemas de Optimización Multi-objetivo (POMs), su costo computacional (medido en términos del número de evaluaciones de la función de aptitud) continúa siendo una de sus principales limitaciones cuando son utilizados en aplicaciones del mundo real. A fin de abordar este problema, una variedad de enfoques híbridos combinando técnicas de programación matemática con un AEMO han sido propuestos recientes años. De esta manera, mientras que el AEMO explora todo el espacio de búsqueda, las técnicas de programación matemática explotan las regiones prometedoras dadas por el mismo AEMO. La mayoría de estos enfoques híbridos dependen de técnicas de programación matemática basadas en gradientes. Por lo tanto, cuando las funciones no son diferenciables, estas técnicas llegan a ser poco prácticas y por tanto, deben explorarse otras alternativas, tales como los métodos de búsqueda directa, es decir, métodos de programación matemática que no requieren información del gradiente. En esta tesis, se presentan diferentes estrategias para hibridizar un popular método de búsqueda directa (el algoritmo de la búsqueda del simplex no lineal (NSS)) con un AEMO. En primer lugar, presentamos una extensión del algoritmo NSS (que fue originalmente propuesto para optimización mono-objetivo) para lidiar con POMs. El objetivo principal de este estudio es analizar y explotar las propiedades del algoritmo NSS cuando es utilizado para aproximar soluciones al conjunto de óptimos de Pareto mientras se mantiene una buena representación del frente de Pareto. Con base en evidencia experimental, concluimos que el algoritmo NSS es una buena alternativa para ser utilizado como un motor de búsqueda local en un AEMO. Después, tomamos las ideas propuestas en la extensión del algoritmo NSS para optimización multi-objetivo para ser acoplado como un motor de búsqueda local en diferentes AEMOs. Esto dio pie a diferentes enfoques híbridos, los cuales fueron validados usando problemas de prueba y medidas de desempeño estándar tomados de la literatura especializada.

Abstract

In spite of the current widespread use of Multi-Objective Evolutionary Algorithms (MOEAs) for solving Multi-objective Optimization Problems (MOPs), their computational cost (measured in terms of fitness function evaluations performed) remains as one of their main limitations when applied to real-world applications. In order to address this issue, a variety of hybrid approaches combining mathematical programming techniques with a MOEA have been proposed in the last few years. In this way, while the MOEA explores the whole search space, mathematical programming techniques exploit the promising regions given by the same MOEA. Most of these hybrid approaches rely on mathematical programming techniques based on gradients. Therefore, when the functions are not differentiable, these mathematical programming techniques become impractical, and then, other alternatives need to be explored, such as the direct search methods, i. e., mathematical programming methods that do not require gradient information. In this thesis, we present different strategies to hybridize a popular direct search method (the Nonlinear Simplex Search (NSS) algorithm) with a MOEA. First, we present an extension of the NSS (which was originally introduced for single-objective optimization) for dealing with MOPs. The main goal of this study is to analyze and exploit the properties of the NSS algorithm when it is used to approximate solutions to the Pareto optimal set while maintaining a reasonably good representation of the Pareto front. Based on experimental evidence, we conclude that the NSS is a good alternative to be used as a local search engine into a MOEA. Then, we take the ideas proposed in the extension of the NSS for multi-objective optimization to be coupled as a local search engine into different MOEAs. This gave rise to different hybrid approaches which were validated using standard test problems and performance measures taken from the specialized literature.