Particle swarm optimization algorithm

Question

What is the difference between the gbest and lbest in particle swarm optimization, and Why is named Lbest PSO ?

Answer 1

Background

Particle swarm optimization (PSO) is a stochastic, population-based search method. There are a number of individuals or particles which move through the search space in search of the best solution. Every particle position represents a potential solution and the goodness/fitness of that solution is measured by an objective function (the function being optimised).

Assuming a basic PSO model (with inertia weight), the movement of the particles through the search space is governed by three factors: the inertia weight component, the cognitive component and the social component.

The inertia weight component allows a particle to maintain some momentum between iterations. The cognitive component allows the particle's movement to be influenced by its memory of good positions that it has found in earlier iterations. The social component will cause the good positions found by other members of the swarm to influence the given particle's movement.

Knowledge Sharing - The Actual Answer

The question is now how knowledge about good positions should be shared within the swarm. The set of particles with which a given particle can communicate is called its neighbourhood.

One strategy is to give the particles full knowledge; in this strategy, all the particles are aware of where the very best location is that the swarm has ever found. This is referred to as the global best or gBest approach, because the particles will all be attracted to the global best position. The neighbourhood of a particle will thus be the entire swarm.

Another strategy is to only allow the particle to communicate with a subset of the other particles. Particle P will thus be attracted to the best position found by the particles in its neighbourhood, but this is not necessarily the best position found by the entire swarm thus far. Consequently, this approach is called the local best or lBest approach.

Neighbourhood Topologies

The way in the neighbourhood is defined is known as the neighbourhood topology. If the knowledge exchange is shown as a graph (where a node represents a particle and an edge represents knowledge exchange), the gBest approach will form a fully connected graph that looks like a star. GBest thus uses a star topology.

There are a number of different topologies that allow the lBest approach. One topology is ring, in which every particle only communicates with 2 other particles. There are also others such as Von Neumann, Pyramid, etc.

For more information, refer to the work of Kennedy and Mendes: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.114.7988&rep=rep1&type=pdf