1 Introduction

Conventional computing paradigms often have difficulty dealing with real world problems, such as those characterised by noisy or incomplete data or multimodality, because of their inflexible construction. Natural systems have evolved over millennia to solve such problems, and, when closely examined, these systems often contain many simple elements that, when working together, produce complex emergent behaviour. They have inspired several natural computing paradigms that can be used where conventional computing techniques perform unsatisfactorily.

This review considers Particle Swarm Optimization (PSO), a relatively recent addition to the field of natural computing, that has elements inspired by the social behaviour of natural swarms, and connections with evolutionary computation. PSO has found widespread application in complex optimization domains, and is currently a major research topic, offering an alternative to the more established evolutionary computation techniques that may be applied in many of the same domains.

Part II of the review is structured as follows. Section 2 briefly reviews the general formulation of PSO. Section 3 reviews the motivations for, and research into, hybrid algorithms, many of which involve evolutionary techniques. Section 4 highlights some recent research into the application of PSO to combinatorial problems. Section 5 considers the use of PSO for multicriteria and constrained optimization, typically associated with practical engineering problems. Section 6 then considers a range of indicative applications. Section 7 concludes.

2 General formulation

PSO (Kennedy and Eberhart 1995) is a simple model of social learning whose emergent behaviour has found popularity in solving difficult optimization problems. The initial metaphor had two cognitive aspects, individual learning and learning from a social group. Where an individual finds itself in a problem space it can use its own experience and that of its peers to move itself toward the solution

$$ v_{t+1} =v_i+\varphi_1 \beta_1 \left({p_i-x_i}\right)+\varphi _2 \beta _2\left( {p_g-x_i} \right) $$
(1)
$$ x_{t+1} =x_t +v_{t+1} $$
(2)

where constants \(\varphi_1\) and \(\varphi_2\) determine the balance between the influence of the individual’s knowledge \((\varphi_1)\) and that of the group \((\varphi _2)\) (both set initially to 2), β1 and β2 are uniformly distributed random numbers defined by some upper limit, βmax, that is a parameter of the algorithm, p i and p g are the individual’s previous best position and the group’s previous best position, and x i is the current position in the dimension considered. This was found to suffer from instability caused by particles accelerating out of the solution space. Eberhart et al. (1996) therefore proposed clamping the velocity to a proportion of the maximum particle movement.

However, by far the most problematic characteristic of PSO is its propensity to converge, prematurely, on early best solutions. Many strategies have been developed in attempts to over come this but by far the most popular are inertia and constriction. The inertia term, ω, was introduced thus (Shi and Eberhart 1998):

$$ v_{t+1}=\omega v_t+\varphi_1\beta_1\left({p_i-x_i}\right)+\varphi_2 \beta_2\left({p_g-x_i}\right). $$
(3)

Later work (Eberhart and Shi 2000) indicates that the optimal strategy is to initially set ω to 0.9 and reduce it linearly to 0.4, allowing initial exploration followed by acceleration toward an improved global optimum. Constriction (Clerc and Kennedy developed 1999, published 2002), χ, alleviates the requirement to clamp the velocity and is applied as follows:

$$ v_{t+1}=\chi\left\{{v_t +\varphi _1\beta _1\left({p_i -x_i } \right)+\varphi_2 \beta_2\left( { p_g -x_i}\right)}\right\} $$
(4)
$$ \chi=\frac{2}{ \left| {2-\varphi-\sqrt{\varphi ^{2}-4\varphi}} \right|}\quad \hbox{where}\,\, \varphi =\varphi_1 +\varphi _2 ,\,\,\varphi > 4. $$
(5)

Eberhart and Shi (2000) showed that combining them by setting the inertia weight, ω, to the constriction factor, χ, improved performance across a wide range of problems. Considerable research has been conducted into further refinement of PSO, and areas such as parameter tuning and dynamic environments, discussed further in Part I of this review.

3 Hybrids

Hybridisation is a growing area of intelligent systems research, which aims to combine the desirable properties of different approaches to mitigate their individual weaknesses. A range of PSO hybrids have been postulated, usually in the context of some specific application domain for which that hybrid is particularly well suited. A selection of these approaches is briefly surveyed here.

