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.
