↵

## Introduction

The particle swarm optimizer (PSO) is a problem solving algorithm that was first proposed in 1995 by Jim Kennedy and Russ Eberhart. It was used initially for modelling the movement of birds in a flock. The basic idea is to move (fly) a group (swarm) of problem solving entities (particles) throughout the range of possible solutions to a problem. This range is known as the problem space. The movement of particles within the problem space has a random component but is mainly guided by three factors.

- The present position of the particle.
- The best position found by the particle (known as personal best or pBest).
- The best position found in the swarm.(known a global best or gBest)

## Particle Swarm Optimization Step By Step.

Say, for example, that the problem was to find the minimal values of X and Y for the equation (X*X)-(Y*Y) where X and Y are integers in the range 0 to 10. The alogrithm will follow the following execution path

- Initialise the particles with random values of X and Y in the range 0-10
- Determine the fitness of the particle by evaluating the equation with the present values of X and Y.
- Update each particle's position based on its personal best and the global best fitness values.
- Either, terminate on a preset fitness value or the number of iterations of steps 2 and 3, or else repeat steps 2 and 3.

## Rosenbrock Function

The Rosenbrock function is often used as a test for the optimizer. It's difficult to find the minimal value as it's multidimensional with lots of local minimal values. It's useful to bear in mind, when selecting suitable functions to test, that the otimizer has a built-in bias. It's easier to find solutions that lie in the centre of the problem space or on the edges of it.

## The Key Optimization Formula In Easy Stages

### Stage 1

Update the velocity of the particle for each dimension, in the example, it would be for both X and Y. The velocity is the amount by which the position changes

**vid=vid*W+C1*rand(pid-xid)+C2*Rand(pgd-xid)**

where

**vid** is the current velocity,

**W, C1,C2** are constants. The approximate values for the constants are C1=C2=1.4 W=0.7

**Rand** and **rand** are two randomly generated doubles >=0 and <1

**xid ** is the current position, **pid** is the personal best position and **pgd** is the global best position.

### Stage 2

Update the current position by adding the new velocity to it.

**xid=xid+vid**

That's it. There isn't any mutation or generation of new particles. It is simply a semi-random search process, directed through information exchange between members of the swarm.

## Recent refinements.

Modern variations of the algorithm use a local best position rather rather than a global best. This tends to ensure better exploration of the problem space and prevents too rapid a convergence to some regional minimal value. Each particle has a fixed overlapping collection of informers from which its local best position is derived. The particles are linked to each other in a ring structure. For example, in an 6 particle swarm, A to F, with the number of informers set at two, particle A would be informed by particles F and B. Particle B will be informed by particles A and C and particle F would be informed by particles E and A. Another variation is to have discrete groups of informers and reorganise them after a certain number of iterations have passed without the global best value changing. This variation enables all the groups to be optimized concurrently on different threads and redistributed after a set number of epochs have passed without an improvement.

## Keeping the Particles Within The Problem Space.

It is possible for the particles to fly outside the problem space, so, the first example, X could acquire a value greater than 10. There are several ways of dealing with this situation. The most simple is just to let them fly but do not allow the escaped particles update the pbest or lbest positions. The particles will be pulled back into the correct range under the influence of pbest and lbest.

## The Code

The Particle class has the following constructor.

public Particle(int dimensions,Func<double[], double> errorFunc,ParticleManager particleManager)
{
this.Dimensions = dimensions;
this.particleManager = particleManager;
this.errorFunc = errorFunc;
this.Initialize();
}

The problem to be solved is passed in as a `Func<double[], double>`

. It returns an error value which the algorithm will try to miminise.The `double[]`

contains all the parameters (dimensions) of the function. The `ParticleManager`

class handles the maths.

public double[] UpdateVelocity(IParticle particle, double[] bestLocalPosition)
{
var newVelocity = new double[particle.Velocity.Length];
for (int j = 0; j < particle.Velocity.Length; ++j)
{
newVelocity[j] = (this.psoAttributes.W * particle.Velocity[j])
+ (this.psoAttributes.C1 * this.randomFactory.NextRandomDouble()
* (particle.BestPosition[j] - particle.Position[j]))
+ (this.psoAttributes.C2 * this.randomFactory.NextRandomDouble()
* (bestLocalPosition[j] - particle.Position[j]));
}
newVelocity.CopyTo(particle.Velocity, 0);
return particle.Velocity;
}
public double[] UpdatePosition(IParticle particle)
{
var newPosition = new double[particle.Position.Length];
for (int j = 0; j < particle.Position.Length; ++j)
{
double newPositionJ = particle.Position[j] + particle.Velocity[j];
newPosition[j] = newPositionJ;
}
newPosition.CopyTo(particle.Position, 0);
return particle.Position;
}

The Optimise functions are fairly straight forward. The number of consecutive static epochs is used to provide an early exit if no improvement is made. The attributes for the optimiser are set in the app.config file.

public double[] Optimize()
{
int epoch = 0;
int staticEpochs = 0;
while (epoch < this.psoAttributes.MaxEpochs && staticEpochs < psoAttributes.MaxStaticEpochs)
{
bool isErrorImproved = false;
foreach (IParticle particle in this.Swarm)
{
double error = particle.OptimizePosition();
if (error < this.BestGlobalError)
{
particle.Position.CopyTo(this.BestGlobalPosition, 0);
this.BestGlobalError = error;
isErrorImproved = true;
staticEpochs = 0;
}
}
if (!isErrorImproved)
{
staticEpochs++;
}
epoch++;
}
return this.BestGlobalPosition;
}
public double UpdateErrorValues()
{
if(this.particleManager.CheckIsInRange(this.Position))
{
double newError = this.particleManager.CalculateError(this.Position,this.errorFunc);
if (newError < this.BestError )
{
this.Position.CopyTo(this.BestPosition, 0);
this.BestError = newError;
}
this.Error = newError;
}
return this.BestError;
}

## Example Application

The example Console application attempts to optimize four of the commomly used test functions.

- Beale's Function. The solution is at xd[0]=3 xd[1]=0.5
- Rosenbrock Function. The solution is at xd[0]=1 xd[1]=1
- Sphere Function. The solution is at xd[0]=0 xd[1]=0 xd[2]=0 xd[3]=0
- Griewank Function.The solution is at xd[0]=0 xd[1]=0 xd[2]=0 xd[3]=0

## Conclusion

Particle Swarm Optimizers are a useful addition to the growing collection of algorithms that employ a form of artificial intelligence to solve problems. They are particularly good at finding solutions to problems that use multiple, continuously variable values. But they can be adapted to solve problems with discrete values like The Travelling Salesman Problem, as I hope to be able to demonstrate in a future article.

## References

Particle Swarm Optimization Lecture by Russ Eberhart

Particle Swarm Optimization Wikipedia

Particle Swarm Optimization Using C# by James McCaffrey

Beale's Function http://www.sfu.ca/~ssurjano/beale.html

Griewank Function http://mathworld.wolfram.com/GriewankFunction.html

Rosenbrock Function https://en.wikipedia.org/wiki/Rosenbrock_function

Rosenbrock Function Illustration https://en.wikipedia.org/wiki/Rosenbrock_function

Sphere Function http://www.sfu.ca/~ssurjano/spheref.html