Hybridisation with Evolutionary Algorithms (EAs), including Genetic Algorithms (GAs), has been a popular strategy for improving PSO performance. With both approaches being population based, such hybrids are readily formulated. Angeline (1998) applied a tournament selection process that replaced each poorly performing particle’s velocity and position with those of better performing particles. This movement in space improved performance in three out of four test functions but moved away from the social metaphor of PSO. Brits et al. (2002) used GCPSO (van den Bergh and Engelbrecht 2002) in their niching PSO (NichePSO) algorithm. Borrowing techniques from GAs, the NichePSO initially sets up sub-swarm leaders by training the main swarm using Kennedy’s (1997) cognition only model. Niches are then identified and a sub-swarm radius set; as the optimization progresses particles are allowed to join sub-swarms, which are in turn allowed to merge. Once particle velocity has minimised they have converged to their sub-swarm’s optimum. The technique successfully converged every time although the authors confess that results were very dependent on the swarm being initialised correctly (using Faure sequences).

One of the main differences between PSO and GAs is the technique used to create new potential solutions. In PSO the individuals move through the solution space through perturbations of their position (which are influenced by other swarm members), in a GA population, members breed with each other to produce new individuals. Løvebjerg et al. (2001) improved convergence speed through the application of breeding, whilst avoiding sub-optimal solutions through introducing subpopulations. This approach suffered in unimodal problems, when compared with the canonical PSO, because new offspring had no knowledge of the group best position and the value to be gained from the social metaphor of shared group knowledge was lost. In multimodal problems, this, in association with the subpopulation technique, was found to be beneficial; the newly produced offspring did not suffer from the cognitive dissonance of the older population and thus did not attempt to cluster about existing solutions.

The development of the genotype to produce a phenotype behaviour that is influenced by the environment was the inspiration behind Krink and Løvebjerg’s (2002) Lifecycle model. In this work the authors allowed each candidate solution to decide what the most productive development path might be (PSO, GA or hill climber) depending on its knowledge of its recent success in improving its fitness. Once the decision is made, the individual joins a population of other candidates who share the same development programme. In experiments using common test functions, the Lifecycle model outperformed populations using the individual techniques. Zhang and Xie (2003) also used different techniques in tandem, rather than combining them, in their Differential Evolution (DE) PSO (DEPSO). In this case the DE and canonical PSO operators were used on alternate generations; when DE was in use, the trial mutation replaced the individual best at a rate controlled by a crossover constant and a random dimension selector that ensured at least one mutation occurred each time. The hybrid was found to be successful for some functions, but not all, with results indicating that DEPSO improves on PSO in problems with higher dimensionality.

Gaussian mutation was combined with velocity and position update rules by Higashi and Iba (2003) and was tested on unimodal and multimodal functions. The hybrid achieved better results than those of GA and PSO alone. Juang (2004) also incorporated mutation alongside crossover and elitism. The upper-half of the best-performing individuals, known as elites, are regarded as a swarm and enhanced by PSO. The enhanced elites constitute half of the population in the new generation, whilst crossover and mutation operations are applied to the enhanced elites to generate the other half. This process imitates the natural phenomenon of maturation and outperformed both PSO and GA in the study.

Inspiration for the Cooperative PSO (van den Bergh and Engelbrecht 2004) was provided by the more specialised Cooperative Coevolutionary Genetic Algorithm developed by Potter and de Jong (1994). This aims to minimise the exponential increase of difficulty in optimizing problems with higher dimensions through targeting each dimension as a single dimensional problem. Several cooperative strategies were developed where small swarms tackle each dimension and cross-dimension communication allows the overall solution to move toward the goal. However, this introduced the potential to stagnate due to the serial nature of swarm evaluations and sub-swarms finding pseudo-minima. These problems were countered by combining the cooperative and single swarm approaches. The problem with cooperative swarms is the large increase in algorithmic complexity. The authors avoid this aspect since performance is measured in objective function evaluations rather than execution time. The constricted PSO still compares favourably, especially in problems with lower dimensionality—a prime example of the “No Free Lunch” theorems of Wolpert and Macready (1997).

