Particle swarm optimization algorithm: an overview

1 Soft ComputDOI swarm optimization algorithm: an overviewDongshu Wang1 Dapei Tan1 Lei Liu2 Springer-Verlag Berlin Heidelberg 2017 AbstractParticle swarm optimization (PSO) is apopulation-based stochastic optimization algorithm moti-vated by intelligent collective behavior of some animals suchas flocks of birds or schools of fish. Since presented in 1995, ithas experienced a multitude of enhancements. As researchershave learned about the technique, they derived new versionsaiming to different demands, developed new applications in ahostofareas,publishedtheoreticalstudies oftheeffectsofthevarious parameters and proposed many variants of the algo-rithm. This paper introduces its origin and background andcarries out the theory analysis of the PSO. Then, we analyzeits present situation of research and application in algorithmstructure, parameter selection, topology structure, discretePSO algorithm and parallel PSO algorithm, multi-objectiveoptimization PSO and its engineering applications.

2 Finally,the existing problems are analyzed and future research direc-tions are by A. Di supplementary materialThe online version of thisarticle ( ) contains supplementarymaterial, which is available to authorized of Electrical Engineering, Zhengzhou University,Zhengzhou 450001, Henan, China2 Department of Research, The People s Bank of China,Zhengzhou Central Sub-Branch, Zhengzhou, ChinaKeywordsParticle swarm optimization Topologystructure Discrete PSO Parallel PSO Multi-objectiveoptimization PSO1 IntroductionParticle swarm optimization (PSO) algorithm is a stochasticoptimization technique based on swarm , which was proposedbyEberhart and Kennedy(1995) andKennedy and Eberhart(1995). PSO algorithm simulates animal s social behavior,including insects, herds, birds and fishes. These swarms con-form a cooperative way to find food, and each member in theswarms keeps changing the search pattern according to thelearning experiences of its own and other design idea of the PSO algorithm is closely relatedto two researches: One is evolutionary algorithm, just likeevolutionary algorithm; PSO also uses a swarm mode whichmakes it to simultaneously search large region in the solu-tion space of the optimized objective function.

3 The other isartificial life, namely it studies the artificial systems with studying the behavior of social animals with the artifi-cial life theory, for how to construct the swarm artificial lifesystems with cooperative behavior by computer, Millonasproposed five basic principles (van den Bergh 2001):(1) Proximity: the swarm should be able to carry out simplespace and time computations.(2) Quality: the swarm should be able to sense the qualitychange in the environment and response it.(3) Diverse response: the swarm should not limit its way toget the resources in a narrow scope.(4) Stability: the swarm should not change its behavior modewith every environmental Wang et al.(5) Adaptability: the swarm should change its behavior modewhen this change is of the same coin. These five principles include the maincharacteristics of the artificial life systems, and they havebecome guiding principles to establish the swarm artificiallife system.

4 In PSO, particles can update their positions andvelocities according to the environment change, namely itmeets the requirements of proximity and quality. In addition,the swarm in PSO does not limit its movement but contin-uously search the optimal solution in the possible solutionspace. Particles in PSO can keep their stable movement in thesearch space, while change their movement mode to adaptthe change in the environment. So Particle swarm systemsmeet the above five Origin and backgroundIn order to illustrate production background and developmentof the PSO algorithm, here we first introduce the early simplemodel, namely Boid (Bird-oid) model (Reynolds 1987). Thismodel is designed to simulate the behavior of birds, and it isalso a direct source of the PSO simplest model can be depicted as follows. Each indi-vidual of the birds is represented by a point in the Cartesiancoordinate system, randomly assigned with initial velocityand position.

5 Then run the program in accordance with thenearest proximity velocity match rule, so that one individualhas the same speed as its nearest neighbor. With the iterationgoing on in the same way, all the points will have the samevelocity quickly. As this model is too simple and far awayfrom the real cases, a random variable is added to the speeditem. That is to say, at each iteration, aside from meeting thenearest proximity velocity match, each speed will be addedwith a random variable, which makes the total simulation toapproach the real designed a cornfield model to simulate the for-aging behavior of a flock of birds (Clerc and Kennedy 2002).Assume that there was a cornfield model on the plane, ,food s location, and birds randomly dispersed on the plane atthe beginning. In order to find the location of the food, theymoved according to the following , we assume that position coordinate of the cornfieldis (x0,y0), and position coordinate and velocity coordinate ofindividual bird are (x,y) and (vx,vy), respectively.

