## 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)`

:

Choose a random subset

`S`

of`N`

particles other than`i`

.Find

`fbest(S)`

, the best objective function among the neighbors, and`g(S)`

, the position of the neighbor with the best objective function.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`

Update the position

`x = x + v`

.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.Evaluate the objective function

`f = fun(x)`

.If

`f < fun(p)`

, then set`p = x`

. This step ensures`p`

has the best position the particle has seen.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.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.Update the neighborhood. If

`flag = true`

:Set

`c = max(0,c-1)`

.Set

`N`

to`minNeighborhoodSize`

.If

`c < 2`

, then set`W = 2*W`

.If

`c > 5`

, then set`W = W/2`

.Ensure that

`W`

is in the bounds of the`InertiaRange`

option.

If

`flag = false`

:Set

`c = c+1`

.Set

`N = min(N + minNeighborhoodSize,SwarmSize)`

.

### Stopping Criteria

`particleswarm`

iterates until it reaches
a stopping criterion.

Stopping Option | Stopping Test | Exit 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
`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.