Optimización de Enjambres de Partículas (PSO) – Método Heurístico

El método de optimización de enjambres de partículas (PSO por sus siglas en inglés Particle Swarm Optimization) es un método de optimización heurístico que fue descrito cerca de 1995 por James Kennedy y Russell C. Eberhart, y este método evoca del comportamiento de los enjambres de insectos en la naturaleza.

En concreto, el enjambre que se pone de ejemplo para explicar este método es uno de abejas, ya que las abejas a la hora de buscar polen buscan la región del espacio en la que existe más densidad de flores, ya que es ahí donde existe más polen. Este método ha sido portado al campo de la computación en forma de algoritmo y se emplea en la actualidad en la optimización de distintos tipos de sistemas.



EL MÉTODO

El espacio de soluciones está formulado como un espacio de dimensión dimension_espacio. En él una población (enjambre) de partículas (insectos) de tamaño n, que actúan de agentes de búsqueda, se mueve en el espacio de soluciones guiadas por los miembros del enjambre que han obtenido las mejores posiciones – mejores valores de la función objetivo f -. El tamaño del enjambre suele oscilar entre 20 y 40 partículas.

Para problemas muy difíciles se eleva a un rango de 100-200.

Cada partícula i se comunica con un entorno o grupo social N(i), Este entorno puede ser parte o todo el enjambre, y puede variar dinámicamente. La estructura de los entornos puede tener una topología anular en la que cada partícula se relaciona con dos, una topología en forma de estrella en la que cada partícula se relaciona con todas. Otra alternativa, Kennedy y Clerc 2006, es fijar el número de partículas k que informan a otras que son elegidas al azar. Estas partículas se renuevan cada vez que mejora la posición grupal.

Cada partícula i guarda información de la mejor posición obtenida Pbest y del mejor valor obtenido por cualquier partícula del entorno Gbest. La información de estas mejores posiciones influye en el comportamiento de la partícula.

Así pues, cada partícula i del enjambre lleva asociados los siguientes vectores:

P[i] posición actual,

V[i] velocidad actual,

Pbest[i] posición de la mejor solución encontrada,

Gbest[i] mejor posición obtenida por cualquier partícula del entorno.

En el gráfico podemos ver un enjambre dentro del cual hay tres grupos o entornos sociales de partículas. Cada grupo tiene su "leader", ☼. El óptimo se encuentra en J.

  

 

Veamos los diferentes pasos de la versión estándar de este algoritmo.

Paso I: Inmersión aleatoria de los insectos en el espacio de búsqueda:

A las partículas inicialmente se les asigna una posición aleatoria, P0[i] ( si el número de variables de la función es dimension_espacio, cada componente será denotada por P0[i][k], k = 1..dimension_espacio2), dentro de su región factible, y así mismo se les asigna una velocidad aleatoria, V0[i], con valores en la región factible, para evitar, en lo posible, que la partícula se "escape" a posiciones no factibles.

Se va a almacenar la mejor solución por la que pasa cada partícula i, que inicialmente se supone f_best[i] = +∞. Análogamente se hace lo mismo con la mejor solución del grupo social al que pertenece i, f_best_grupo[i].

Paso II: Actualizando la velocidad y posición de las partículas:

Tras cada iteración hay que recalcular la velocidad, y actualizar la posición de los insectos a partir de las nuevas velocidades. Así para la partícula i su velocidad es:

V[i]= c_inercia.V[i] + c_confianza1 .rnd1.(Pbest[i]- P[i])+ c_confianza2 .rnd2. (Gbest[i]- P[i]) (*)

Dónde:

c_inercia es un parámetro que representa el efecto de la inercia, controlando el efecto de la velocidad y evitando que crezca indefinidamente;

c_confianza1 y c_confianza2 son parámetros que marcan la confianza de la partícula en sí misma y en su grupo.

Los valores rnd1 y rnd2 son números aleatorios entre 0 y 1.

Es habitual tomar c_inercia=1 y c_confianza1 = c_confianza2 en el rango [0,4]. También lo es tomar estos tres parámetros de forma que su suma sea 1. En la versión estándar de Kennedy y Clerc los valores son: c_inercia = 1/(2+ln2) y c_confianza1 = c_confianza2 = 0.5 + ln2;

La posición de la partícula será: P[i]=P[i]+V[i] (**)

Se han ido contando las infactibilidades, cuyo cómputo se ha tenido en cuenta a la hora de dar valores a los parámetros, procurando que el número de infactibilidades no sea muy elevado.

Paso III: Actualización de las mejores soluciones de cada partícula:

En una matriz Pbest[i] vamos almacenando la mejor posición de cada insecto y en otra matriz, f_best[i], el mejor valor de la función objetivo. Tras cada iteración si la solución obtenida por la partícula i es mejor que la mejor conocida hasta ese momento son actualizadas Pbest[i] y f_best[i]. Así mismo en la matriz Gbest[i] se va almacenando la mejor posición del grupo social o entorno de la partícula i. Tras cada iteración si la solución obtenida por alguna de las partículas de N(i ) es mejor que la mejor conocida hasta ese momento es actualizada Gbest[j],A j E N(i ).

 

De tal manera, el pseudocódigo del algoritmo sería el siguiente:

Inicializar aleatoriamente todos los insectos

Mientras t < max_iter hacer

Para cada insecto i hacer

Calcular velocidad teniendo en cuenta la inercia, su mejor posición y la mejor posición de su entorno social (*)(**);

Calcular posición tras variación velocidad;

Si no factible i HacerFactible;

Obtener funcion_objetivo;

    Si Valor_funcion < f_best[i] entonces actualizar

P_best[i] y f_best[i]

Si Valor_funcion < f_best_grupo[i] entonces actualizar

G_best[j] y f_best_grupo[j] A J E N(i)

t:= t+1