Contenido
PalancaOptimización de Enjambre de partículas
Kennedy y Eberhart propusieron la optimización del enjambre de partículas (OEP, o PSO). Este método está inspirado en el comportamiento social de los animales que evolucionan en enjambres.
Inicialmente, buscaron simular la capacidad de las aves para volar sincrónicamente y su capacidad para cambiar de dirección abruptamente mientras permanecían en una formación óptima.
Las partículas son individuos y se mueven a través del hiperespacio de investigación basándose en información limitada:
- Cada partícula está dotada de una memoria que le permite memorizar el mejor punto por el que ya pasó y tiende a volver a ese punto.
- Cada partícula está informada del punto más conocido dentro de su vecindad y tenderá a ir hacia este punto.
Por lo tanto, cada individuo utiliza no solo su propia memoria, sino también la información local sobre sus vecinos más cercanos para decidir su propio movimiento. Reglas simples, como: ir a la misma velocidad que los demás, moverse en la misma dirección o permanecer cerca de los vecinos son ejemplos de comportamientos que son suficientes para mantener unido al enjambre.
El movimiento de una partícula está influenciado por tres tipos de comportamiento:
- Un componente físico: la partícula tiende a seguir su propio camino;
- Un componente cognitivo: la partícula tiende a regresar al mejor sitio por el que ya pasó;
- Un componente social: la partícula tiende a moverse hacia el mejor sitio ya alcanzado por sus vecinos.
Algoritmo de optimización de enjambre de partículas
En Rno, la partícula i del enjambre está modelada por su vector de posición xI = (xi1,…, Xen) y por su vector de velocidad vI = (vi1,…, Ven).
Esta partícula guarda en la memoria la mejor posición por la que ya ha pasado, señaló pI = (pi1,…, PAGen). La mejor posición alcanzada por todas las partículas del enjambre se anota pgramo = (pg1,…, PAGgn).
En el tiempo t + 1, el vector de velocidad se calcula a partir de la fórmula A:
con c1 y C2 dos constantes, llamadas coeficientes de aceleración; r1 NS2 son dos números aleatorios extraídos uniformemente en [0,1].
Los tres términos agregados de la fórmula se pueden explicar de la siguiente manera:
- vij(t) corresponde al componente físico del desplazamiento;
- el siguiente término corresponde al componente cognitivo del desplazamiento con c1 que pondera las tendencias de la partícula a querer seguir su instinto de conservación e ir hacia su posición más conocida;
- el último término corresponde al componente social del desplazamiento. vs2 controla la aptitud social de la partícula acercándose a la mejor posición de sus informantes.
La posición de la partícula i se define entonces mediante la fórmula B:
Pseudocódigo de optimización por enjambre de partículas
El criterio de parada puede ser diferente según el problema planteado y las necesidades del usuario. Si el óptimo global se conoce a priori, un error aceptable se puede definir como criterio de parada. De lo contrario, podemos establecer un número máximo de iteraciones o un número máximo de evaluaciones de la función objetivo.
Variantes
- Imponer una velocidad máxima positiva y negativa.
- Aplicar un coeficiente de inercia al primer término de la fórmula A -> Shi y Eberhart 1998
- Aplicar un factor de constricción en la fórmula A en lugar de las constantes -> Clerc y Kennedy 2002
- Aplicar una topología de vecindad para saber con qué partícula me comunicaré una partícula -> Kennedy 1999