Particle Swarms

Posted by ljmacphee on April 20, 2007 under source code, topics in artificial intelligence |

Particle Swarms take several particles move them randomly around an area looking for a minimum/maximum or some other condition. As particles test each location they land at the best score for the group and each particle is updated. The particles velocity is then adjusted to head more in the direction of each one’s personal best and in the direction of the group best. The velocities also contain a random variable to keep particles from swarming the first good location they find and ending up at a local min or max.

The algorithm is very simple:
Initialize particles

Loop:
For each particle:
move
test location to see if it is better than previous best
update velocity vectors
End for each particle

Test to see if any particle has beaten the group best so far and up date if so
End Loop:

The velocity vector is calculated:
OldVelocity += ConstantForGroup * randomNumberBetweenZeroAndOne * (GroupBestLocation - CurrentParticleLocation) + ConstantForParticles * randomNumberBetweenZeroAndOne * ( PersonalBestLocation - CurrentLocation)

The time step is decreased each cycle by multiplying dt by .99. Otherwise the particles start zooming around and fail to home in except by brute force.

The example takes six particles through a hundred loops and attempts to find the location of the maximum. The code is heavily commented and should be easy to understand and adjust.

ParticleSwarm.java

See also:
Ant Algorithms
Particle Swarm Optimization ( PSO ) in Python (source code available)
Swarm Behavior - National Geographic
The swarm is reporting for duty
Swarming birds, plasma, crowds and stock markets
Swarm intelligence reaches a new level
Are swarms chaotic

More information:
Swarm approach to photography