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.
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.
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:
with c1 and 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:
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.
- 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)