Monday, December 19, 2011

Particle Swarm Optimisation and Genetic Algorithm

"Particle Swarm Optimization (PSO) is a relatively recent heuristic search method whose
mechanics are inspired by the swarming or collaborative behavior of biological populations.
PSO is similar to the Genetic Algorithm (GA) in the sense that these two evolutionary
heuristics are population-based search methods. In other words, PSO and the GA move
from a set of points (population) to another set of points in a single iteration with likely
improvement using a combination of deterministic and probabilistic rules. The GA and its
many versions have been popular in academia and the industry mainly because of its
intuitiveness, ease of implementation, and the ability to effectively solve highly nonlinear,
mixed integer optimization problems that are typical of complex engineering systems. The
drawback of the GA is its expensive computational cost." queted from "A COMPARISON OF PARTICLE SWARM OPTIMIZATION AND THE GENETIC ALGORITHM"

The pseudo code of PSO procedure is as follows

For each particle
   Initialize particle

   For each particle
   Calculate fitness value
   If the fitness value is better than the best fitness value (pBest) in history
     set current value as the new pBest

Choose the particle with the best fitness value of all the particles as the gBest
For each particle
   Calculate particle velocity according equation (a)
   Update particle position according equation (b)
While maximum iterations or minimum error criteria is not attained

Most of evolutionary techniques have the following procedure:
1. Random generation of an initial population
2. Evaluate the fitness value for each subject.
3. Reproduction of the population based on fitness values, add random solution to explore the space of solution.
4. If requirements are met, then stop. Otherwise go back to 2.

Using evolutionary algorithm or PSO are nice formulation for some complex problem but visualizing the evolutionary process is fun.

You could take a look to : Yong-Hyuk Kim, Kang Hoon Lee and Yourim Yoon, Visualizing the Search Process of Particle Swarm Optimization, Proceedings of the 11th Annual conference on Genetic and evolutionary computation (GECCO 2009), 49-56, July 2009. (videos)

If you want play:
Genetic Algorithm: Evolving Objects (EO): an Evolutionary Computation Framework

No comments:

Post a Comment