Departamento de Computación

En el mundo real, existe una gran cantidad de problemas de optimización para los cuales los métodos clásicos de programación matemática no pueden garantizar que la solución obtenida sea óptima. Además, estos métodos pueden resultar poco eficientes y en algunos casos inoperables para un determinado problema. Para estos problemas más complejos de optimización, es cuando se justifica plenamente el uso de metaheurísticas. Los algoritmos evolutivos son metaheurísticas que en los últimos años se han vuelto muy populares debido a su simplicidad conceptual y su eficiencia en este tipo de problemas. Los algoritmos evolutivos han sido utilizados exitosamente en el área de optimización multiobjetivo, debido a que por su naturaleza (basada en poblaciones) permiten generar varias soluciones del conjunto de óptimos de Pareto en una sola ejecución. Desafortunadamente, cuando la función objetivo es computacionalmente costosa de evaluar, los algoritmos evolutivos suelen volverse imprácticos. En esta tesis presentamos dos nuevos algoritmos híbridos basados en cómputo evolutivo y métodos clásicos de optimización. El primero denominado Nonlinear Simplex Search Differential Evolution (NSSDE) para optimización global, está basado en la heurística de evolución diferencial (ED) y utiliza el método de Nelder-Mead como buscador local. La finalidad de esta implementación es diseñar una estrategia de búsqueda local, que pueda ser utilizada de manera similar en el problema de optimización multiobjetivo (el cual es el objetivo principal de esta tesis). El segundo algoritmo híbrido denominado Nonlinear Simplex Search Genetic Algorithm (NSS-GA) para optimización multiobjetivo, está basado en el algoritmo evolutivo multiobjetivo Non-dominated Sorting Genetic Algorithm-II (NSGA-II), acoplando los métodos clásicos de optimización matemática de Nelder-Mead (para funciones multidimensionales) y el de la sección dorada (para funciones unidimensionales) que fungen como buscadores locales. La motivación principal de estas dos hibridizaciones, es aprovechar el poder explorativo de los algoritmos evolutivo y el poder explotativo de los métodos de programación matemática. Los resultados obtenidos en nuestras dos propuestas NSSDE y NSS-GA, son comparados con respecto a los obtenidos por los algoritmos evolutivos simples ED y NSGA-II, respectivamente. Nuestras propuestas algorítmicas muestran tener mejores resultados, en la mayoría de las funciones de prueba adoptadas.

Abstract

In the real world, there are a lot of optimization problems for which traditional methods of mathematical programming cannot guarantee that the solution obtained is optimun. Furthermore, these methods can be inefficient and in some times inoperable for a particular problem. For these more complex optimization problems, the use of metaheuristics is fully justified. The evolutionary algorithms are metaheuristics which in the recent years have become very popular because for their conceptual simplicity and efficiently in these types of problems. Evolutionary algorithms have been used successfully in the multiobjective optimization area, for their nature (based on a population) allow to generate multiple solutions of the Pareto optimal set in a single run. Unfortunately, when the function is computationally expensive to evaluate, evolutionary algorithms often become impractical. In this thesis, we present two new hybrid algorithms based on evolutionary computation and classical optimization methods. The first algorithm called Nonlinear Simplex Search Differential Evolution (NSSDE) for global optimization, is based on the Differential Evolution heuristic and uses the Nelder-Mead method as its local search mechanism. The purpose of this implementation, is to design a local search strategy, which can be used in an analogous way in the multiobjective optimization problem (which is the main objective of this thesis). The second hybrid algorithm proposed is called Nonlinear Simplex Search Genetic Algorithm (NSS-GA) for multiobjective optimization. This algorithm is based on the Non-dominated Sorting Genetic Algorithm-II (NSGA-II), coupled with the classical methods of mathematical programming Nelder-Mead (for multidimensinal functions) and the golden section (for unidimensional functions) both act as local search engines. The main motivation for these two hybridizations, is to exploit the explorative power of the evolutionary algorithms and the exploitative power of the mathematical programming methods. The results obtained in our two proposals, NSSDE and NSS-GA, are compared with respect to the results obtained by the original evolutionary algorithms adopted, DE and NSGA-II, respectively. Our proposed approaches have shown better results in most of the test funcions adopted.