Swarm, Particle! Swarm! Part 1
The particle swarm optimization algorithm can be an effective algorithm for solving difficult problems. Why use particle swarms to solve problems? How does it work?
What is particle swarm optimization?
Particle swarm optimization (PSO) is an algorithm whose goal is to find the optimal solution for a problem.
Give me an example.
Let’s say the problem you’re attempting to solve is x*x + y*y = 0. Potential solutions to this problem consist of (x,y) pairs. Any (x,y) pair could be a potential solution:
- (1,3)
- (4,2)
- (5,9)
In PSO, a potential solution is represented by a particle. Therefore, a particle with the values (1,3) represents the potential solution (1,3). If x and y are coordinates on an x-y coordinate system, the particle with the values (1,3) would be positioned at x=1 and y=3. If the particle moves to x=4 and y=2, it now represents a different potential solution, namely (4,2).
Each time the particle moves to a different position, it uses its (x,y) values and plugs them into the problem (x*x+y*y=0) to see if it gets 0. If not, it moves to another location which represents yet another potential solution. If more than one of these particles is moving around looking for potential solutions, we get a particle swarm. Particle swarms moving around in this manner are searching for the optimal solution to the problem.
This seems like random guesswork. How does the particle swarm find the right solution?
The short answer is that each particle’s movement is not completely random. Particles are influenced by their personal experience and the experience of the entire swarm. Due to these influences, the swarm tends to converge on the optimal solution.
What is a particle’s personal experience?
Every particle remembers the best solution it has come across in its own personal experience. As the particle moves from position to position, it plugs them into the problem and gets a result. The closer this result is to 0, the closer it is to the optimal or “right” solution. When the particle encounters a solution that is more optimal than the solution currently in its memory, the new solution replaces the older, less optimal solution in the particle’s memory.
Cool… so what’s the experience of the entire swarm?
When a particle moves to a different position, not only is the new solution compared with the particle’s memory, the solution is compared with the swarm’s memory. If the new solution is more optimal than the current solution in the swarm’s memory, the new solution replaces the less optimal solution in the swarm’s memory. In addition to each particle remembering the single most optimal solution it’s found so far, the swarm also remembers the single most optimal solution found so far.
How do these experiences influence the particle’s movement?
The actual mechanics of how the particle is influenced will be explained in another post. Despite the particle flying around randomly, it has a tendency to be pulled in the direction of its best personal solution as well as the swarm’s best solution.
But how does it find the best solution?
There is no guarantee that it finds the best solution.
The particles are randomly searching all solutions with a tendency to be pulled in the direction of the best solution it’s found and the best solution found by the swarm. This tendency makes the swarm focus its search in relatively promising regions in hopes of finding a better solution.
It’s possible for a swarm to converge on a non-optimal solution too quickly before getting a chance to search the rest of the solutions. Balancing the weight of influence from both personal and swarm experience is one of the most important factors for the swarm converging on the optimal solution.
Where can I find more information about PSO?
If you’re looking for the paper that started it all, here’s the original paper from Kennedy and Eberhart: Particle Swarm Optimization.
A really good tutorial on the basics of PSO: PSO Tutorial.
Maybe you want to see PSO in action: Source Code Library: Particle Swarm Optimisation (PSO).
Wikipedia’s take on PSO: Particle swarm optimization.
