Particle Swarm Optimization: Taking a Cue from Mother Nature
Mimicking the social behavior of groups of animals to search for the minimum value of an objective function
Optimizing the solution to a problem occurs commonly in engineering and in nature. The Particle Swarm Optimization (PSO) algorithm borrows ideas from nature and is a fairly new method of optimization compared to established approaches such as Genetic, Simulated Annealing and Clustering algorithms. It mimics the social behavior of groups of animals in order to search for the minimum value of an objective function by manipulating system design variables. The swarm consists of several individual “particles,” each with a position in the design space representing a distinct design. Particles are free to move through the design space and to evaluate their fitness at discrete time steps during the optimization. Social behavior is mimicked in the sense that any promising region found in the design space by a particle is reported to the remainder of the swarm, which is then drawn toward it. This attraction ensures that the immediate neighborhoods of minima found are explored. Any sampled locations yielding improved values become new attraction points, which eventually ensure search convergence.
The swarm attraction is achieved through a simple mathematical relationship which manipulates the velocity vectors of individual particles. The velocity of particle i is updated at discrete time steps k. It is a function of its current position x and velocity v and a function of the distance from two attraction points—the ‘cognitive’ component which is that particle’s best location p and the ‘social’ component which is the entire group’s best location g. Each attraction point is associated with a weighing factor and a random number between 0 and 1.
vik+1 = wkvik + c1r1 (pik – xik) + c2r2 (gk – xik)
It is standard practice to set the cognitive and social scaling parameters c1 = c1 = 2 to allow the product c1r1 or c2r2 to have a mean of 1. These scaling values result in particles overshooting the attraction point half the time statistically, thereby maintaining separation in the group and allowing for a greater area to be searched. The position/design vector xik of individual particles is updated at each time step by simply adding the calculated velocity vector to the current position vector.
xik+1 = xik + vik+1’
The variable wk in the velocity function is a modification on the original PSO algorithm and was added to control the swarm search area. During the initial stages of the optimization it is desirable to set wk at a higher value, ensuring large distances between sampled positions and a widespread search pattern. Once the approximate region of the global minimum is found, however, this value should be reduced to allow for a refined search in order to pinpoint the exact optimum location like a pack of predators closing in on their prey. The best possible rate for this reduction is unfortunately problem dependent, and affects the efficiency of the algorithm. Too fast of a reduction may lead to regions in the design space not being explored and risks convergence to a local and not global optimum. Too slow of a reduction over-samples the design space, wasting unnecessary fitness evaluations. To date, several reduction schemes have been proposed, among which a dynamic method which monitors changes in the objective fitness value shows promise.
The inherent parallelism of the swarm behavior has allowed it to be implemented for use on massively parallel computer clusters and multi-core processors. This has enabled optimization of previously intractable problems where simulation time and complexity of the design space were barriers. The PSO algorithm has been successfully used to solve a wide ranging array of engineering problems, with examples including system identification in biomechanics, structural optimization, diagnosing Parkinson’s disease, and optimizing power distribution networks to name but a few.
Dr. Schutte recently obtained his PhD at the University of Florida and is currently employed by the Materials Sciences Corporation in Pennsylvania. His graduate studies focused on particle swarm optimization applied to structural problems and the use of parallel processing. Currently he is involved in the design and testing of composite materials for structural applications.
For further information on Particle Swarm Optimization visit http://www.particleswarm.info/