Particle Swarm optimization

A swarm of bees flies across a field to find the points with the highest density of flowers. Initially, when no knowledge on the field has been gained yet, the bees move randomly. Each bee remembers the locations where it found the most flowers and knows from the others the other locations with high concentration of flowers.

After the first random exploration, each bee is simultaneously pulled to returning to the location where it had found the most flowers and to the location reported by the fellow bees. It alters its trajectory to fly somewhere between the two points depending on whether self-cognitive or social factors influence its decision.

From time to time, one bee may fly over a place with more flowers than had been encountered by any bee in the swarm, drawing the whole swarm toward that location in additional to their own personal discovery.

Eventually, the bees are led to the place in the field with the most concentration of flowers and all the bees swarm around this point.

This is particle swarm optimization. A general pseudo-code is the following:

 

Initialize population
Initialize pbest (the vector of the best locations of each bee) and gbest (the best location of the whole swarm)
Initialize the particles' velocities
While (not exit criterion) do
   Fly the particles through the solution space according to their velocities
    Calculate the fitness for each particle and update pbest and gbest
     Update the particles' velocities
 End

The velocity of the particle is changed according to the relative locations of pbest and gbest, that is

 vn = w vn + c1 rand() (pbest,n - xn) + c2 rand() (gbest,n - xn)

 where the subscript n denotes the components along the n-th dimension, and x is the particle’s location.

The new velocity is the old velocity scaled by w and increased in the direction of gbest and pbest. c1 (cognitive rate) and c2 (social rate) are scaling factors that determine the relative “pull” of pbest and gbest; c1 determines how much the particle is influenced by its individual experience and c2 determines how much the particle is influenced by the social behavior.

Increasing c1 encourages exploration of the solution space as each particle moves toward its own pbest; increasing c2 encourages exploitation of the supposed global maximum region. rand() returns a number between 0.0 and 1.0.

It is generally the case that the two appearances of rand() function represent two separate calls to the function.

If you want to know more, try it by yourself! We provide you a free Particle Swarm Optimization software.

Leave a Reply

Your email address will not be published. Required fields are marked *