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
SdeNpartí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)
u1yu2de 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
vLa diferencia entre la posición actual y la mejor posición que ha visto la partícula
p-xLa 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
xestá 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 velocidadvde 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 queptenga 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ículasjdel enjambre.Si es
f < b, entonces establezcab = fyd = x. Este paso garantiza quebtenga la mejor función objetivo en el enjambre y quedtenga 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 deflagse utiliza en el siguiente paso.Actualizar el vecindario. Si
flag = true:Establecer
c = max(0,c-1).Establezca
NenminNeighborhoodSize.Si es
c < 2, entonces establezcaW = 2*W.Si es
c > 5, entonces establezcaW = W/2.Asegúrese de que
Westé 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.