6 Distancebetween the current position and cornfield is used to distance to the cornfield , the better the performance, onthe contrary, the performance is worse. Assume that each birdhas the memory ability and can memorize the best positionit ever reached, denoted velocity adjustingconstant,randdenotes a random number in [0,1], change inthe velocity item can be set according to the following rules:ifx>pbestx,vx=vx rand a, otherwise,vx=vx+rand >pbesty,vy=vy rand a, otherwise,vy=vy+rand assume that the swarm can communicate in someway, and each individual is able to know and memorize thebest location (marked asgbest) the velocity adjusting constant; then, after the veloc-ity item was adjusted according to above rules, it must alsoupdate according to the following rules:ifx>gbestx,vx=vx rand b, otherwise,vx=vx+rand >gbesty,vy=vy rand b, otherwise,vy=vy+rand simulation results show that whena/bis rel-atively large, all individuals will gather to the cornfield quickly.

7 On the contrary, ifa/bis small, the particles willgather around the cornfield unsteadily and slowly. Throughthis simple simulation, it can be found that the swarm can findthe optimal point quickly. Inspired by this model, Kennedyand Eberhart devised an evolutionary optimization algo-rithm, after a sea of trials and errors, they finally fixed thebasic algorithm as follows:vx=vx+2 rand (pbestx x)+2 rand (gbestx x)x=x+vx(1)They abstracted each individual to be a Particle without massand volume, with only velocity and position, so they calledthis algorithm Particle swarm optimization algorithm. On this basis, PSO algorithm can be summarized as fol-lows: PSO algorithm is a kind of searching process basedon swarm , in which each individual is called a particledefined as a potential solution of the optimized problem inD-dimensional search space, and it can memorize the opti-mal position of the swarm and that of its own, as well as thevelocity.

8 In each generation, the particles information is com-binedtogethertoadjustthevelocityofea chdimension,whichis used to compute the new position of the Particle . Particleschangetheirstatesconstantlyinth emulti-dimensionalsearchspace, until they reach balance or optimal state, or beyondthe calculating limits. Unique connection among differentdimensions of the problem space is introduced via the objec-tive functions. Many empirical evidences have showed thatthis algorithm is an effective optimization tool. Flowchart ofthe PSO algorithm is shown in following gives a relatively complete presentationof the PSO algorithm. In the continuous space coordi-nate system, mathematically, the PSO can be described123 Particle swarm optimization algorithm: an overviewStartSwarm initializationParticle fitness evaluatingCalculating the individual historical optimal positionCalculating the swarm historical optimal positionUpdating Particle velocity andposition according to the velocityand position updating equationSatisfying theending condition?

9 EndNoYesFig. 1 Flowchart of the Particle swarm optimization algorithmas follows. Assume that swarm size isN, each parti-cle s position vector inD-dimensional space isXi=(xi1,xi2, ,xid, ,xiD), velocity vector isVi=(vi1,vi2, ,vid, ,viD), individual s optimal position ( ,the optimal position that the Particle has experienced)isPi=(pi1,pi2, ,pid, ,piD), swarm s optimalposition ( , the optimal position that any individual inthis swarm has experienced) is represented asPg=(pg1,pg2, ,pgd, ,pgD). Without loss of generality,taking the minimizing problem as the example, in the initialversion of the PSO algorithm, update formula of the individ-ual s optimal position is:pdi,t+1={xdi,t+1,iff(Xi,t+1)<f(Pi,t)p di,t,otherwise(2)The swarm s optimal position is that of all the individual soptimal positions. Update formula of velocity and positionis denoted as follows, respectively:vdi,t+1=vdi,t+c1 rand (pdi,t xdi,t)+c2 rand (pdg,t xdi,t)(3)xdi,t+1=xdi,t+vdi,t+1(4)Since the initial version of PSO was not very effectivein optimization problem, a modified PSO algorithm (Shiand Eberhart 1998) appeared soon after the initial algorithmwas proposed.}

10 Inertia weight was introduced to the velocityupdateformula,andthenewvelocityu pdateformulabecame:vdi,t+1= vdi,t+c1 rand (pdi,t xdi,t)+c2 rand (pdg,t xdi,t)(5)Although this modified algorithm has almost the samecomplexity as the initial version, it has greatly improvedthe algorithm performance; therefore, it has achieved exten-sive applications. Generally, the modified algorithm is calledcanonical PSO algorithm, and the initial version is calledoriginal PSO analyzing the convergence behavior of the PSO algo-rithm,Clerc and Kennedy(2002) introduced a variant of thePSO algorithm with constriction factor which ensured theconvergence and improved the convergence rate. Then, thevelocity update formula became:vdi,t+1= (vdi,t+ 1 rand (pdi,t xdi,t)+ 2 rand (pdg,t xdi,t))(6)Obviously, there is no essential difference between theiteration formulas (5) and (6).