Documentation

This is machine translation

Translated by
Mouseover text to see original. Click the button below to return to the English version of the page.

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 `FunctionTolerance`Relative change in the best objective function value `g` over the last `MaxStallIterations` iterations is less than `FunctionTolerance`.`1`
`MaxIterations`Number of iterations reaches `MaxIterations`.`0`
`OutputFcn` or `PlotFcn``OutputFcn` or `PlotFcn` can halt the iterations.`-1`
`ObjectiveLimit`Best objective function value `g` is less than or equal to `ObjectiveLimit`.`-3`
`MaxStallTime`Best objective function value `g` did not change in the last `MaxStallTime` seconds.`-4`
`MaxTime`Function 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.

Watch now