Departamento de Computación

En la actualidad existen varios métodos deterministas para resolver problemas de optimización con ciertas características específicas. Sin embargo, estos métodos pueden resultar ineficientes e incluso inadecuados al enfrentar problemas con alta dimensionalidad, discontinuos y multimodales. Además existen problemas con espacios de búsqueda muy grandes, los cuales no pueden ser resueltos en tiempo polinomial sino exponencial. En estos casos es donde se justifica el uso de las técnicas llamadas heurísticas. En particular, en esta tesis estamos interesados en las heurísticas pertenecientes a la computación evolutiva llamadas algoritmos evolutivos. Los algoritmos evolutivos se han utilizado exitosamente para resolver una amplia gama de problemas de optimización. Éstos operan sobre poblaciones, lo cual evita que fácilmente queden atrapados en óptimos locales y requieren poca información específica del problema, lo cual los hace herramientas de búsqueda más generales. La optimización mediante cúmulos de partículas (PSO) es una técnica evolutiva inspirada en el comportamiento social de las bandadas de aves.
En este trabajo presentamos dos algoritmos evolutivos basados en optimización mediante cúmulos de partículas. El primero fue desarrollado para resolver problemas de optimización mono-objetivo con restricciones. El segundo está diseñado para resolver problemas multiobjetivo sin restricciones. Ambos algoritmos utilizan un tamaño de población muy pequeño no mayor a cinco individuos.
Las dos propuestas realizadas son evaluadas utilizando funciones de prueba estándar. Los resultados del algoritmo mono-objetivo con restricciones presentado en esta tesis son comparados con respecto a tres técnicas representativas del estado del arte en el área. El número de evaluaciones de la funcion objetivo que nuestra propuesta requiere para alcanzar los óptimos globales es menor o igual que el número requerido por las técnicas con respecto a las cuales es comparada. Los resultados del algoritmo multiobjetivo sin restricciones presentado en este trabajo se comparan con respecto al Non-dominated Sorting Genetic Algorithm II (NSGA-II). Nuestra propuesta muestra poseer una mejor cobertura y distribución de las soluciones obtenidas, así como una rápida convergencia. En la mayoría de las funciones de prueba utilizadas, nuestro algoritmo requiere tan sólo de 3000 evaluaciones de la función objetivo.

Abstract

Currently, there are several deterministic methods for solving optimization problems with certain specific features. However, these methods may become inefficient and even inappropriate when facing high-dimensional, discontinuous and multimodal problems. Furthermore, there exist problems with a very large search space, which cannot be solved in polynomial time, but require exponential time. In these cases is in which the use of the so-called {\em heuristic} techniques is fully justified. Particularly, in this thesis we are interested in the heuristics within evolutionary computation, which are called evolutionary algorithms. Evolutionary algorithms have been successfully used to solve a wide variety of optimization problems. They operate on a population of solutions, which avoids that they get easily trapped in local optima, and require little specific-domain information, which makes them more general search engines. Particle swarm optimization (PSO) is a type of evolutionary algorithm inspired on the social behavior of a flock of birds.
In this work, we present two evolutionary algorithms based on PSO. The first was \mbox{developed} to solve constrained single-objective optimization problems. The second was designed to solve unconstrained multi-objective optimization problems. Both approaches adopt a very small population size no larger than five individuals. The two approaches developed as part of this work are validated using standard test \mbox{functions}. The results of the constrained single-objective optimizer presented in this thesis are compared with respect to three approaches representative of the state-of-the-art in the area. The number of evaluations of the objective function required by our \mbox{proposed} approach, in order to reach the global optima, is lower or equal to those required by the techniques with respect to which it was compared. The results of the unconstrained multi-objective optimization approach presented in this thesis are compared with respect to the Nondominated Sorting Genetic Algorithm II (NSGA-II). Our proposed approach is shown to provide a better coverage and spread of the solutions obtained, as well as a faster \mbox{convergence}. In most of the test functions adopted, our proposed approach requires only 3000 objective function evaluations. .