Liu and Abraham (2005) hybridised a turbulent PSO (TPSO) with a fuzzy logic controller to produce a Fuzzy Adaptive TPSO (FATPSO). The TPSO used the principle that PSO’s premature convergence is caused by particles stagnating about a sub-optimal location. A minimum velocity was introduced with the velocity memory being replaced by a random turbulence operator when a particle exceeded it. The fuzzy logic extension was then applied to adaptively regulate the velocity parameters during an optimization run thus enabling coarse-grained explorative searches to occur in the early phases before being replaced by fine-grained exploitation later. The technique was evaluated on problems with low and high dimensionality and found to perform well against both. Notably, whilst the performance of canonical PSO degraded considerably as dimensionality increased, the TPSO and FATPSO remained largely unaffected.

It has been argued that the PSO metaphor is more important than the implementation itself (Kennedy 2003). Poli et al. (2005) took this to the extreme and applied GP to develop more efficient PSO algorithms on a problem-by-problem basis. The rationale behind their approach was that GP could be used to routinely evolve specialist position update algorithms for use by PSO in order to meet the needs of specific problem domains. Using several fitness measures, three of the evolved algorithms were selected for competition against four basic (human derived) algorithms taken from the literature. Using the city block sphere and Rastrigin functions (unimodal and multimodal problems respectively) the evolved algorithms outperformed their competitors. The work does suggest that, as the hardware becomes more powerful, it may be the social metaphor of PSO that is the key and the actual mechanics may be developed on the basis of the requirements of individual applications.

Recently, Jian and Chen (2006) introduced a PSO hybrid with the GA recombination operator and dynamic linkage discovery to optimize difficult real number optimization problems. Dynamic linkage discovery is a technique based on the notion that if the links between the basic building blocks of the objective function can be discovered then optimization of that problem can be improved. The approach first applies linkage discovery to the function before running the PSO with recombination operator for a specified number of generations. This is repeated until fitness improvement checks indicate no further value in applying the linkage discovery at which time the PSO with recombination operator is repeated until a given termination requirement is met. A number of standard objective functions were used in experimentation, and results were promising, with only the toughest problems, containing many local minima, evading solution.

Further hybrid approaches are discussed in later sections, in connection with specific applications.

4 Combinatorial problems

NP-hard combinatorial problems exist in scenarios such as the Travelling Salesman Problem (TSP) and scheduling and have been addressed by a variety of PSO techniques.

The fuzzy discrete PSO (Pang et al. 2004) is a matrix based approach where the TSP is represented as a matrix containing the set of cities and the TSP sequences. The particle position is a fuzzy matrix, the values of which represent the degree of membership to the corresponding elements of the TSP matrix (the particle velocity continues to represent the movement through the solution space but is also formulated as a matrix). Equation 3 is then modified to accommodate the matrix representations of positions and velocities. This approach allows the solution to a discrete problem to be sought in continuous space, since the fuzzy membership is in the real number range [0, 1]. Initial experimentation showed that the technique was viable for such problems, although further development was encouraged.

Lopes and Coelho (2005) combined PSO with Fast Local Search (FLS) and included Genetic Algorithm (GA) concepts. The GA influenced PSO is used to guide the particles at the macro level (exploration), whilst at each iteration the FLS is employed to search for locally improved solutions (exploitation). Experimentation using PSO with and without hybridisation across wide ranging instances of the TSP showed the average excesses above the known optima to be 2.5 and 87%, respectively.

Using a similar ploy, Habibi et al. (2006) also developed a hybrid PSO, this time with Ant Colony (AC) and Simulated Annealing (SA). The AC algorithm replaces the individual best element of PSO, whilst the cooling process of SA is used to control the exploration of the group best element, both of which are then applied within the PSO framework (all random numbers being generated using a Gaussian distribution function). Experimentation with known TSP instances indicated that good approximations can be found efficiently (achieving 100 and 97% of optimality in Burma14 and Berlin52, respectively).

