Particle Swarm Optimization Algorithm

Algorithm Outline

particleswarm is based on the algorithm described in Kennedy and Eberhart [1], using modifications suggested in Mezura-Montes and Coello Coello [2] and in Pedersen [3].

The particle swarm algorithm begins by creating the initial particles, and assigning them initial velocities.

It evaluates the objective function at each particle location, and determines the best (lowest) function value and the best location.

It chooses new velocities, based on the current velocity, the particles’ individual best locations, and the best locations of their neighbors.

It then iteratively updates the particle locations (the new location is the old one plus the velocity, modified to keep particles within bounds), velocities, and neighbors.

Iterations proceed until the algorithm reaches a stopping criterion.

Here are the details of the steps.

Initialization

By default, particleswarm creates particles at random uniformly within bounds. If there is an unbounded component, particleswarm creates particles with a random uniform distribution from –1000 to 1000. If you have only one bound, particleswarm shifts the creation to have the bound as an endpoint, and a creation interval 2000 wide. Particle i has position x(i), which is a row vector with nvars elements. Control the span of the initial swarm using the InitialSwarmSpan option.

Similarly, particleswarm creates initial particle velocities v at random uniformly within the range [-r,r], where r is the vector of initial ranges. The range of component k is min(ub(k) - lb(k),InitialSwarmSpan(k)).

particleswarm evaluates the objective function at all particles. It records the current position p(i) of each particle i. In subsequent iterations, p(i) will be the location of the best objective function that particle i has found. And b is the best over all particles: b = min(fun(p(i))). d is the location such that b = fun(d).

particleswarm initializes the neighborhood size N to minNeighborhoodSize = max(2,floor(SwarmSize*MinNeighborsFraction)).

particleswarm initializes the inertia W = max(InertiaRange), or if InertiaRange is negative, it sets W = min(InertiaRange).

particleswarm initializes the stall counter c = 0.

For convenience of notation, set the variable y1 = SelfAdjustmentWeight, and y2 = SocialAdjustmentWeight, where SelfAdjustmentWeight and SocialAdjustmentWeight are options.

Iteration Steps

The algorithm updates the swarm as follows. For particle i, which is at position x(i):

  1. Choose a random subset S of N particles other than i.

  2. Find fbest(S), the best objective function among the neighbors, and g(S), the position of the neighbor with the best objective function.

  3. For u1 and u2 uniformly (0,1) distributed random vectors of length nvars, update the velocity

    v = W*v + y1*u1.*(p-x) + y2*u2.*(g-x).

    This update uses a weighted sum of:

    • The previous velocity v

    • The difference between the current position and the best position the particle has seen p-x

    • The difference between the current position and the best position in the current neighborhood g-x

  4. Update the position x = x + v.

  5. Enforce the bounds. If any component of x is outside a bound, set it equal to that bound. For those components that were just set to a bound, if the velocity v of that component points outside the bound, set that velocity component to zero.

  6. Evaluate the objective function f = fun(x).

  7. If f < fun(p), then set p = x. This step ensures p has the best position the particle has seen.

  8. The next steps of the algorithm apply to parameters of the entire swarm, not the individual particles. Consider the smallest f = min(f(j)) among the particles j in the swarm.

    If f < b, then set b = f and d = x. This step ensures b has the best objective function in the swarm, and d has the best location.

  9. If, in the previous step, the best function value was lowered, then set flag = true. Otherwise, flag = false. The value of flag is used in the next step.

  10. Update the neighborhood. If flag = true:

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

    2. Set N to minNeighborhoodSize.

    3. If c < 2, then set W = 2*W.

    4. If c > 5, then set W = W/2.

    5. Ensure that W is in the bounds of the InertiaRange option.

    If flag = false:

    1. Set c = c+1.

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

Stopping Criteria

particleswarm iterates until it reaches a stopping criterion.

Stopping OptionStopping TestExit Flag
MaxStallIterations and FunctionToleranceRelative change in the best objective function value g over the last MaxStallIterations iterations is less than FunctionTolerance.1
MaxIterationsNumber of iterations reaches MaxIterations.0
OutputFcn or PlotFcnOutputFcn or PlotFcn can halt the iterations.-1
ObjectiveLimitBest objective function value g is less than ObjectiveLimit.-3
MaxStallTimeBest objective function value g did not change in the last MaxStallTime seconds.-4
MaxTimeFunction run time exceeds MaxTime seconds.-5

If particleswarm stops with exit flag 1, it optionally calls a hybrid function after it exits.

References

[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.

See Also

Topics