Particle swarm

Particle Swarm Optimization

Particle Swarm Optimization (OEP, or PSO) was proposed by Kennedy and Eberhart. This method is inspired by the social behavior of animals evolving in swarms.

Initially, they sought to simulate the ability of birds to fly synchronously and their ability to change direction abruptly while remaining in optimal formation.

Particles are individuals and they move through the research hyperspace based on limited information:

  1. Each particle is endowed with a memory which allows it to memorize the best point through which it has already passed and it tends to return to this point.
  2. Each particle is informed of the best known point within its neighborhood and it will tend to go towards this point.

Each individual therefore uses not only his own memory, but also local information on his closest neighbors to decide on his own movement. Simple rules, such as: going at the same speed as the others, moving in the same direction or staying close to one's neighbors are examples of behaviors that are enough to keep the swarm together.

The movement of a particle is influenced by three types of behavior:

  1. A physical component: the particle tends to follow its own path;
  2. A cognitive component: the particle tends to return to the best site through which it has already passed;
  3. A social component: the particle tends to move towards the best site already reached by its neighbors.

Particle Swarm Optimization Algorithm

In Rnot, the particle i of the swarm is modeled by its position vector xi = (xi1,…, Xin) and by its speed vector vi = (vi1,…, Vin).

This particle keeps in memory the best position through which it has already passed, noted pi = (pi1,…, Pin). The best position reached by all the particles of the swarm is noted pg = (pg1,…, Pgn).

At time t + 1, the speed vector is calculated from formula A:

Particle Swarm Optimization

with c1 and c2 two constants, called acceleration coefficients; r1 NS2 are two random numbers drawn uniformly in [0,1].

The three added terms of the formula can be explained as follows:

  • vij(t) corresponds to the physical component of the displacement;
  • the following term corresponds to the cognitive component of the displacement with c1 which weights the tendencies of the particle to want to follow its instinct of conservation and to go towards its best known position;
  • the last term corresponds to the social component of displacement. vs2 controls the social aptitude of the particle by getting closer to the best position of its informants.

The position of particle i is then defined by formula B:

Particle Swarm Optimization

Pseudo Code of Optimization by Particle Swarm

The stopping criterion may be different depending on the problem posed and the user's requirements. If the global optimum is known a priori, an acceptable error can be defined as a stopping criterion. Otherwise, we can set a maximum number of iterations or a maximum number of evaluations of the objective function.
Particle Swarm Optimization

Variants

  • Impose a positive and negative max speed
  • Apply a coefficient of inertia to the first term of the formula A -> Shi and Eberhart 1998
  • Apply a constriction factor in formula A instead of the constants -> Clerc and Kennedy 2002
  • Apply a neighborhood topology to know with which particle a particle i will communicate -> Kennedy 1999