Abstract
Particle Swarm Optimization (PSO) is a simple but powerful optimization algorithm, introduced by Kennedy and Eberhart (Kennedy 1995). Its search for function optima is inspired by the behavior of flocks of birds looking for food. Similarly to birds, a set (swarm) of agents (particles) fly over the search space, which is coincident with the function domain, looking for the points where the function value is maximum (or minimum). In doing so, each particle’s motion obeys two very simple difference equations which describe the particle’s position and velocity update. A particle’s motion has a strong random component (exploration) and is mostly independent from the others’; in fact, the only piece of information which is shared among all members of the swarm, or of a large neighborhood of each particle, is the point where the best value for the function has been found so far. Therefore, the search behavior of the swarm can be defined as emergent, since no particle is specifically programmed to achieve the final collective behavior or to play a specific role within the swarm, but just to perform a much simpler local task. This chapter introduces the basics of the algorithm and describes the main features which make it particularly efficient in solving a large number of problems, with particular regard to image analysis and to the modifications that must be applied to the basic algorithm, in order to exploit its most attractive features in a domain which is different from function optimization.
TopBackground
One of the most attractive features of PSO, apart from its effectiveness and robustness with respect to local minima, is certainly its simplicity, which makes it trivial to implement in any programming language. It is also very versatile and applicable to a large number of optimization problems, virtually to any problem defined within a space for which a metric can be defined. However, its behavior, which mainly depends on the values of three constants, is still far from being fully understood. Extensive work (Engelbrecht2005, Clerc2006, Poli2007a) has provided very important insights into the properties of the algorithm, in studies where the dynamic properties of the swarm have been studied, even if under some restrictive assumptions.
The model which underlies PSO describes the motion of a swarm of particles within the domain of a function, usually termed fitness function as for evolutionary algorithms (Eiben 2004, de Jong 2006), seeking for its optimum. Such a motion is comparable to the random motion of a set of independent non-interacting particles within a force field generated by two attractors, one of which is specific to each cell.
The basic PSO equations for a generic particle P within the swarm areXP(t) = XP(t-1) + vP(t) (1)vP(t) = ω * vP(t-1) + C1 * rand() * [XPbest - X(t-1)] + C2 * rand() * [Xgbest - X(t-1)] (2) where vP is the velocity of particle P, C1 and C2 are two positive constants, ω is the so-called inertia weight, XP is the position of particle P, XPbest is the best-fitness point reached by P up to time t-1, Xgbest is the best-fitness point found by the whole swarm, rand() is a random value taken from a uniform distribution in the interval [0,1].
Key Terms in this Chapter
Sub-Swarm: In particle swarm optimization, subset of a swarm, within which the distance between any particle and the closest one is below a pre-set threshold.
Segmentation: In computer vision, a process by which an image is subdivided into regions having homogeneous visual features.
Image Analysis: Collection of techniques by which high-level information content is extracted from a digital image using image processing and computer vision techniques.
Particle Swarm Optimization: Optimization technique inspired by the exploratory behavior of animal swarms/flocks/herds in search of food.
Fitness Function: In evolutionary computation the objective function which is to be optimized.
Evolutionary Computation: Collection of techniques, basically aimed at function optimization but applicable to a huge variety of problems, by which the optimum of a function (fitness function) is sought through iterative refinements, according to rules inspired by the laws of natural evolution.
Swarm Intelligence: Collection of techniques, usually inspired by nature, in which high-level intelligent behaviors emerge as a result of the interaction among a high number of agents which, individually, perform apparently trivial, low-level tasks.