“The emergent collective intelligence of
groups of simple agents.”
(Bonabeau et al, 1999)
Composed of many individuals
Individuals are homogeneous
Local interaction based on simple rules
Self-organization ( No centralized
Control)
Inspired from the nature social behavior and dynamic
movements with communications of insects, birds and
fish
In 1986, Craig Reynolds described this process in 3
simple behaviors:
Separation Alignment Cohesion
avoid crowding local move towards the average move toward the average
flockmates heading of local position of local
flockmates flockmates
Application to optimization: Particle Swarm
Optimization
Proposed by James Kennedy & Russell Eberhart (1995)
Combines self-experiences with social experiences
Uses a number of agents (particles)
that constitute a swarm moving
around in the search space looking
for the best solution
Each particle in search space adjusts
its “flying” according to its own
flying experience as well as the
flying experience of other particles
Inspired by social behavior of bird
flocking and fish schooling
So what is the best strategy to locate
the food?
Suppose a group of birds is searching
food in an area
Only one piece of food is available
Birds do not have any knowledge about
the location of the food
But they know how far the food is from
their present location
The best strategy is to follow the bird
nearest to the food
A flying bird has a position and a velocity at any time
In search of food, the bird changes his position by
adjusting the velocity
The velocity changes based on his past experience
and also the feedbacks received from his neighbor
Each solution is considered as bird, called particle
All the particles have a fitness value. The fitness values can
be calculated using objective function
All the particles preserve their individual best performance
They also know the best performance of their group
They adjust their velocity considering their best
performance and also considering the best performance of
the best particle
Collection of flying particles (swarm) - Changing
solutions
Search area - Possible solutions
Movement towards a promising area to get the global
optimum
Each particle keeps track:
• its best solution, personal best, pbest
• the best value of any particle, global best, gbest
Each particle adjusts its travelling speed dynamically
corresponding to the flying experiences of itself and
its colleagues
Each particle modifies its position according to:
• its current position
• its current velocity
• the distance between its current position and
pbest
• the distance between its current position and
gbest
My best
perf.
pi
Here I The best
am! x perf. of my
pg
neighbours
v
Random
position
Regular
position
Velocity
• It's also common to see PSO
geographical
algorithms using population
topologies, or
"neighborhoods", which can be
smaller, localized subsets of
the global best value.
• Although some variants use a
“geographical” social
neighbourhood, that is to say
compute distances and take
the nearest particles, the most
widely used neighbourhood is
a “social” one: just a list of
neighbours, regardless where
they are.
• Usually, in practice, social
neighbourhoods are defined
just once, at the very
beginning, which is consistent
with the principle “simple
rules for simple agents”.
• The use of neighborhoods
often help the algorithm to
avoid getting stuck in local
minima.
global
Advantages
• Insensitive to scaling of design variables
• Simple implementation
• Easily parallelized for concurrent processing
• Very few algorithm parameters
• Very efficient global search algorithm
Disadvantages
• Tendency to a fast and premature convergence in mid optimum
points
• Slow convergence in refined search stage (weak local search
ability)
