Departamento de Computación

Existen muchos problemas de optimización global del mundo real que contienen un gran número de variables (100 o más) las cuales se definen mediante números reales. A éstos se les denomina "problemas de optimización global de gran escala" y se caracterizan por tener un espacio de búsqueda muy grande. Estos problemas son muy dificiles de resolver mediante técnicas de programación matemática debido a que suelen contar con un gran número de óptimos locales en los que los algoritmos pueden quedar fácilmente atrapados. Adicionalmente, la solución de estos problemas suele involucrar un costo computacional considerable, el cual crece con la dimensionalidad del problema. Estas limitantes han motivado el uso de técnicas alternativas de búsqueda y optimización, de entre las que destacan las metaheurísticas. En esta tesis se propone el uso de una metaheurística bio-inspirada llamada "optimización mediante cúmulos de partículas" (PSO, por sus siglas en inglés) para optimización global de gran escala. PSO simula los patrones de vuelo de un grupo de aves que buscan comida y ha sido usada de manera exitosa en una amplia variedad de problemas de optimización global. La principal contribución de esta tesis es el desarrollo de una versión del PSO que usa una población muy pequeña (no más de cinco partículas) para resolver problemas de optimización global de gran escala. El algoritmo propuesto (llamado micro-PSO o m-PSO) es comparado con respecto a algoritmos del estado del arte en el área, utilizando problemas de prueba estándar de la literatura especializada

Abstract

There are many real-world global optimization problems having a large number of decision variables (100 or more) which are defined through the use of real numbers. These are the so-called "large scale global optimization problems" and they are characterized for having a very large search space. These problemas are very difficult to solve using mathematical programming techniques, because they normally have a large number of local optima in which an algorithm can get easily trapped. Additionally, the solution to these problems normally involves a considerably high computational cost, which increases with the dimensionality of the problem. These limitations have motivated the use of alternative search and optimization techniques, from which metaheuristics are worth emphasizing. In this thesis, we propose the use of a bio-inspired metaheuristic called "particle swarm optimization" (PSO) for large scale global optimization. PSO simulates the flight patterns of a flock of birds seeking for food, and it has been successfully used in a wide variety of global optimization problems. The main contribution of this thesis is the development of a PSO version that adopts a very small population size (no more than five particles) to solve large scale global optimization problems. The proposed algorithm (called micro-PSO or m-PSO) is compared with respect to state-of-the-art algorithms from the area, adopting standard test problems from the specialized literature