As indicated earlier, discrete problems can be also optimized in continuous space through a suitable mapping of the problem space to the potential solutions generated. Parsopoulos and Vrahatis (2006) applied their previously developed Unified PSO (Parsopoulos and Vrahatis 2004) to the single machine total weighted tardiness problem, by utilising the Smallest Position Value (SPV) mapping mechanism (Tasgetiren et al. 2004). In the SPV scheme the schedule is produced by placing the index of the lowest valued particle component as the first item, the next lowest as the second and so on. For example, a given particle having position (3.23, 1.45, −9.34, 0.01) would represent the potential schedule (3, 4, 2, 1). This potential schedule would then be submitted to the objective function for an assessment of its fitness. In a comparison with the constricted PSO, Eqs. 4 and 5, in fully connected and ring neighbourhood schemes using 40 and 50 task problems, several versions of the Unified PSO, each having differing levels of balance between exploitation and exploration, were found to be competitive, with the most accurate being a variant that also included a level of mutation.

Chen et al. (2006) also utilised SA in a hybrid with a quantum Discrete PSO (DPSO, Yang et al. 2004) for application to the Capacitated Vehicle Routing Problem (CVRP). DPSO is similar to Kennedy and Eberhart’s (1997) discrete PSO, in that the particle position represents a probability that a value will be a 1 or 0, but applies a different series of equations to calculate the probability values. To map the CVRP to the DPSO binary particles, each particle has K sections, each having N bits, where each section represents a vehicle and each bit represents a customer. If a customer is to be served by a particular vehicle the corresponding customer bit is set in the section for that vehicle. The hybrid is applied to the problem in a stepwise manner: initially, the DPSO is applied to the particles providing a globally influenced move to new locations; then, at the new locations, SA is applied to each particle to provide a local search, with each particle moving to the best location in its vicinity; the process is then repeated until the stopping criteria are met. In comparisons with GA and SA approaches, the hybrid DPSO showed large improvements in terms of accuracy and efficiency, finding the optimum several times, indicating the technique could be useful for difficult combinatorial problems.

5 Multicriteria and constrained optimization

In the real world, there is often a need to optimize a solution across multiple objectives where the various trade-offs between objectives creates a series of potential solutions across a Pareto Optimal Front. This is typical of engineering design problems. Further, many practical problems introduce constraints such that portions of the search space are invalid. Addressing Multiple Objective (MO) and Constrained Optimization (CO) problems remains an active area of research. PSO can be applied to such problems, but due to its unconstrained characteristics the technique must be modified. The following research can be seen to either redefine the manner in which the local or global best solutions are dealt with and/or to introduce an archiving system to maintain an elite set of the best non-dominated solutions. These techniques can be employed in the application of PSO to the field of Engineering Optimization (EO).

Parsopoulos and Vrahatis (2002b) presented an initial investigation into the potential of PSO to produce a Pareto front using a modified PSO system based on Schaffer’s (1985) Vector Evaluated GA. The approach utilised multiple swarms, each targeting one of the objectives, the best particle from one swarm being used as the global best for another. Later work (Parsopoulos et al. 2004) indicated that the approach could be further improved through parallelisation, although performance degraded with larger numbers of swarms due to communication overheads.

At a similar time, Hu and Eberhart (2002a) developed a Dynamic Neighbourhood PSO (DNPSO) in which each particle calculates its fitness and uses the proximity of neighbouring particles against each objective function to deduce its own local best solution. As the particle moves through the problem space the particles in its neighbourhood will change as the Pareto front emerges. A later modification using an archive to maintain a record of Pareto solutions reduced computational time (Hu et al. 2003a). Coello Coello and Lechuga (2002) also produced an alternative method of determining the local best solution by dividing the search space into hypercubes and applying a form of elitism, made possible by a repository of best non-dominated vectors. The approach compared well against two competitive EAs in terms of quality, and bettered them in terms of speed.

The Sigma method was introduced by Mostaghim and Teich (2003a) to redefine the selection of each particle’s local best. To do this they calculate a sigma value for each particle (based on the swarm’s minimum/maximum objective function solutions) and compare it with the sigma values from an archive of particles (maintained using a clustering technique). The local best is then selected as the archive particle with the closest sigma value. The technique was compared with an EA and was competitive with two objectives, but was not as accurate with three. Further work (Mostaghim and Teich 2003b) improved the performance of the Sigma method by improving the archiving system through the use of ε-dominance.

