Optimización de Enjambre de Partículas

La metaheurística de Optimización de Enjambre de Partículas o PSO por sus siglas en inglés

(Particle Swarm Optimization), fue desarrollada por Kennedy Eberhart [1] y está inspirada en la
simulación de un modelo social simple observado en grupos de individuos tales como parvadas
de pájaros, enjambres de insectos y bancos de peces. Tal comportamiento social se basa en la
transmisión del suceso de cada individuo a los demás individuos del grupo, lo cual resulta en un
proceso sinergético que permite a los individuos satisfacer de la mejor manera posible sus
necesidades más inmediatas, tales como la localización de alimentos o de un lugar de cobijo.
Un sistema PSO combina un modelo “únicamente social”, el cual sugiere que los individuos
ignoran su propia experiencia y ajustan su conocimiento de acuerdo a las creencias exitosas de
los individuos en la vecindad; y un modelo “únicamente cognitivo”, el cual trata a los
individuos como seres aislados. Una partícula cambia de posición utilizando estos dos modelos
[2].
La metaheurística PSO ha mostrado ser muy eficiente para resolver problemas de optimización
de un sólo objetivo con rápidas tasas de convergencia [3], haciendo atractiva la idea de su
aplicación en la resolución problemas de optimización de múltiples objetivos.
Básicamente, la metaheurística PSO consiste en un algoritmo iterativo basado en una población
de individuos denominada enjambre, en la que cada individuo, llamado partícula, se dice que
sobrevuela el espacio de decisión en busca de soluciones óptimas. Así, dado un espacio de
decisión N-dimensional, cada partícula i del enjambre conoce su posición actual
X i =[ xi 1 , x i 2 , … , x i N ] , la velocidad V i=[ v i 1 , v i 2 , … , v ¿ ] con la cual ha llegado a dicha posición
y la mejor posición Pi=[ pi 1 , pi 2 , … , p ¿ ]en la que se ha encontrado, denominada mejor
personal. Además, todas las partículas conocen la mejor posición encontrada dentro del
enjambre G= [ g 1 , g2 ,… , g N ] , denominada mejor global. Existe otra variante en la que se
definen sobre el enjambre subgrupos de partículas, posiblemente solapados, a los que se
denominan vecindades, en tal caso las partículas también conocen la mejor posición encontrada
dentro de su vecindad Li=[ l i 1 ,l i 2 ,… , l ¿ ], a la que se denomina mejor local. Suponiendo el uso
de la información proveniente del mejor global, en cada iteración t del algoritmo PSO, cada
componente j de la velocidad y la posición de cada partícula i del enjambre se actualiza
conforme a:

vijt+1=ω × v tij +C 1 × rand () × ( p tij −xtij ) +C 2 × rand ()× ( gtij −x tij )

donde ω es el parámetro de inercia que regula el impacto de las velocidades previas en la

velocidad actual, influenciando el cambio entre las habilidades de exploración global (rango
amplio) o local (rango corto) de las partículas. Un peso inercial mayor facilita la exploración
global para buscar nuevas áreas, mientras que un peso inercial menor tiende a facilitar
exploración local para sintonizar finamente el área de búsqueda actual. Una correcta selección
del peso inercial puede proveer un balance entre las habilidades de búsqueda local y global, por
lo tanto, requiere menores iteraciones para encontrar el punto óptimo[4], C 1 es el parámetro
cognitivo que indica la influencia máxima de la mejor experiencia individual de la partícula en
su nueva velocidad y C 2 es el parámetro social que indica la influencia máxima de la
información social en el nuevo valor de velocidad de la partícula. Mientras que, rand ( ) es una
función que retorna un número aleatorio en el intervalo [0, 1], mediante el cual se determina la
influencia real de las informaciones individual y social en la nueva velocidad para la partícula.
La actualización de una partícula se ilustra de manera general en la figura 1.
 Figura 1. Actualización de una partícula

A los pesos C 1 y C 2 generalmente se les asigna el valor 2. Para obtener una mayor información
acerca de la influencia de estos parámetros en la efectividad del algoritmo PSO el lector puede
referirse a [4][5].
Cuando se opta por utilizar la información local proveniente de las vecindades para actualizar
las partículas, de manera a evitar que todas ellas sean influenciadas por una única mejor
posición, la ecuación se convierte en:

vijt+1=ω × v tij +C 1 × rand () × ( p tij −xtij ) +C 2 × rand ()× ( l tij −xtij )

Referencias Bibliográficas

[1] J. Kennedy and R. Eberhart, “Particle swarm optimization,” in Proceedings of ICNN’95-

international conference on neural networks, 1995, vol. 4, pp. 1942–1948.
[2] E. Ozcan and C. K. Mohan, “Particle swarm optimization: Surfing the waves,” in
Proceedings of the 1999 Congress on Evolutionary Computation-CEC99 (Cat. No.
99TH8406), 1999, vol. 3, pp. 1939–1944.
[3] R. C. Eberhart, Y. Shi, and J. Kennedy, Swarm intelligence. Elsevier, 2001.
[4] Y. Shi and R. C. Eberhart, “Parameter selection in particle swarm optimization,” in
International conference on evolutionary programming, 1998, pp. 591–600.
[5] T. Beielstein, K. E. Parsopoulos, and M. N. Vrahatis, Tuning PSO parameters through
sensitivity analysis. Citeseer, 2002.