Common model analysis and improvement of particle swarm optimizer

Joumnal of Control Theory and Applications 2007 5(3) 233 -238DOI 10.1007/s1 1768-006-6132-xCommon model analysis and improvement ofparticle swarm optimizerFeng PAN, Jie CHEN, Minggang GAN, Guanghui WANG, Tao CAI(School of Information Science Technology, Beijing Institute of Technology, Beijing 100081, China)Abstract: Particle swarm optimizer (PSO), a new evolutionary computation algorithm, exhibits good performancefor optimization problems, although PSO can not guarantee convergence of a global minimum, even a local minimum.However, there are some adjustable parameters and restrictive conditions which can affect performance of the algorithm.[n this paper, the algorithm are analyzed as a time-varying dynamic system, and the sufcient conditions for asymptoticstability of acceleration factors, increment of acceleration factors and inertia weight are deduced. The value of the inertiaweight is enhanced to (-1, 1). Based on the deduced principle of acceleration factors, a new adaptive PSO algorithm-harmonious PSO (HPSO) is proposed. Furthermore it is proved that HPSO is a global search algorithm. In the experiments,HPSO are used to the model identification of a linear motor driving servo system. An Akaike information criteria basedfitness function is designed and the algorithms can not only estimate the parameters, but also determine the order of themodel simultaneously. The results demonstrate the efectiveness of HPSO.Keywords: Particle swarm optimizer; Asymptotic stability; Global convergence; System identification; Akaike infor-mation criteria1 Introductionby the swarm information pga and its own informationpla.Particle swarm optimizer (PSO) algorithm is aIn this paper, the standard PSO algorithm is analyzed as apopulation-based parallel optimization technique [1], which discrete dynamic system. Sufficient conditions for asymp-exhibits good performance for optimization problems. totic stability are deduccd. On the basis of the analysis,There are some adjustable parameters, such as the inertia a new adaptive PSO algorithm, HPSO, is proposed andweight, acceleration factor, scaled factor, and so on, which proved to be a global search algorithm. Futhermore, com-greatly infuence the convergence performance and stabil- bined with HPSO, a new synthetic method for system iden-ity of the algorithm. Some papers [2~4] about the stability tification, which accomplishes the order selection and pa-analysis have been published with many proposed methods. rameters estimation simultaneously, is applied to a servoAt time k + 1, the update equations of the i-th particle in system. Experiments demonstrate the efctiveness.the d-th dimension search space of the standard PSO algo-2 Stability analysis of PSOrithm are defined as follows:Adjustable parameters of PSO are always tuned empini-嘴1= w0 + C1rpa(pgd -馏) + C2rid(哈-站), (1)cally. The state equations of particles are simplified and an-1物+1=嗡+ moa+1,(2alyzed as a constant coefficient dynamic system [2]. In thiswhich satisfies |u嘴|≤Vmax. where w0 is the inertia weight, section, the suffcient asymptotic stability conditions with-指is the current position of the particle, 哈is the veloc- out Lipschitz condition constrains for acceleration factor 中ity vector,嘴is the personal best position of the particle, and inertia weight w are deduced. First, a lemma is intro-is the swarm best position among all particles, C1 and duced [5].C2 are acceleration factors, respectively, rid and r'gd are ran-Lemma 1 Given time-varying discrete dynamic sys-dom poumbers in the range [0, 1]. As an upper bound of the termns as below:velocity vector in every epoch, Vmaxcan be presented as thex(n + 1)= A(n)x(n).Lipschitz condition of particles dynamic systems.The sufficient condition for asymptotic stability of the|脂1-哈| < Vmax.(3) discrete-time system is that there existIn the search space, the particles“fly" to the target guided中国煤化工4Received 26 July 2006; revised 3 April 2007.YHCNMHGThis work was supported by the Teaching and Rescarch Award Program for Outstanding Young Teacher in Higher Education Instiute of Ministry ofEducation of China (NO. 20010248).234F PAN et al. /Journal of Control Theory and Applications 2007 5(3) 233 -238satistfyingBased on Jury criterion, the sufcient conditionofp(.)< 1p(T(k,k- M))<1,where(mw)2 <1,(9)T(,k-M)=I A(k-i)1 |2rw- L*(1 +ru) + L*np*+1<1+ (mu).问1is the transfer matnix, ρ is the spectral radius andBy calculation, w∈(-1/n, 1/n) satisfying (9) and alsop(T(k,k- M) = max{|\l;i∈n}<1.-np*(1 + mw)≤p+1.Based on Lemma I, Theorem 1 can be deduced.1+mw-npkTheorem 1 The sufcient condition for asymptotic sta-。2(1 + (qu)2)- rp*(1 + mu)bility of PSO algorithm is that: the acceleration factor1+nw-npknpk+1 and inertia weight ηw satisfying the following con-This completes the proof.ditions:At time k + 1, the acleration factor npk + ' and inertianmw∈(-1,1);(4)weight w should meet (4), (5) l0 ensure asymptotic stabil-{πp+1∈U|U C (nt1, ptt)}(5) ity, At a certain moment, if the value range of nηpk+1 sat-andisfies rp*+1∈[UInpmx; mpmin1}, the movement of par--η4*(1 + mw)ticle dynamic system tends to asymptoically stablc; Oth-1+nw-nerwise, the system will diverge. Generally speaking, we canpk+1 =2(1 + (7w)2)- ηp*(1 + nw)assume the initial conditions is that w lake a value in(-1,1)1+mw- ηpand ny° is betwecn (0, 4), then the upper and lower boundProof The standard PSO algoithm can be expressed as curves of nph+1 are potted in Fig.1 and Fig.2.(1 + mw-np*+1) -pu20001500000 t(6)00上0fwhere acceleration factor-50(ψ*+1=p+1+qe+I,-1000-150p:+l=c;Xri,-2000and input vector is2500pf+1.嗜++-p管-0.50.5 1pk+1The transfer matrix of (6) isFig. 1 Range curve of npm故.T(k,k-2)1+mw-np* -nw |「1 + mw-npk+1 -ηw |1000o」500From Lemma 1, if the conditionp(T(k,k- 2)) = max()\i|)< 1- 1000is satisfed, the system described by (6) is asymptoticallystable.|λ- L*Ik+1 + mw nwLk).5|\E -T(k,k -2)1= _τλ+rpw|,(7)0-1-00中国煤化工where Lk = (1 + mw - mpk). The characteristic equation_Pnin "of (7) is described as.JHCN M H Gion for asympotic staD(A)=λ2 + A\2rw- L*(1十mw)+ L*ηp+t]bility of PSO algorithm is that the increment of aceleration+(nw)”,(8) factor nOph and inertia weight nw satisfying the fllwingF PAN et al. /Joumal of Control Theory and Applications 2007 5(3) 233- -238235conditions:this papet.w∈(-1.1),At every epoch, according to the current value of acceler-{nOp°∈UU C [Omin, Omux]}(10) ation factor at time k and swarm states can be adjusted dy-namically. If expansion condition is met, the value of np*+1will be out of the range of 10, so every the particle system is0min=(1 +nw-n3们)2-(1 + mu)2unstable and the swarm system will be extended to a wider1 + 7W- mphtspace. On the other hand, the value of ηp'k+1 will be withinImas_(1+qw-np*)2+(1 - nw)2.the stability region, when one of the particle find a promis-1 + nmu- noking solution and need others shrink for further research inProof The acleraion factor rγp° +1 can be xressed local area. Based on chosing a dferent value for the nextastime, it is simple to control the convergence or divergence ofηpk+1 = nxp* + n0qp*.(11) the swarm. The swarm expands and shrinks continuously, s0Taking into acount the sability condition of ηph+1 from that we can search the solution space repeatedly. The logicalTheorem l,flow of HPSO is-np*(1 + muc).≤nyp*+1Step 1 Create and initialize a PSO swarm.1+mw-ηpkStep 2 Evaluate each particle in the swarm.2(1 + (mw)2)- mp*(1 + nw)(12)Step 3 If the available time has expired, or reach the1+nw-nphtermination, return the best solution, if not, go to Step 4.This completes the proof.Step 4 If the consecutive failure times exceed CFmaxBy sbracing nrp on each side of (12), we deduced the or DVwrm < DVmim. update particles based on (4) andsability condition of ηAφpk as follow:(5), to expand the swarm, else if DVswarm > DVmin, shrinkthe swarm.(1 +nw-np)2-(1 + rw)2Step 5 Update particles given by (4) and (5) to shrink1 + npw- nηpthe swarm. Go to Step 2.≤Oηp°≤(1+ nw- np*)2+(1 - rnw)2In the above flow, the term CFmax is the upper bound1 +ηpw - npkThe ange of nAo* are ploted in Fig3, when w ake a of cosecuive filurle times, where .he filure means thecurrent fitness is worse than the previous best fitness of thevalue in (-1, 1) and ηpk is between (0, 4).swarm. DVswarm = E Ddeviacion(Sswarm) is defined as thesum of swarm variance, and DVmax denotes the variance ofsearching space.603.2 Global convergence proof of HPSO5040Solis and Wets [6] provided some conditions and results30for the global convergence of random search algorithms as200 |follows.10H1) f(D(x,ξ)) ≤f(x) andifξ∈S", f(D(x,E))≤f(E), where ξk is generated from sample space (R"; B, uk); .xgh+1 = D(xk, ξ*),D:Snx Rn→sn; sn is a subset of0.5R"; B is the σ -algebra of the subset of R"; k is the prob-094)01ability measure.H2) For any (Borel) subset A of sn with v(A) > 0,Fig. 3 Range of nOqk.there existsiI [1- pe(A) = 0, where v is a negative3 Harmonious PSO and its global conver- measure defined on B, generally is Lebesgure measure.genceLemma 2 (Global search) Suppose that f is a measur-3.1 A kind of adaptive PSO - haronious partiele able fnction, sn is a measrable sbst ofR", HI) andswarm optimizer中国煤化工equence generated bySimilar to GA and other evolutionary computing tech-the aYHCNMHGniques, PSO is facing a dilemma between rapid searchinglim H[x^ ∈le,M」=l,and premature convergence. According to the analysis re-sult of Theorem 1, a kind of adaptive PSO is proposed in where P[xk∈Re,M] is the probability at step k and the236F PAN et al. / Joumal of Control Theory and Applications 2007 5(3) 233 -238point x is generated by the algorithm in the optimality gyroscope (sce Fig.5) and the sampling period is 1.5 ms.region. It has been proved that PSO does not satisfy H2)and Lemma 2 [3]. In this paper, a convergence property ofHPSO is studied. Without Lipschitz constrain condition, (1)and (2) of the standard PSO can be represented as嘴+1≈w.啮+φ+1.(p-嘴1),(13)x路+1=箱+ noa+1,(14)where p is a hypercube whose vertexes are嘴and pgd.From the above, we have Theorem 3.Theorem3 HPSO is a global search algorithm.Proof D function of HPSO is defined below [3]:D(点临《哈%≤(脂) (5)[嘘f(啮)> f(啮).Fig. 4 The servo system driven by a linear motor.It is clear that (15) satisfies HI). At time k, the support M$108。of the i-th particle is defined asM+1 =蹈+ nw点+ nph+1(p-蹈)，4t Iwhere Mk+1 is a hyper sphere whose center is啦and ra-| (idiusisp:+1 = mwra + npk (p - x啪). For HPSO, searchingis a process of the“Shrink Expand Shrink" course. More-2- |over, according to Lemma 1, there is no restriction on thenph+1 value, especially, if the swarm is in an expandingstatus. So the range of ρ: +1 has no limiation theoretically.-1If only the following condition is met:mpk+1≥|Sax; Sminll2 - rmwo(16)-120.00.40.8 1.20.0 0.40.8 1.2l/st1(p-嘴)then隆≥|ISmax: Sminl2, where Sx and Smin areFig, 5 Response of pseudo random signal.the upper and lower bound of searching space Sn, sepa-The model identification of the system velocity loop isrately. If nph+1 meets (16), then Sn C Mg, furthermore, based on the input-output data. The autoregressive movings"c∪M5(∪M∩S)= u(S). sovAC s", avage(ARMA)(.) modelis aoped as belwi(2)=-它aky(n-i)+之bru(n-I). (17i [1 - ue(A)j = 0 and H2) are stisfied.According to Lemma 2, HPSO is a global search algo-In the common way, first of all, order selection methods,such as AIC, FPE, MDL, CAT, SVD, etc. are used to deter-rithm.mine the model order p and q. Then, numerical estimationmethods, such as LS, LMS, ML, etc. are used to estimate the4 Experimentsparameters. They are two separate parts of the model iden-4.1 Backgroundtification. These two steps usually bave to be repeated manyIn this section, it is focused on a servo plaform di-times to venify the results. In this paper, a new identifca-rectly driven by linear motor on the vertical directiontion method, based on HPSO and a specific fitness function,[7] (sece Fig.4). With this configuration, all mechanical accomplishes these two parts simultaneously. Furthemore,transmissions, such as ballead screws, rack & pinions,results of the new method are verified by F-test. Descriptionblspuleys, and gearboxes are eliminated. In tum it elim- of the experiments is given below.inates backlash and compliance and other problems associ-4.2 Fitness function designated with these mechanical transmissions. The identifcationproblem is studied in this part. The input of the system is a中国煤化工AIC citeria (as (18)4 order peudo-random signal. The level time is 40 ms and showrtMYH，CNMHG+g)Nprithms.periodic is 15, amplitude is 7.5 V, which is equivalent to af(o,p,q)=NT-(o+q)IN'(18)18.75 mm/s velocity command to the linear motor. The rota-tional velocity signal of the platform is measured by the rateThe parameter estimation and order selection can be eval-F: PAN et al. /Journal of Control Theory and Applications 2007 5(3) 233-238237uated by this fitness function, whereσ2= (y - 4(y, u)X)2is the sum of the eror squares, N is the data size, X and Yrepresent input and output vectors, respectively.10'Y=[y(k) y(k-1) ... y(p)]T,X=[a1... ap b1... bq]T,4(y, u)10[u(k-1)... y(k-p) u(k) ... u(k-g)(y(k-2)..y(k-p-1)u(k-1)-.u(k-q-1)(19)102y(1) u(q-1)... u(1)」Epoch4.3 Coded and dimensionFig 7 Fitness function.At time k, a particle vector is a three-part vector in any(m) - 1.778y(n- 1) + 0.7957 = 0.0191u(n), (20)(ni+ m + 2)-dimcnsion solution space, defined as ri =21400(21)(p,q, 1,2,. ,ain,bi1, b2,- ,bim). The first two rows2 + 228.5s + 19830elements are the order part; the others are the parametersThe curve corresponding to PSO (the dotted line) almostof the autoregressive aid and moving average bid parts. Thecompletely coincides with the dashed line of response data.parameter m and n are larger than P and q, so as to provideThe error curve is drawn in Fig.3. It is clear that the conver-redundancy variable of model. Here, the update rule for thegence speeds of HPSO are not high enough at the beginningmodel order part (P and q), is that, within the value limit,of optimization, but can keep going until the optimizationtheir values are rounded to the nearest integer at cach itera-goal has been satisfied. The reason is that the HPSO willtion. The upper limit of the model order p and q is separatelyrepeat the“Expand-Shrink" process, but not shrink only.chosen to be 5 and the lower limit is 1.HPSO can guarantee a harmonious relation of swarm di-4.4 Parameter setting for HPSOversity and keep searching, even if there is no new informa-The AIC citeia and LS algorithm are in general used tion itrduced. The swarm of the HPSO expands unil theand can work efecienly. Here, HPSO are used to estimate whole searching space is overlapped. This is the reason thatthe ARMA(p,g) model. The parameter values of HPSO are during the searching process, there are somne stagnation ofgiven in Table 1.the curve without performance improvement in Fig.7. AfterTable 1 Parameter sting for HPSO.that, the swarm shrinks to a lower limit. This process willrepeat till the terminal condition is met.Swarm size1:Inertia weight0.79In order to verify the results of order selection, F-test isDVmaxInitial acceleration factor 1.4adopted as (22) shown.Initial value[-1 1] DVmin(Jn-Jn+1)Jn+1Max generation100Scaled factor~F(Op,N-p-q), (22)△pN- p-qThe results estinated using AIC and HPSO is plotted inwhere p is order dfference, the length of data set isFig.6 and Fig.7. The order (p, q) estimated using the HPSON= 658, .is (2,1), the AIC of the HPSO 0.18971. Model can be ex-pressed as (16) and (17).degree of confidence is selected as15-a= 0.01.Results in Table 2 demonstrate ARMA(2,1) is more legiti-mate than the others, and the method combined with HPSOand AIC is proper.Table 2 Order determination by F-test.中国煤化工午Fa-10-60.4 6.8515LMYHCNMH G186 6.850.0 0.2 0.4 0.6 0.8 1.0 1.2ARMA(2,2) 0.1855 9.65976.85t/sARMA(3,2) 0.1828 4.2426 6.85Fig. 6 ldentification results.238F PAN et al. /Journal of Control Theory and Applications 2007 5(3) 233 -2385 ConclusionsJie CHEN received the B.S. degree, the M.S.degree and the Ph.D. degree in Control The-In this paper, the stability without Lipschitz constraint ofory and Control Engineering in 1986, 1993 andPSO parameters has been explored, the suficient conditions2000, respectively, from the Beijing Instituteof asymptotic stability have been obtained theoretically, theof Technology. From 1989 to 1990, he was amathematical relation between w and P is explored, the in-visiting scholar in Califomnia State University,ertia weight w value is enhanced to (-1,1). Furthermore,U.S.A. From 1996 to 1997, he was a Researchthe HPSO has been proposed, which can adaptively adjustFellow in School of E&E, the University ofBirmingham, U.K. He is crrently a profssorparameters and its global convergence has been proved, Inof Control Science and Enginecring. Beijing Istute of Technology, P.R.the experiment section, AIC criteria was introduced to de-China. His main research interests are complicatcd system muti-object opsign the ftmes function for system ieniticaion of a servo umizatin and desion, iln cntol, costrined nliner coutol,platform driven by a linear motor, which improve the op-optimization methods, etc. E-mail: chernjie@bit.edu.cn.timization ability of the HPSO that can achieve the modelorder selection and parameters estimation simultaneously.Minggang GAN reved the B.S. degree inReferencesControl Theory and Contol Engincering inl1] J. Kennedy, R. C. Eberhart. Particle swarm opimization[CW2002, from the Beijing Institute of Technol-Proceedings of IEEE lntermational Conference on Neural Nenworks.ogy in China. He is curenly a Ph.D. candidatePiscataway, New Jersey: IEEE Service Ceater, 1995: 1942 - 1948.of Pttem Recognition and lnelligent System2] M. Clerc, J. Kennedy. The particle swarm: explosion stubilityin Beijing Instiute of Technology. His mainand convergence in a muli dinensional complex space[J]. IEEEresearch is about elctromagnetic interferenceTransactions Evolution Computation. 2002, 6(|): 58 - 73.and compalibility of control system. His main(3] F. van den Bergh. An Analysis of Particle Swamn Optimizers[M].research aspects include artificial itelligence,South Africa: University of Prelorial, 2002.filter, shielding and system elctromagnetic interference sppression.[4] J. Chen, F. Pan, T. Cai, et al. The sabilily analysis of particleswarm optimization without Lipschitz condition constrain[J]. Journalof Control Theory and Applications, 2004, l(): 86- 90.Guanghui WANGreceived the B .S. degree5] Y. Xiao. Analysis of Dynamical Systems[M]. Beijing: Northemn Jiao-in electonic and information engineering inTong University Press, 2002.2005, form China University of Geosciences6] F. Solis, R. Wets. Minimization by random scearch techniques{J].(Bcjjng) in China. Now he is a M.S. can-Mathematics of Operations Research, 1981.60: 19 - 30.didate in Patterm Recognition and Ielligent[7] F Pan, J. Chen, M. Gan, et al. Model analysis of particle swarmSystem, in Beijing Institute of Technology inoptimizer{J]. Acta Automatica Sinica, 2006, 32(3): 368 - 377.China, His research areas incelude rtifcial in-[8] X. Zhang. Morden Sigral Processing[M]. Beijing: Tsinghuaelligence and computing ineligence.University Press, 1995.Feng PAN received the B.S. degree and Ph.D.Tao CAI received the B.S. degree and the M.S.degree in Pattern Recognition and Intellectualdegree in Control Theory and Contrul Engi-System from the Beijig Institute of Technol-neering in 1993 and 1999, respectively, fromogy in China. Now he is a lecturer in Beiingthe Beijing Institute of Technology in China.Institute of Technology. His currently researchHis main research focus on the ineligent con-interests include iteligent control, evolutiontrol, system engineering, nonlinear control andcomputation and atificial itelligence, elc. E-arificial itelligence, etc.mail: andropanfeng@ 126.com.中国煤化工MYHCNMHG