Zhang et al. (2003) used a more simple averaging method in their determination of global best positions. After calculating the particle best positions for each objective function, the group best for each function is used to find the average group best. The group best is only used where it is closer than the particle best, otherwise a random position between the objective function positions of the particle best is used. The approach works well with two objectives but was not tested at higher levels of complexity.

Lu (2003) produced two PSO/EA hybrids to improve MO PSO. The first uses a dynamic MO EA (Yen and Lu 2002) as the framework, but replaces the crossover and mutation mechanisms with PSO, this had the effect of speeding up the optimization at the expense of the quality of the Pareto front. To overcome the reduction in quality the second hybrid reintroduces the EA crossover mechanism, which in combination with the PSO speeds up convergence and improves the quality of the Pareto front (compared with the original dynamic EA).

Baumgartner et al. (2004) utilised the conventional weighted sum technique to calculate the swarm leader and then Pareto optimality is detected using a two-stage process. First the new particle position is checked for improvement on the previous position; if it is, then a gradient-based algorithm is applied. If the particle is optimal, it is removed and archived. The approach was successfully applied to a magnetics problem.

Sierra and Coello Coello (2005) implemented a crowding based selection to control the number of leading particles, along with mutation and a ε-dominance controlled archive, and thus improved the performance of MO PSO through increased control of particle distribution and the size of the archive. The performance did suffer at the extremes of the Pareto front, but was highly competitive against other MO PSO and MO EAs. Suggested further work targets the archiving as the technique’s weakness.

Xiao-hua et al. (2005) applied an Agent-Environment-Rules (AER) model to drive the particles toward the Pareto front. The AER model is inspired by Marvin Minsky’s book, Society of Mind (1986), and each particle is endowed with the properties required by AER agents; some of which they already possess, such as cooperation, whilst others, such as competition and clonal mutation, are introduced. Experimentation showed the approach could be used to improve PSO solution diversity and convergence across a range of MO problems.

Recent applications of PSO to MO problems have included the design of combinatorial logic circuit (Luna et al. 2004), the design of high performance microwave absorption coatings (Goudos and Sahalos 2006) and the analysis of water for selective withdrawal from a thermally stratified reservoir (Baltar and Fontane 2006).

Hu and Eberhart (2002b) adopted a trial and error approach to CO using the canonical PSO with two modifications: first, particles were only initialised to feasible positions, and, second, only solutions that satisfied the constraints were used for the local and global best positions. The results of experimentation using 12 known test problems indicated that PSO was a viable alternative to GA. Parsopoulos and Vrahatis (2002c) utilised problem dependent dynamic penalty functions taken from existing EA work for CO. Three variants of PSO (inertia only, constriction factor only and a combination thereof) were compared with other EAs that used the same penalty functions and found to be competitive.

Zavala et al. (2005) explored the CO problem of reliability against cost in product design. They proposed a novel PSO that uses a ring topology and a combination of feasibility and domination in the selection of the local best particle. EA inspired perturbations are then applied to the particles to maintain diversity and exploration within the swarm.

PSO has been applied to EO in both single and multi-objective problems. Gaing (2003) applied PSO to solving the economic dispatch problem considering the generator constraints. This is a problem in power system operation with the objective of reducing the total generation cost of units while satisfying constraints of the ramp rate limit and prohibited operating zone. Hu et al. (2003b) used PSO to solve some EO problems: the design of a pressure vessel, welded beam design, minimisation of the weight of a tension/compression spring and Himmelblau’s non-linear optimization problem. Their approach involved starting the population with only feasible solutions and the particles keeping only feasible solutions in their memory after updating. Robinson and Rahmat-Samii (2004) applied PSO to the design of a profiled corrugated horn antenna. The PSO also incorporated the invisible wall boundary approach to handle constraints.

6 Applications

