Particle Swarm Optimization

Question

I'm using Particle Swarm Optimization(PSO) in java. I am having little knowledge about what we do. Since, I am applying for multiple sequence alignment in bioinformatics.

We need to find position and velocity for aligning those sequences. I need detailed explanation and references about PSO and the need for calculating velocity and position in PSO. If possible I need simple example explaining PSO in java. Actually, I need to understand how it optimizes a problem.

public class Position {
 private double x;
 private double y;

 public Position(double x, double y) {
 this.x = x;
 this.y = y;
 }

 public double getX() {
 return x;
 }

 public void setX(double x) {
 this.x = x;
 }

 public double getY() {
 return y;
 }

 public void setY(double y) {
 this.y = y;
 }
}

Here is the class for representing the position of the particle with getters and setters

Like wise other classes are available here

Answer 1

Particle Swarm Optimization:

1. randomly initialize a set of particles at random positions in the search space;
2. evaluate all positions and update the global best position and the personal best positions;
3. update each velocity based on the relative position of the global best position, the current velocity of the particle, the personal best position of the particle and some random vector;
4. goto 2.

Answer 2

General Overview

Particle Swarm Optimization (PSO) is a population-based, stochastic search method. The position of each individual or particle in the population represents a possible solution to the optimization problem.

The goodness/score of a given position in the search space is measured by the objective function, which is the function being optimized.

The particles move through the search space in search of the optimal solution.

The way in which the particles move through the search is where the magic happens. Assuming that you're using the inertia weight model, this is governed by three different factors: the inertia component, the social component and the cognitive component.

The inertia component essentially introduces a form of momentum so that the particle's movement isn't too erratic from one iteration to the next. The cognitive component allows a particle's memory of where it has previously found good solutions to influence its movement direction. The social component allows the knowledge of other swarm members (i.e. where other members of the swarm have found good solutions) to influence a particle's movement.

The Update Equations

At iteration t a given particle's position is denoted by x(t). Its new position for the next iteration is calculated according to:

x(t+1) = x(t) + v(t+1)

where v(t+1) denotes the particle's velocity for the next iteration. Note that each of the values above are vectors. The length of these vectors will be equal to the problem dimensionality/the number of input variables to the objective function. (Apologies for my terrible notation; I don't have enough reputation to post pretty equations). The particle's velocity is calculated according to:

v(t+1) = w*v(t) + c1*r1*(pBest(t) - x(t)) + c2*r2*(gBest(t) - x(t))

The three different components described previously (inertia, cognitive and social) are each represented by one of the three terms in the equation above.

w is called the inertia weight and regulates the effect of the momentum component. c1 and c2 are the cognitive and social acceleration coefficients and they regulate the importance of the cognitive and social components (respectively). r1 and r2 are vectors of random numbers (sampled from a unifrom distribution between 0 and 1) that are used to scale each component of the difference vectors.

The first difference vector (pBest(t) - x(t)) allows the particle to move towards its personal best/pBest - the best position that the particle has encountered thus far. (In order to implement the algorithm, it is thus necessary for a particle to examine every position it encounters and save it if it is the best so far).

The second difference vector (gBest(t) - x(t)) allows the particle to use information from other particles in the swarm. In this expression, gBest(t) denotes the best position found by the swarm thus far. (So for implementation, after every iteration, the scores of all the particles should be examined so that the very best one can be saved for future use).

The particles move around the search space based on these equations for a number of iterations until hopefully, they all converge to the same point. The global best can then be taken as the final solution produced by the algorithm.

Hopefully this makes the inner workings of PSO more clear. With every iteration, every particle moves in a direction that is determined by its personal best and the global best. Assuming that the objective function's optimum is somewhere near these two points, it is likely that the particle will eventually encounter better and better solutions.

Other Considerations

Note that there are many different variations on the process described above. For example, it is possible to only allow knowledge sharing amongst a subset of the swarm's particles. The subset of particles with which a given particle can communicate is known as its neighbourhood. The particle will then move in the direction of the best solution found in its neighbourhood, the "local best" instead of the global best.

Also, there are a number of other possible pitfalls such as the values for w, c1, and c2. Although it is possible to do fancy things here, the general rule of thumb is to set:

w = 0.729844

c1 = c2 = 1.49618

as suggested by http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=870279&tag=1 to lead to convergent behaviour (i.e. so that all the particles will eventually converge to roughly the same point).

Usually, the particles are randomly initialized throughout the search space. Although it is possible to initialize their velocities randomly as well, this isn't necessary and may lead to divergent behaviour, so it's fine to just start the velocities as 0-vectors.

Some parties also advise making use of velocity clamping (where every velocity component is bounded above and below by some maximum and minimum value; if a particle's velocity exceeds that, it is clamped to the maximum/minimum). This is usually not necessary if w, c1 and c2 are chosen correctly and the gBest and pBest are only updated if they are within the bounds of the search space.