The bottom of this page contains a simple Java applet which visually demonstrates a particle swarm searching for a maximum value in a 3-D landscape. The Java applet is delivered as a 45KB jar file which has been tested with the Microsoft JVM installed under IE6 but should work with any JVM 1.1 or higher.

Particle Swarm Optimization is an approach to problems whose solutions can be represented as a point in an n-dimensional solution space. A number of of particles are randomly set into motion through this space. At each iteration, they observe the "fitness" of themselves and their neighbours and "emulate" successful neighbours (those whose current position represents a better solution to the problem than theirs) by moving towards them. Various schemes for grouping particles into competing, semi-independent flocks can be used, or all the particles can belong to a single global flock. This extremely simple approach has been suprisingly effective across a variety of problem domains.

PSO was developed by James Kennedy and Russell Eberhart in 1995 after being inspired by the study of bird flocking behaviour by biologist Frank Heppner. It is related to evolution-inspired problem solving techniques such as genetic algorithms.

Resources

• Particle Swarm Optimization, paper by James Kennedy and Russell Eberhart
• Book: Swarm Intelligence by James Kennedy, Russell C. Eberhart, with Yuhui Shi (Table of contents)
• Particle Swarm Central - a directory of resources pertaining to PSO

Feel free to contact Project Computing to discuss applications of PSO.

PSO is typically used to address problems with many unknowns (of many "dimensions"). This visualisation is comparatively extremely simple and trivial: the swarm searches across 2 unknowns (or "dimensions"), and the value of each point in these 2 dimensions has been plotted in the 3rd dimension.

This applet was written by Kent Fitch, Project Computing by building on and combining modified versions of these 2 programs:

• The code included in 3D computer graphics: Moving from wire-frame drawings to solid, shaded models by Todd Sundsted, which appeared in JavaWorld, July 1997. Although the Java 3D-API provides the required functionality, Todd's code is simple and runs under Java 1.1
• The PSO implementation from adaptiveview.com, which is simple and was easy to make run under Java 1.1.

• This applet generates a semi-random 3-D landscape. A randomly generated particle swarm of 12 particles attempts to find the "global maximum" on the landscape. The swarm does not "know" what the maximum value is: it is just told to stop when it encounters it.
• A new swarm (with new starting positions) can be generated, as can new landscapes.
• The swarm of 12 particles can "work together" as 1 flock, or can be divided into 2, 3 or 4 semi-autonomous flocks.
• The swarm can be run to completion (or 100 iterations), "single stepped" and paused.
• Different colours are used to render the position of the current and previous generations, and movement tracks are rendered to help visualize the progress of the swarm.

• Wait until the applet loads. As the code is only 45KB, this shouldn't take long. You should then see a 3-D landscape below. Either start clicking buttons, or read the explanation which follows!
• The global maximum (which is the point the swarm is seeking) is marked with a red arrow.
• You can rotate the landscape using the Up/Down/Left/Right buttons, or by clicking on the landscape and using the arrow keys. You can't rotate the landscape using the mouse.
• Click the "step" button. This will initialise the swarm on the landscape. The initial position of each particle will be shown by a small green marker. Rotate the landscape to see the particles in relation to each other and the maximum.
• Click the "step" button again. The green squares will move, generally in the direction of the "fittest" particle. The previous location of the particles is marked with a yellow marker, and a green line is drawn from the previous to the current location, "visualising" the movement.
• "Step" again: the original generation is now coloured magenta, the second generation is now coloured yellow and the location of the current generation is again rendered in green. Yellow lines shows the vectors taken by the original generation moving to the second generation, and green lines show the vectors taken by this generation moving to the current generation.
• "Step" again: the original generation is now coloured blue. Step again, and this generation is now black. That is, generations are represented using the following colours: green, yellow, magenta, blue, black. The positions of all generations older the most recent 4 are rendered in black. Movement vectors are shown for just the 2 most recent generations.
• The movement vectors are always rendered "on top" of the landscape and can be seen even if the landscape would obscure the vector in the "real world".
• The status information at the bottom of the applet window shows the number of iterations completed, the maximum value the swarm is seeking, the maximum value found in the last (most recent) iteration and the maximum value found in any iteration in this run.

• First single-step the swarm to get a feeling for what is going on. This is easiest with just 1 flock, as there is no visual indication of which particles are in grouped together in a flock.
• Then run a few tests to completion, observing the flock moving across the landscape.
• Notice how rerunning tests on the same landscape produces often startlingly different results; that is, how some starting positions of the particles lead to rapid location of the global maximum, and how other positions lead to failure after 100 iterations.
• Test the results of using different numbers of flocks on the same landscape.
• Try new landscapes. Observe how some landscapes are just more difficult, such as those with "attractive" local maxima some distance from the global maximum.
• Notice that the swarm has no memory other than the current generation. It revisits previous locations which, if it had such a memory, it would "know" cannot be the global maximum. Also notice that sometimes repeating patterns will be set up, often with multiple particles simultaneously traversing the same vectors.