PSO has been applied, largely in the research laboratory, to problems from a wide range of domains. In this section, a cross-section of applications of particle systems, aside from that of computer animation, is briefly surveyed, with pointers to the relevant literature for those interested in investigating particular domains in further detail. Utilising PSO as a paradigm can be subdivided into two main approaches: the first exploits its ability to optimize efficiently, which often requires adapting PSO to meet the specific needs of the problem; the second adapts the problem to allow the use of PSO. A third, less common, approach uses the original social metaphor of individual and group learning to provide further insight into how individuals within groups behave.

The strength of Artificial Neural Networks (ANNs) in pattern matching applications is often lessened by problems due to the size of associated optimization aspects or changing environments where the ANN would need to be taken offline for re-training. Conradie et al. (2002) investigated the possibility of augmenting standard neurocontrollers in industrial processes with a PSO based algorithm known as Adaptive Neural Swarming. PSO was selected for its ability to match the weights of the controller to the changing environment without taking the controller off-line, thus balancing the need to adapt with the requirement to generalise. Experimentation using a simulated non-linear bioreactor indicated that profitability could be significantly improved without destabilising the process.

To overcome the speed problem of a practical ANN based face recognition system, caused by the high-dimensionality of the classification stage and the size of the search stage, Sugisaka and Fan (2005) improved the search stage of the recognition process by expressing it as an integer non-linear optimization problem and applying an extended PSO algorithm. During experimentation the approach was found to be competitive, but was outperformed by a system using a more computationally efficient classifier. This suggests that whilst PSO can accelerate the overall process, the search aspect is not the area where most efficiency gains can be made. Other work using PSO in collaboration with ANNs has been carried out by Ismail and Engelbrecht (1999), van den Bergh and Engelbrecht (1999, 2000), Voss and Feng (2001, 2002, 2003), in combination with a Group Method Data Handling ANN (psychological-social metaphor only), Mendes et al. (2002), Xiao et al. (2003), Chen et al. (2004), Georgiou et al.(2004) and Karpat and Özel (2006).

In addition to ANNs, PSO has also been successfully applied to training Neural Fuzzy Networks (NFNs), which are a hybridisation of ANNs with fuzzy controllers. Lin et al. (2006) utilised a PSO hybrid with a local approximation method (to initialise the swarm to an approximate solution) and multi-elites strategy (to slow convergence and thus try to avoid sub-optimal solutions) combined with Recursive Singular Value Decomposition to improve the learning process of a Takagi-Sugeno-Kang type NFN. The hybrid learning algorithm replaced the more usual back propagation algorithm, with each particle representing a potential set of antecedent parameters. Experimentation indicated that the approach offered a more accurate and efficient training regime. In a different approach to NFNs, Mehran et al. (2006) employed PSO to assist with the division of the input space in a locally linear NFN. The input space division is a divide-and-conquer technique, with the division lines being produced by the Local Linear Model Trees (LOLIMOT) learning algorithm, and PSO is applied to the process to reduce the number of redundant local models produced. This is achieved by representing each potential network as a particle (having components that represent the input space partitions); particle movement represents sliding the input space partitions to produce new input space divisions, and the fitness function is the error produced by that model. The use of PSO proved successful in producing smaller errors and consuming fewer models during the learning process.

Colour image quantisation is the process of reducing the number of colours used to reproduce an image. It takes the desired colour for a pixel in the image and attempts to match it as closely as it can to the available colour map. Omran et al. (2005) extended PSO, in a technique known as PSO-CIQ, to match the desired colours with a given colour map. Their approach used each particle to represent a candidate colour map, thus the swarm represents a number of candidates. Pre-processing of the particles in each time-step using the K-means clustering algorithm is used to reduce the search space before each pixel in the image is assigned to the cluster with the closest match. A mean squared error fitness function is then applied before the canonical PSO is used to move the particles. Experimentation indicated the approach compared well with several other well-known soft computing colour image quantization techniques (self-organising maps and the genetic C-means algorithm).

Recommender systems, software tools designed to make recommendations to users of Internet e-commerce sites, are a further area in which the utilisation of PSO as a tuning mechanism has been investigated. Ujjin and Bentley (2003) compared PSO with a GA and a Pearson algorithm as tuners of a collaborative filtering system using a dataset containing 22 features. They found that, in general, the PSO based system was faster, particularly when compared with the GA, and more accurate than its rivals in matching user profiles.

