display | more...

A method developed by James Kennedy and Russ Eberhardt in 1995 as an evolutionary computation and social behavior modeling tool, specifically for optimization of nonlinear functions. It is strikingly similar to the foundation Genetic Algorithms.

Particle swarm optimization (an outgrowth of swarm intelligence research) can be thought of as a process whereby fauna move in n-dimensional space, each fauna being a "solution" and the space being the problem. For example, a flock of birds flying through the problem, where the problem is locating the nearest food source, or the distribution of heat sources in the vacuum of space. As a social psychology tool, each particle represents a setting of abstracted behavior, and their movement defines a global pattern of response. Particle swarm optimization can also be used to show behavior in group dynamics situations.

In particle swarms, there is no central control, as in a ant colony - each particle is simply an agent that acts on information given to it. PSO and particle swarms are the basis for a theory called swarm intelligence, where each particle, even though they are not directed by a hive mind (such as an ant colony queen) can become much greater than the sum of their parts. This makes it an effective method for modelling the behavior of individuals rather than slaves.

Particle swarm optimization defines two properties (outside of velocity, which directs movement throughout the problem space) which are communicated locally and globally throughout the swarm: lBest and gBest. These represent local and global effectiveness (fitness) of each solution as it passes through the problem space. The individual particle stores another value, pBest, as it passes through the space. This value is expressed as the effectiveness of that particle so far. Think of gBest as the maximum effective solution thus far. Particles follow the neighboring optimum particles by changing these properties in each iteration or generation.

Unlike other genetic algorithms, particles in this context do not possess "mating" properties, like mutation and crossover. They do, however, have memory. PSO is pretty simple, mathematically, and has application to a wide range of problems in several different areas. It is effective against the traveling salesman problem.

It is often compared to the ant colony algorithm, which operates differently. The ants drop stuff to lay a trail. The particles use the ansible of Ender's Game fame to communicate simultaneously during each iteration. Broadcast. Iterate. Broadcast. Iterate.

Pretty cool stuff.

Log in or register to write something here or to contact authors.