El algoritmo de optimización mediante cúmulos de partículas (Particle Swarm Optimization o PSO) es una metaheurística cuyo principio de funcionamiento se inspira en el comportamiento de ciertos animales que se mueven en grupo, tales como las aves o los peces. Estos animales son capaces de resolver, de forma conjunta, problemas complejos como el buscar fuentes de alimento. Al realizar esta tarea de forma cooperativa, se incrementa el área de búsqueda cubierta y con ello la probabilidad de éxito. Esto contrasta con realizar una búsqueda individual que tomaría mucho tiempo y que, posiblemente, terminaría con un final negativo. Desde la primera versión del algo ritmo de PSO publicada en 1995, hasta la fecha, se continúan desarrollando mejoras al algoritmo. Esto se debe, principalmente, al surgimiento de problemas de optimización cada vez más complejos. Uno de ellos es precisamente la optimización global de alta dimensionalidad (100 o más variables), que es un dominio en el que la mayoría de las metaheurísticas utilizadas para optimización suelen tener un rendimiento pobre. Si bien el principio de funcionamiento del PSO original ayuda en gran medida a que el algoritmo sea robusto, a medida que aumenta la dimensionalidad del problema, el tamaño del espacio de búsqueda crece exponencialmente, lo cual incrementa considerablemente la dificultad de encontrar el óptimo global. A este fenómeno se le denomina “maldición de la dimen sionalidad” e implica un mayor consumo de los recursos necesarios para encontrar una solución aceptable, ya que resulta más difícil y costoso (computacionalmente hablando) recorrer el espacio de búsqueda. En específico, en este trabajo nos concentramos en mejorar una de las versiones de PSO creadas para resolver problemas de optimización global de alta dimensionalidad. El algoritmo propuesto utiliza una especie de rastro que guardará información sobre cómo se comportan las partículas en determinado momento en el medio en el que se encuentran (espacio de búsqueda). Esto tiene el propósito de ir adaptando en tiempo real el comportamiento social y cognitivo de cada partícula y hacer más eficiente la exploración y la explotación de soluciones prometedoras. Para validar el algoritmo propuesto se utilizó el conjunto de problemas del 2013 IEEE Congress on Evolutionary Computation (CEC’2013), el cual contiene problemas de optimización global de gran escala. El conjunto consta de quince problemas que involucran diversos desafíos que se pre sentan en problemas del mundo real, tales como el que haya múltiples óptimos locales o la no separabilidad entre variables. Este conjunto constituye un buen punto de referencia para probar el rendimiento de nuestro algoritmo frente a otros del estado del arte. Los resultados reportados en esta tesis indican que el algoritmo propuesto proporciona mejores resultados que los algoritmos con respecto a los que fue comparado, además de mantener un funcionamiento relativamente simple, lo cual facilita su implementación y uso.
Abstract
Particle Swarm Optimization (PSO) is a metaheuristic which is inspired on the behavior of some animals that move in groups, such as birds and fish. Such animales are capable of solving, collecti vely, complex problems such as finding food sources. When performing this task in a cooperative way, the search area covered gets increased and this also increases the probability of success. This contrasts with performing individual searches, which would take a lot of time and would probably have a negative ending. Since the original version of PSO published in 1995 to date, a variety of improved versions of the algorithm have been developed. This has been motivated by the rise of problems of increased complexity. Large scale global optimization (100 or more decision variables) is precisely one of such complex problems. Since this is a domain in which most of the existing optimization metaheuristics have a poor performance. Although the working principle of the original PSO algorithm contributes to its robustness, as we increase the dimensionality of a problem, the size of the search space grows exponentially, which considerably increases the difficulty of finding the global optimum. This phenomenon is known as “the curse of dimensionality” and implies a greater consumption of the resources required to find an acceptable solution, since it becomes more difficult and costly (computationally speaking) to traverse the search space. Specifically, in this work, we focus on improving PSO versions designed to solve large scale global optimization problems. The proposed algorithm uses some sort of trail that stores information about the behavior of the particles in a given moment in the medium in which they are located (the search space). This aims to adapt, in real time, the social and cognitive behavior of each particle, in order to make more efficient the exploration and the exploitation of promising solutions. In order to validate the proposed algorithm, we adopted the test problems from the 2013 IEEE Congress on Evolutionary Computation (CEC’2013), which consist of large scale global optimization problems. This set contains fifteen problems that involve several challenges that arise in real-world problems such as the presence of local optima, or non-separability of the decision variables. This set constitutes a good reference to test the performance of our proposed algorithm with respect to others from the state of the art. The results reported in this thesis indicate that the proposed algorithm provides better results than those of the algorithms with respect to which it was compared, while keeping a relatively simple behavior, which facilitates its implementation and use.