In the field of computational biology, Chang et al. (2004) utilised HPSO-TVAC (with minor modifications to prevent the algorithm from introducing artificial local minima) to improve protein motif discovery. A protein sequence motif is a short sequence of amino acids that exist within a protein family. Being able to identify and classify motifs can assist with the more complex process of classifying unknown proteins. The optimization process encodes the symbolic representations of the acids into numerical form, and the sequences are then subjected to a fitness function that scores the unknown pattern against existing patterns. The approach was compared with a manual method and a combinatorial method with neuro-fuzzy optimization. The modified HPSO-TVAC easily outperformed the former and matched the latter in terms of quality. The PSO based method had the additional strength of speed during the optimization phase (i.e., post-initial motif generation) although premature convergence was cited as problematic. Hsiao et al. (2005) also exploited the speed and efficiency of PSO in a similar biological application, this time to improve bimolecular sequence alignment in much larger DNA or protein sequences. To enable the use of PSO the problem was first adapted to form a suitable solution space. This involved creating particles that consisted of sequence arrays, which were then quality scored by an objective function that produced three performance indices (matched score, mismatched score and gap penalties) before the particles were moved using the PSO algorithm. The technique outperformed other established alignment methods in both speed and matching ability, with the advantages being most notable in sequences with lengths over 2000.

Wachowiak et al. (2004) developed a bespoke PSO system, in which a third social influence was added, to optimize the global search element of biomedical image registration. Image registration is the process of taking several 2-D images from various sources, such as Computer Assisted Tomography (CAT) and Magnetic Resonance Imaging (MRI) scans, and combining them into a 3-D image. The new PSO influence was that of a clinical expert who initially positioned the images in approximately the right vicinity, effectively preventing the swarm from being drawn away from a known good search area by local optima. In experiments the bespoke PSO was also hybridised with several other evolutionary techniques such as crossover and mutation, these further improved the approach and promising results achieved. A further medical science application has been proposed by Li et al. (2005), in which PSO is used to assist in the selection of optimal beam angles in intensity-modulated radiotherapy and thus assisting in safer and more effective treatment of tumours. To achieve this, candidate beam angles are mapped to particles that are optimized to form a beam intensity map, which is then optimized using a conjugate gradient algorithm, and evaluated using a fitness function prior to position update. During simulation based experimentation on representative problems (prostrate and head and neck) the technique was shown to match or improve on results achieved using a GA.

The equipment used in such medical fields is also being affected through the possibility of enhancing engineering design using PSO. Das et al. (2005a) applied a modified PSO (DV-PSO, Das et al. 2005b) to improve the design of Infinite Impulse Response (IIR) filters used in biomedical imaging such as digital mammography. To enable the use of DV-PSO the problem was reformulated as a constrained minimisation problem with each trial solution being presented as a particle in the search space. Results showed the technique to be simpler than other recent approaches, whilst still providing faster and better solutions.

Initial progress has also been made in the study of modelling biomechanical movement to develop understanding in the field of kinesiology. Khemka et al. (2005) used PSO to optimize a biomechanical model of a football kick. The model simulates the 17 different muscle groups involved in kicking a ball, a complex leg movement that results in a 56-dimension search problem, and includes realistic constraints, such as the toes must not hit the floor, which were imposed using heavy fitness penalties. Results were found comparable to those from sports equipment manufacturer research.

Financial forecasting traditionally adopts statistical techniques, with varying degrees of success, and usually on the assumption of linearity. Ko and Lin (2004) adopted a hybrid of PSO with statistical techniques, essentially with the aim of optimizing the inputs to a regression process. The approach, when compared with statistical and GA approaches, was found to offer improved performance. Other financial sector implementations of PSO have been proposed by Nenortaite and Simutis (2004), Kendall and Su (2005) and Nenortaite (2005).

