La optimización mediante cúmulos de partículas (PSO, por sus siglas en inglés) es una metaheurística que está inspirada en el comportamiento social de una parvada de aves o un grupo de peces en busca de comida. El PSO opera sobre un conjunto de partículas que se mueven a lo largo del espacio de búsqueda utilizando su mejor posición visitada previamente, así como las posiciones de los vecinos a los que se encuentra conectada. Se ha demostrado experimentalmente que la forma en que se conectan estas partículas (es decir, la topología cumular) influye en el desempeño del PSO. En consecuencia, la selección de una topología adecuada resulta fundamental para que la metaheurística tenga un buen desempeño. Debido a su simplicidad, el PSO ha sido modificado en varias ocasiones para resolver problemas multiobjetivo. La optimización mediante cúmulos de partículas para problemas multiobjetivo (MOPSO, por sus siglas en inglés) almacena las mejores posiciones visitadas por todas las partículas en un cúmulo o archivo externo. Por tanto, cada partícula en un MOPSO se mueve a lo largo del espacio de búsqueda utilizando su mejor posición previamente visitada, así como una posición del archivo externo que es seleccionada mediante un criterio dado por el usuario o el algoritmo correspondiente. A pesar de la existencia de una amplia variedad de MOPSOs, el impacto que tiene la topología cumular en su desempeño ha sido poco estudiada (hasta ahora, este tema se había abordado solo para unos pocos problemas con dos funciones objetivo). Por lo tanto, resulta relevante el análisis a profundidad de como afecta la topología cumular el desempeño de un MOPSO. Dicho análisis debiera permitir una mejor comprensión del funcionamiento de los MOPSOs, e incluso debiera conducirnos a mejoras en su desempeño.
En esta tesis estudiamos precisamente el impacto que tiene una topología cumular en el desempeño de un MOPSO. En primer lugar, proponemos dos esquemas de inserción de una topología, ya que un MOPSO está sujeto de manera natural a una topología totalmente conectada por lo que un esquema de inserción permite utilizar una topología distinta. Posteriormente, incorporamos el mejor esquema de inserción en tres MOPSOs representativos del estado del arte (el MOPSOhv (basado en un indicador de desempeño), el dMOPSO (basado en descomposición) y el SMPSO (basado en optimalidad de Pareto)) y analizamos la influencia que tienen las topologías estrella, anillo, rueda, Von Neumann y árbol en su desempeño. En este estudio concluimos que una topología cumular impactaría de forma distinta el desempeño de diferentes MOPSOs. Sin embargo, la selección de una topología y de un esquema de inserción adecuados pueden mejorar el desempeño original de un MOPSO. Adicionalmente, concluimos que si bien una topología impacta el desempeño de un MOPSO, este efecto disminuye conforme aumenta el número de objetivos.
Abstract
Particle swarm optimization (PSO for short) is a metaheuristic inspired on the social behavior of a bird flock or school of fish looking for food. PSO operates on a set of particles that move throughout the search space using the best position that they previously visited combined with the positions of the neighbors connected to the particle. There is experimental evidence indicating that the way in which the particles are connected (i.e., the swarm topology) has an in uence on the performance of the particle swarm optimizer. Consequently, the choice of a proper topology plays a fundamental role on the performance of this metaheuristic. Due to its simplicity, PSO has been extended in multiple occasions for the solution of multiobjective problems. The so-called multi-objective particle swarm optimizers (MOPSOs) store the best visited positions of all particles in an external swarm or archive. Therefore, each particle in a MOPSO moves through the search space using its best previously visited positions combined with a position from the external archive which is selected using a criterion defined by the user or the corresponding algorithm. In spite of the existence of a wide variety of MOPSOs, the impact that the swarm topology has on their performance has been scarcely studied (so far, this topic had been studied only for a few bi-objective problems). Consequently, it is relevant to conduct an in-depth analysis of the way in which the swarm topology affects the performance of a MOPSO. Such an analysis should allow a better understanding of the way in which a MOPSO works, and should even lead us to improvements in their performance.
In this thesis, we precisely study the impact that a swarm topology has on the performance of a MOPSO. First, we propose two topology insertion schemes, since a MOPSO is naturally subject to a fully connected topology and, therefore, the use of an insertion scheme allows the use of a diferent topology. Then, the best insertion scheme is incorporated into three MOPSOs that are representative of the state-of-the-art in the area (namely, MOPSOhv (which is based on a performance indicator), dMOPSO (which is based on decomposition) and SMPSO (which is based on Pareto optimality)) and we analyze the influence that different topologies (i.e., star, ring, wheel, Von Neumann and tree) have on their performance. In this study, we conclude that a swarm topology impacts the performance of different MOPSOs in different ways. However, the selection of the proper topology and insertion scheme can improve the original performance of a MOPSO. Additionally, we conclude that even when the topology will impact the performance of a MOPSO, this effect decreases as we increase the number of objectives.
