Algoritmo de optimización de enjambre de partículas
Esquema del algoritmo
particleswarm
se basa en el algoritmo descrito en Kennedy y Eberhart [1], utilizando modificaciones sugeridas en Mezura-Montes y Coello Coello [2] y en Pedersen [3].
El algoritmo de enjambre de partículas comienza creando las partículas iniciales y asignándoles velocidades iniciales.
Evalúa la función objetivo en cada ubicación de partícula y determina el mejor valor de función (el más bajo) y la mejor ubicación.
Elige nuevas velocidades, basándose en la velocidad actual, las mejores ubicaciones individuales de las partículas y las mejores ubicaciones de sus vecinas.
Luego actualiza iterativamente las ubicaciones de las partículas (la nueva ubicación es la anterior más la velocidad, modificada para mantener las partículas dentro de los límites), las velocidades y los vecinos.
Las iteraciones continúan hasta que el algoritmo alcanza un criterio de detención.
Estos son los detalles de los pasos.
Inicialización
De forma predeterminada, particleswarm
crea partículas de manera aleatoria y uniforme dentro de ciertos límites. Si hay un componente ilimitado, particleswarm
crea partículas con una distribución uniforme aleatoria de –1000 a 1000. Si solo tiene un límite, particleswarm
cambia la creación para que el límite sea un punto final y un intervalo de creación de 2000 de ancho. La partícula i
tiene la posición x(i)
, que es un vector de fila con nvars
elementos. Controle la extensión del enjambre inicial usando la opción InitialSwarmSpan
.
De manera similar, particleswarm
crea velocidades de partículas iniciales v
de manera aleatoria y uniforme dentro del rango [-r,r]
, donde r
es el vector de rangos iniciales. El rango del componente k
es min(ub(k) - lb(k),InitialSwarmSpan(k))
.
particleswarm
evalúa la función objetivo en todas las partículas. Registra la posición actual p(i)
de cada partícula i
. En iteraciones posteriores, p(i)
será la ubicación de la mejor función objetivo que la partícula i
haya encontrado. Y b
es la mejor de todas las partículas: b = min(fun(p(i)))
. d
es la ubicación tal que b = fun(d)
.
particleswarm
inicializa el tamaño del vecindario N
a minNeighborhoodSize = max(2,floor(SwarmSize*MinNeighborsFraction))
.
particleswarm
inicializa la inercia W = max(InertiaRange)
, o si InertiaRange
es negativo, establece W = min(InertiaRange)
.
particleswarm
inicializa el contador de pérdida c = 0
.
Para facilitar la notación, establezca las variables y1 = SelfAdjustmentWeight
y y2 = SocialAdjustmentWeight
, donde SelfAdjustmentWeight
y SocialAdjustmentWeight
son opciones.
Pasos de iteración
El algoritmo actualiza el enjambre de la siguiente manera. Para la partícula i
, que está en la posición x(i)
:
Elija un subconjunto aleatorio
S
deN
partículas distintas dei
.Encuentre
fbest(S)
, la mejor función objetivo entre los vecinos, yg(S)
, la posición del vecino con la mejor función objetivo.Para los vectores aleatorios distribuidos uniformemente (0,1)
u1
yu2
de longitudnvars
, actualice la velocidadv = W*v + y1*u1.*(p-x) + y2*u2.*(g-x)
.Esta actualización utiliza una suma ponderada de:
La velocidad anterior
v
La diferencia entre la posición actual y la mejor posición que ha visto la partícula
p-x
La diferencia entre la posición actual y la mejor posición en el vecindario actual
g-x
Actualizar la posición
x = x + v
.Imponer los límites. Si algún componente de
x
está fuera de un límite, configúrelo igual a ese límite. Para aquellos componentes que recién se establecieron en un límite, si la velocidadv
de ese componente apunta fuera del límite, establezca ese componente de velocidad en cero.Evalúa la función objetivo
f = fun(x)
.Si es
f < fun(p)
, entonces establezcap = x
. Este paso garantiza quep
tenga la mejor posición que la partícula haya visto.Los siguientes pasos del algoritmo se aplican a los parámetros de todo el enjambre, no a las partículas individuales. Consideremos la
f = min(f(j))
más pequeña entre las partículasj
del enjambre.Si es
f < b
, entonces establezcab = f
yd = x
. Este paso garantiza queb
tenga la mejor función objetivo en el enjambre y qued
tenga la mejor ubicación.Si en el paso anterior se redujo el mejor valor de la función, entonces configure
flag = true
. De lo contrario,flag = false
. El valor deflag
se utiliza en el siguiente paso.Actualizar el vecindario. Si
flag = true
:Establecer
c = max(0,c-1)
.Establezca
N
enminNeighborhoodSize
.Si es
c < 2
, entonces establezcaW = 2*W
.Si es
c > 5
, entonces establezcaW = W/2
.Asegúrese de que
W
esté dentro de los límites de la opciónInertiaRange
.
Si
flag = false
:Establecer
c = c+1
.Establecer
N = min(N + minNeighborhoodSize,SwarmSize)
.
Criterios de detención
particleswarm
itera hasta alcanzar un criterio de detención.
Opción de detención | Prueba de detención | Indicador de salida |
---|---|---|
MaxStallIterations y FunctionTolerance | El cambio relativo en el mejor valor de la función objetivo g durante las últimas MaxStallIterations iteraciones es menor que FunctionTolerance . | 1 |
MaxIterations | El número de iteraciones alcanza MaxIterations . | 0 |
OutputFcn o PlotFcn | OutputFcn o PlotFcn pueden detener las iteraciones. | -1 |
ObjectiveLimit | El mejor valor de la función objetivo g es menor que ObjectiveLimit . | -3 |
MaxStallTime | El mejor valor de la función objetivo g no cambió en los últimos MaxStallTime segundos. | -4 |
MaxTime | El tiempo de ejecución de la función excede MaxTime segundos. | -5 |
Si particleswarm
se detiene con el indicador de salida 1
, opcionalmente llama a una función híbrida después de salir.
Referencias
[1] Kennedy, J., and R. Eberhart. "Particle Swarm Optimization." Proceedings of the IEEE International Conference on Neural Networks. Perth, Australia, 1995, pp. 1942–1945.
[2] Mezura-Montes, E., and C. A. Coello Coello. "Constraint-handling in nature-inspired numerical optimization: Past, present and future." Swarm and Evolutionary Computation. 2011, pp. 173–194.
[3] Pedersen, M. E. "Good Parameters for Particle Swarm Optimization." Luxembourg: Hvass Laboratories, 2010.