Balci and Valenzuela (2004) improved on the PSO based solution to the Unit Commitment Problem (UCP) presented by Ting et al. (2003) by using PSO combined with Lagrangian Relaxation (LR). The UCP is described as a non-linear, mixed integer combinatorial problem for optimizing the generation of electricity in a competitive power supply market. In this complex hybridisation the PSO is used to search for the optimal Langrangian multipliers that are then used in the sub-problems created in the LR process, which are in turn solved using Dynamic Programming. A standard 10-unit problem was used to compare the approach with other optimization techniques, including PSO, and was found to be several times more efficient whilst maintaining a competitive solution quality. Application to other areas of electric power systems has included voltage control (Yoshida et al. 2001), dynamic security border identification (Kassabalidis et al. 2002), optimal power flow (Abido 2002), distribution state estimation (Naka et al. 2003), post-failure restoration (Jiménez and Cedeño 2003) and generation expansion planning (Kannan et al. 2004).

Foo et al. (2005) reduced the optimal wavelength converter placement problem in wavelength routed optical networks to a binary optimization problem. Working as part of a larger system optimization paradigm, in which the best routing scheme is initially found using either a traffic engineering (TE) aware or equal-cost multipath (ECMP) algorithm, a binary PSO (BPSO) was then applied to locate the optimal position for the converters. The effectiveness of the process was assessed in comparisons of the blocking probability and network efficiency against the number of converters. In terms of blocking probability, BPSO was found to work best with ECMP and in efficiency tests the BPSO process was found to be most useful where large numbers of converters are in use since in small systems all the combinations are generally tried anyway.

The social metaphor of PSO has also been exploited to provide insight into the causes of organisational inertia. Brabazon et al. (2005) produced a model (OrgSwarm) of strategic adaptation in large profit making organisations using the swarm particles to represent organisations and the NK model (Kauffman and Levin, 1987) to represent the strategic landscape. In dynamic environments, in which organisations usually exist, they found that without the application of some inertia and a type of elitism (that ensured only improving moves were made by organisations), the particles performed a random search constantly attempting to relocate the optimal position, thus concluding that some strategic inertia could benefit organisations by preventing unnecessary organisational change.

7 Conclusions

Particle swarm optimization, in its present form, has been in existence for roughly a decade. In that time, it has gathered considerable interest from the natural computing research community and has been seen to offer rapid and effective optimization of complex multidimensional search spaces, with adaptations to multiple objective and constrained optimization. Whilst Part I of this review considered the origins and development of the PSO paradigm, Part II has focussed on recent research in some of the more complex active areas of research: hybridisation, combinatorial problems, multiple objective and constrained optimization. Hybridisation, in particular, is seen as a useful way of combining PSO’s strengths, such as rapid optimization, with other useful techniques, particular from the somewhat related field of evolutionary computation, which help alleviate some of the challenging aspects of PSO performance, such as stagnation.

Considerable research has been invested in adapting and refining PSO algorithms to cope with multiple objectives and optimization in the presence of constraints, both of which are important steps to facilitating engineering design optimization and whilst appreciable levels of success have been seen in these areas in recent years, they remain active research topics. The rapid development of the paradigm has led to an explosion in applications. In this review, a variety of domains are briefly touched upon, including the optimization of artificial neural networks, neural fuzzy networks, image processing and medical imaging, computational biology, financial forecasting, optimization of electricity generation and network routing. Naturally, there are many more applications of PSO within the literature, and it has been seen to offer general principles that can be readily adapted to a very wide range of domains.

This paper has offered a timely review of this increasingly important natural computing paradigm. It has found PSO to be highly effective and adaptable to diverse application requirements, with considerable potential for hybridisation and integration into a range of intelligent systems. Challenges remain, in areas such as dynamic environments, avoiding stagnation, handling constraints and multiple objectives, and these are pertinent research foci evident from the literature. Like evolutionary algorithms, PSO has become an important tool for optimization and other complex problem solving. The next decade will no doubt see further refinement of the approach and integration with other techniques, as well as applications moving out of the research laboratory and into industry and commerce. Further understanding of the relative strengths of PSO and other techniques, and the challenges in deploying a PSO based system are required. However, PSO is certainly a welcome addition to the optimization toolbox.