Catalogue of Artificial Intelligence Techniques
Particle Swarm Optimization
Keywords: algorithm, optimization, particle, problem, search, swarm
Author(s): Andrei Lyashko
Particle Swarm Optimization (PSO) is a relatively new family of algorithms that are used to find optimal solutions to numerical and qualitative problems whose solutions can be represented as a point in an n-dimensional search space. It is inspired by the swarming behaviour of birds and insects. It is easily implemented and has proven both very effective and quick when applied to a diverse set of optimization problems.
PSO shares many similarities with evolutionary computation techniques such as Genetic Algorithms, however, unlike GA, PSO has no evolution operators such as crossover and mutation. The PSO concept based on a population of particles who are randomly set into motion through the search space. Each particle keeps track of its coordinates which are associated with the best solution or 'fitness' it has achieved so far. At each iteration, they observe the 'fitness' of themselves and their neighbours and move towards more successful neighbours, whose current position represents a better solution to the problem than theirs. Acceleration is weighted by a random term, with separate random numbers being generated for acceleration toward its own best position and the overall best position. This will provide some form of convergence to the search, while providing a degree of randomness to promote a wide coverage of the search space.
Here is a list of the parameters that typical PSO algorithm takes:
- • number of particles
• inertia (w) (a component of motion in the direction it is moving)
• own-best weighting (c1)
• global-best weighting (c2)
• maximum allowable velocity (v)
where p of i,n and p of g,n are the own-best position of i-th particle and global-best position found by other particle respectively.
Below is a simple visualization of PSO algorithm for finding the maximum height in 3-dimensional landscape (source). Green and yellow lines indicate the current and the previous move made by each particle respectively:
Overall, PSO demonstrates better results comparing with other methods in a faster, cheaper way and has been successfully applied in many research and application areas. It also avoids some of the problems GA met. The development of PSO is still ongoing and there are still many unknown areas in PSO research.
- C. R. Mouser, S. A. Dunn, Comparing genetic algorithms and particle swarm optimisation for an inverse problem exercise, Anziam journal (2005), 13.
- J. Kennedy, R. C. Eberhart, Particle swarm optimization, Proc. of the IEEE Int. Conf. on Neural Networks, vol. IV, Piscataway, 1995, pp. 1942-1948.
- D. N. Wilke, Analysis of the particle swarm optimization algorithm, Master's Dissertation, University of Pretoria, 2005, pp.74.