Contenido principal

Esta página se ha traducido mediante traducción automática. Haga clic aquí para ver la última versión en inglés.

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):

  1. Elija un subconjunto aleatorio S de N partículas distintas de i.

  2. Encuentre fbest(S), la mejor función objetivo entre los vecinos, y g(S), la posición del vecino con la mejor función objetivo.

  3. Para los vectores aleatorios distribuidos uniformemente (0,1) u1 y u2 de longitud nvars, actualice la velocidad

    v = 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

  4. Actualizar la posición x = x + v .

  5. 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 velocidad v de ese componente apunta fuera del límite, establezca ese componente de velocidad en cero.

  6. Evalúa la función objetivo f = fun(x) .

  7. Si es f < fun(p), entonces establezca p = x. Este paso garantiza que p tenga la mejor posición que la partícula haya visto.

  8. 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ículas j del enjambre.

    Si es f < b, entonces establezca b = f y d = x. Este paso garantiza que b tenga la mejor función objetivo en el enjambre y que d tenga la mejor ubicación.

  9. 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 de flag se utiliza en el siguiente paso.

  10. Actualizar el vecindario. Si flag = true:

    1. Establecer c = max(0,c-1) .

    2. Establezca N en minNeighborhoodSize.

    3. Si es c < 2, entonces establezca W = 2*W.

    4. Si es c > 5, entonces establezca W = W/2.

    5. Asegúrese de que W esté dentro de los límites de la opción InertiaRange.

    Si flag = false:

    1. Establecer c = c+1 .

    2. Establecer N = min(N + minNeighborhoodSize,SwarmSize) .

Criterios de detención

particleswarm itera hasta alcanzar un criterio de detención.

Opción de detenciónPrueba de detenciónIndicador de salida
MaxStallIterations y FunctionToleranceEl cambio relativo en el mejor valor de la función objetivo g durante las últimas MaxStallIterations iteraciones es menor que FunctionTolerance.1
MaxIterationsEl número de iteraciones alcanza MaxIterations.0
OutputFcn o PlotFcnOutputFcn o PlotFcn pueden detener las iteraciones.-1
ObjectiveLimitEl mejor valor de la función objetivo g es menor que ObjectiveLimit.-3
MaxStallTimeEl mejor valor de la función objetivo g no cambió en los últimos MaxStallTime segundos.-4
MaxTimeEl 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.

Consulte también

Temas