Particle swarm optimization

Optimization by Particle Swarm (PSO) was proposed by Kennedy and Eberhart. This method is inspired by the social behavior of swarming animals.

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

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

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

Each individual uses not only his own memory but also local information about his closest neighbors to decide on his own move. Simple rules, such as: going at the same speed as others, moving in the same direction or staying close to one’s neighbors are examples of behaviors that are sufficient to maintain the cohesion of the swarm.

The displacement of a particle is influenced by the 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 point by which it has already passed;
  3. A social component: the particle tends to move towards the best point already reached by its neighbors.

Algorithm

In Rn, the particle i of the swarm is modeled by its vector position xi = (xi1, …, xin) and by its velocity vector vi = (vi1, …, vin).

This particle keeps in memory the best position by 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 velocity vector is calculated from formula A:

essaim1

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

The three added terms of the formula are explained as follows:

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

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

essaim2

Pseudo code

The stopping criterion may be different depending on the problem and the requirements of the user. If the global optimum is known a priori, we can define an acceptable error as a stopping criterion. Otherwise, one can set maximum number of iterations or a maximum number of evaluations of the objective function.
essaim3

Variants

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

 

Publicités