粒子群算法研究

Swarm SwarmIn ligence(SI)的概念最早由Beni、 Bonabeau、Dorigo和Theraulaz在他们的著作《SwarmIn ligence:FromNaturaltoArtificialSystems中对群智能进行了详细的论Swarm ligence(续S可被描述为一些互作邻集合，蜂群、蚁群、鸟群都的典型例子。鱼成个之间能简单加所得的社会性动物群体所拥有的这种性能助很好适应环境，所能获得的信远比通过身感所取得的多，其根本原因于之间在着息交互能力。Swarm ligence(续信息的交互过程不仅仅在群体内了信息，而且群内还能处理信息，并根据所获得的信息出了智能。因此，Bonabeau将SI的定义进一步推广为：无智能或简单智能的主体通过的聚 Swarm ligence(续JamesKennedy和RussellC.Eberhart在2001年出版了《SwarmInligence》，是群智能发展的一个 的定义，赞同由MarkMillonas（1994）构建Swarm ligence(续 ProximityPrinciple:群内具有能执行简单 QualityPrinciple:群内能对环境（包括群内其它） PrincipleofDiverseResponse群内不同 StabilityPrinciple不是每次环境的变化都会导 AdaptabilityPrinciple环境所发生的变化中，Swarm 《SwarmIn Mindissocial，也就是认为人的智能是源于社会Swarm ligence(续SI的优化算法都是源于对动物社会通过协作解决问题行为的模拟，它主要强调对社会系统中之间相互协同作EEEC一样的是，SI的目的并不是为了忠实地模拟自然现象，而是利用他们的某些特点去解决实际问题。另一个与E的相同点是,SI的优化算法也是概率搜索算法。Swarm ligence(续Swarm ligence(续等)的融合还不足。蚁群算蚁群算法（AntColonyOptimization,ACO）由又采取不同路线回到巢中，那么比较绕弯的一条蚁蚁群算法(续其它群智能优化算目前，还有一些不成群智能优化算法，2003年、邵之江等鱼群算法，食行为，主要利用鱼的觅食、聚群和追为构造底层行为；通过鱼群中各的局部的。在基本运算中引入鱼群的生存机制、竞争率。其它群智能优化算法（续优化问题简PSO算法简(paticlesmimizin，PSO)由Kenn和Eberhart在1995年提出，该算法模SInligence的优化方法。同遗传算法类似，也一种基于群体叠代的，但并没有遗传算法用的交叉以及变异，而是粒子在解空间追随最优的粒子PS有深刻的智能背景，既适合科学研究，又特别适合工程应用，并且没有许多参数需要调整。JamesKennedyreceivedthePh.D.degreefromtheUniversityofNorthCarolina,ChapelHill,in1992.HeiswiththeU.S.DepartmentofLabor,Washington,DC.HeisaSocialPsychologistwhohasbeenworkingwiththeparticleswarmalgorithmsince1994.Hehaspublisheddozensofarticlesandchaptersonparticleswarmsandrelatedtopics,incomputerscienceandsocialsciencejournalsandproceedings.HeisacoauthorofSwarmInligence(SanMateo,CA:MorganKaufmann,2001),withR.C.EberhartandY.Shi,nowinitsthirdprinting.RussellC.Eberhart(M’88–SM’89–F’01)receivedthePh.D.degreeinelectricalengineeringfromKansasStateUniversity,Manhattan.HeistheChairandProfessorofElectricalandComputerEngineering,PurdueSchoolofEngineeringandTechnology, University–PurdueUniversitynapolis(IUPUI),napolis,IN.HeiscoeditorofNeuralNetworkPCTools(1990),coauthorofComputationalInligencePCTools(1996),coauthorofSwarmInligence(2001),ComputationalInligence:ConceptstoImplementations(2004).Hehaspublishedover120technicalpapers.Dr.EberhartwasawardedtheIEEEThirdMilleniumMedal.In2002,hebecameaFellowoftheAmericanInstituteforMedicalandBiologicalEngineering.近年PSO方面文献的数22220 PSO产生背景之一：复杂适应系CAS理论的最基本的思想可以概述如下我们把系统中的成员称为具有适应性的主体(AdaiveAgt，简称为主体。所谓具有适应在这种交流的过程中“学习”或“积累经验”，并且根据学到的经验改变自身的结构和行为方式整个系统的演变或进化，包括新层次的产生，分化和多样性的出现，新的、聚合而成的、更大的主体的出现等等，都是在这个基础上出现的。复杂适应系统（CAS）CAS的四个基本特点首先，主体(AdaptiveAgent)是主动的、活的实体其次，与环境(包括之间)的相互影响，相PSO产生背景之二:工系统 ①研究如何利用计算技术物现象(Nature多源于生物现象的计算技巧，例如,人工神经网络是简化的大脑模型.遗传算法是模拟 基本PSO算真的群体行为，鸟成群地在空中飞行，当遇到时它们会分开绕行而过，随后又会重新形成基本PSO算法（续仿真研究，而并未将它用于优化计算中。Kenn和Eberhar在中加入了一个特来寻找食物。他们的初衷是希望通过这种模型来模拟鸟群寻找食源的现象，然而实验结果却尤其是在空间寻优中。基基本PSO算法(续PSO初始化为一群随机粒子。然后通过叠代找到最优解。在每一次叠代中，粒子通过两个"极值"这个解叫做极值pBest.另一个极值是整个种群目PSO算法数学表示如下Di个粒子Xi=(xi,xi,…,xiDi个粒子“飞行”历史中的过去最优位置（即该位置对应解最优）为Pi=(pi,pi,…,piD，其中PPi(i=1,…,n)中的最优；第i个粒子的位置变率（速度）为向量Vi=(vi1vi2viD)。每个行vid

wvid(t)

rand()[pid(t)

xid

rand()[pgd(t)

xid(t)] (t1) (t)

(t

1i 1d其中，C1,C2为正常数，称为加速因子；rand()为[0，1]之间d（1≤d≤D）维的位置变化范围为[-XMAXdXMAXd]，速度变化范围为[-VMAXd,VMAXd]，迭代中若位置和速度超过边界(Global)分成若干个有部分粒子的相邻PSO与EC的异它在生物体的每一代之间；而PSO模拟的是社（Meme），这一词由Dawkin在《The本单位，在社会中会根据环境来改变自身的思想，Meme的途径是在与之间，在实计算机、计算机与计算机之间。PSOPSO与EC的异同（续其次，EC中强调“适者生存”，不好的不好的通过学习向好的方向转变，不好的被保留还可以增强群体的多样性。EC中最好的通过产生的后代来自己的，而PSO中的最佳通过吸引其它向它靠近来自己的敏因。而PSO中的除了有着位置和速度外，还有着过去的历史信息（pBest、gBest），也就是具有E作组成，而PSO在某种程度上看，PSst和st似于3个父代：Xi、gBest和pBest的之间重组变异是有偏好的，而并非通常的完全随EC和PS所分别模拟的两个伟大的自然随EvlinMid差异，尽管它们都是基于群体的，都是由其PSE中。ParticleSwarm研究热IEEETRANSACTIONONEVOLUTIONARYCOMPUTION于2004年了第3卷：SPECIALISSUEONPSO。RussellC.EberhartYuhui在卷首语中了当前PSO研究的几个主要方向及粒子运动轨迹的分一维的，分别用12表示式（2.5）中的c1和c2rand()，仅研究粒子群中的某一个粒子ivi

wvi(t)

1)

粒粒子运动轨迹的分析（续将式（3.1）和（3.2）递推可得到

2)

w1)vi

1)wv(t)

xi(t2)(1w12)xi(t1)wxi(t)1

2

各项系数均为正值，于是可得到差分方（3.4）稳定的条件为（取某一个条件1w 2w2

当满足4）由vi

1)

(z))

1w

2w2 xi

1)Xi

这说明，在不考虑随机量且pBest、gBest置不变的假设下，当满足式（3.25）中时，单个粒子的位置将趋

112图3.1协同合作，因此其变化是不可忽视的。这子本身的运动过程还存在着弱反馈关系，那么式6）所给出的粒子最终位置是否仅是一种理想状态的？是否能上是不肯定的。p

pi(t)

(xi(t))

f(pi

(t)

f(x

(t))

f(

p(t1) iff

f(pi

fpg(t

f(

f(pg(t))

f若f(x)不是2.2.3节（NFL定理）中所说的函数f(pi(t)),f(Pg(t))和烈，随后pi(t),pg(t)将逐步近某个值，而f(pi(t)),

pi(t)2

pg

12粒粒子运动轨迹的分析（续sBs

pi(t)2

pg(t))

12

pg(t)粒粒子运动轨迹的分析（续为便于分析，式（3.22）中初始x(0

，并对也取Z变换可得到 Xi(z)

(

1

w)z

不考 之间存在的弱反关系Pi(所示

0i(z)对应的系统如图由仿真实例可以看出，当PSO参数不满足（3.25）的条件时，粒子的运动轨迹也收敛

pi(t)2

pg

1

；而当PSO数满足式（3.25）的条件时，粒子的运敛到一个固定点并不完全遵照式（5）所粒子运动轨迹的分析（续(12(12 2w212

粒子运动轨迹的分析（续粒子运动轨迹的分析（续PSO算法收敛性分随机算法收敛的

A,

代的结果XK，下一次迭代的结果为xk+1 是算法D条件

(D(x,))

f(

有f(D(x, PSOPSO算法收敛性分条件H2：

B

s.t.v[B]

，有 (1uk[B，有 k其中uk

为算法第k次迭代的结果在集合B上的概率度。算法满足条件H2意味着，A中任意满

v[B0的集B，算法D连续无穷次未搜索到A中点的几率为0。R

A，那么满足条件的算法连续无穷次搜索不近似全局最优点的概率为0条件H3：

L0{xA

为紧集(0,1，s.t

xL0，有[D(x,uk([dist(D(x,),Rε,M)dist(x,Rε,M) )Rε,M[D(x,}}是算法D产生数列，则有lim

{kP[k

k算法满足条件

}

法D k生数列，则有

k

Rε,M]定义3.1（粒子状态和粒子状态空间）粒子的位置x，速度vO

(x,

p)|

p

f(p)

f(x),v[vmin,vmax简称粒子空间,ON定义3.2（粒子群状态和粒子群状态空间,ONSO1,O2

。所有可能的粒子群状态的集合构成子群状态空

S

,ON

O(1i

N 定义3.3（粒子群等价）对于S N(S,O)

O(Oi

，其中A

表示事件A示性函数

表示粒子群状态中包含子状态的数目。若有两个粒子群S1S2S对于O

，若有

(S2,O)，则称和S2等价，记作～定理3.3“～”是S上的等价关系 L

(N|O|N

(N)!(|O

定理3.13在数字计算机实现的标准PSO算中，粒子群状态序Markov链

{S(t);t

是有限齐定理3.14在数字计算机实现的标准PSO算中，粒子群等价类状态序{L(t);t次Markov链

0}是有限定义3.19（最优粒子状态集）设优化题A,

的全局最优解

g*，定义粒最优状态集M

(x,v,p)

f(p)

f(g*OO}定义3.20（最优粒子群状态集）设优问题A,

的全局最优解为

，定义最粒子群状态

G

,ON|OiM,1iN}定理3.17PSO算法中，对粒子群状态序列{S(t);t0}而言，最优粒子群状态集合G定理3.19GS时，状态空间S中至G存在一个G之外的闭GB

S,

PSO算法的收敛性分析（续GGSBPSO算法收敛性分定理3.20

S时，PSO3.21当

G

PSO理论分析的其它可能方学还很少，本文了两个新的分析分析方法和呢？根据对其它随机算法讨对其它可能的分析方法和作简单的。随机过程中的其它方MarkovPS算法做分析。但如果独立分析粒子群的Markov是否可以采用随机过程中的其它方法直接对进行分析呢？例如，可以把粒子的运动看成一个随量，它的变化都有着一定的确定性，也存在着一定的不确定性，能否用熵或相对熵来描述粒子运动离散分布的不确定性的大小，从而对算法的收敛率做分析呢？随机过程中的其它可能方法（续PS个序列，因此可利用鞅收敛定理就可对算法的收敛性进行分析。同时也可以看到，要保证算法的收敛，有两个参数很重要：一个是过程进入满意解之后下一步脱离满意解的可能性；另一个是未进入满意解时下一步仍不能进入满意解的可能性。利用这种方法得到结果可能直观而且简练，也许对如何改进PSO算有重要指导意义基于混沌动力学理一个好的PS系统既非稳定态也非混沌态，而统。从系统工程的角度而言，PS应该是一个连续的非线性动态系统，因此将复杂系统PS途的。基于混沌动力学理论（续动力学理论来描述粒子群系统也存在一些，如何定义PSO系统中的吸、轨道、分叉和稳地系统的稳定性，而且系统的稳定性与优化Atotalnumberofncirculardisheswithuniformthicknessandmassdistributionwillbelocatedonacircularbearingplatewitha showninFig.1.Supposeriandmi(i∈I)aretheandmassoftheidish,

Fig1.SchematicLayoutThebasicproblemistofindthepositionofeachdishsothatallthedishescanhighlyconcentratetothecenterofthebearingplatewhilethefollowingconditionsexist.(a)Nooverlapexistsbetweenanytwodishes.(b)Nodishprotrudesoutofthebearingplate.(c)Thestaticequilibriumerrorofthewholesystemshouldnotexceedapermissiblevalue[δj].SupposethattheCartesiancoordinatesystemcoincideswiththesymmetricaxisofthebearingplateandXi=(xi,yi)isthecentroidoftheithdish.Thenthemathematicalmodeloftheaboveproblemcanbedescribedasthefollowing.x2x2y2ii

F(Xi

i

S.t.①Nooverlapexistsbetweenanytwof1(X

)

rj

i

j;

j

(xx)2(yy)2(xx)2(yy)2ijijx2y2iif2x2y2ii

R

i

③Thestaticequilibrium( nmx ( nmx n2i my2i

[J]

ParticleSwarmOptimizationwithMutationOperatorThispaperintroducesamutationoperatortobasicPSO,somethinglikeGA.IfthehistoricoptimalpositionPlkeepscontinuouslyunchangedorhaschangedextremelyalittle,inotherword,theparticleswarmaggregatesheavily,wewillkeepPlandre-randomseveraldimensionofparticlesaccordingtocertainprobabilitytoimproveglobalsearchingabilitywithoutdecreasingtheconvergentspeedandsearchaccuracy.ThepseudocodeofPSOwithmutationoperatorWhilek<MaxIterations&IfIfRe-randomthepositionandvelocityofseveraldataofeachparticlesaccordingtomutationprobabilityρ;UpdatethepositionandvelocityaccordingtoEq.(1)andEq.TestsuiteInthetestsuite,theradiusoftheroundcontainerisR,whichequalsto50mm,andthenumberoftheroundto-be-laidobjectsis7.Supposetheacceptablevalueofthestaticequilibriumerror,J,is[δJ=3.4g·mm],andtheotherdataoftheto-be-laidobjectsandtheresultofthelayoutisshowninTABLE1.TABLE1RESULTSOFLAYOUTSCHEMEFORTESTSUITInitiallayoutLayoutschemebyHCIGALayoutschemeByPSO1234567(a)LayoutPatternby (b)LayoutPatternbyTABLE2COMPARISONOFLAYOUTSCHEMESFORTESTSUITRefRadiusoftheoutwarpcircleStaticequilibriumerror000ComputationtimePs:Thecomputationtimeisconvertedintothetimeofthecomputerwith166Mmainfrequency,byusingPSO,whenthecalculatedradiusoftheoutwrapcircleis32.66,thecomputationtimeis760RepeatthetestsuitbyPSOfor40times,andtheresultsareshownasTABLE3,thatis,everytimetheresultallsatisfiestherestrictconditions,andthemeanradiusoftheoutwrapcircleis32.49mm.TABLE3RESULTSOF40TIMESCOMPUTATIONFORTESTSUITRadiusofthewarpcircle(32.3,(32.5,52Radiusofthewarpcircle(32.9,223TestSuitInordertoprovetheavailabilityofPSOfurther,theknownmostoptimalsolutioninthetestsuitof[8]isquoted.Inthebigroundcontainer,ofwhichtheradiusisR=125mm,fiveto-be-laidobjectsarelaidout.Thedataoftheto-be-laidobjectsandtheresultofthelayoutareshowninTABLE6.(In[8],thepopulationsizeofGA,M,is60,whileinthispaper,thenumberofthePSOparticles,M,is60,andthepopulationsizeofneighborhoodis2,andc1=c2=1.49,andw=0.729,andthe numberofiterationis200.)Table6RESULTSOFLAYOUTSCHEMEFORTESTSUIT(Known12345(a)(b)Layout(c)LayoutLayoutbybyTable7COMPARISONOFLAYOUTSCHEMESFORTESTSUITRadiusoftheoutwarpcircleStaticequilibriumerrorInterference000ComputationLayoutPatternoftheglobaloptimaandusuallocaloptimaofshowinFig2,ifλ1=1,λ2=1,λ3=0.01.Fig2LayoutPatternoftheglobaloptimaandusuallocalTomeasuretheeffectivenessandviabilityofPSOwithmutationoperator,resultsarecomparedwithbasiclocalPSOandMultiStartPSO.Themaxiterationis1000，sizeofpopulationis60,MaxStep=10,ρ=20%and.ResultsarepresentedinTable7,50runsforeachalgorithm.带时间窗车辆路径问车辆路径问题(icletigProbl，VRP)zigs9年首次提出的，它是指对一系列发货点或收货点适当的行车路径，使车辆通过它们，NP问题，在运筹、计算带带时间窗车辆路径问题（续带时间窗的车辆路径问题(VehicleRoutingProblemWithTimeWindows,VRPTW)是在VRP问题上加了客户要求的时间窗口。由于在现实生活中许多遗传算法、搜索和模拟退火等智能化启发式算库，拥有车K辆，容量分别为qk(k=1,..,K)；现有L 个发货点的货运量为gi(i=1,…,L)，max(g)i≤max(qi，完成发货点i窗口[ETi,LTi]完成，其中ETi为任务i的允许最早 min

cij

pEmax(

si,0)

pLmax(

giykiqk i

yki

i1,,

ykjyki

j0,1,,L；ki0,1,,

X

(xijk)

xx

i,j0,1,,

yki

i0,1,,

带带时间窗车辆路径问题（续型。若(1中Ei=0,i→∞，则VRPTW模型就变成了普通的VRP模型；若仅有一个车辆TSP问题；若去(2mTSPTW问题。2LL个发货点任务的VRP问题，每个发货点任务对应两维：完成该任务的k，该任务k。为表达和计算方便，将每个粒子对应的2LX分成两个L维向量：Xv表示各任X。VRP7为3X为：发货点任务号1234567Xv1222233Xr1431221车1：0→1→0车2：04→532车3：076粒子速度向量V与之对应表示为Vv和Vr高，但由于PSO算法在寻优问题有着非粒子群划分成若干个两两相互的相邻子群将初始评价值作为历史最优解Pi，并寻找各子对每一个粒子，按式(1)Ｖ、Ｖr计算v、r，其中v若优于历史最优解则更新Pl、Pg。对于子群内有多同为最优值的情况，则随机取其中一个为子其中，评价函数Eval完成以下任务X值的大小顺序，由小到大执行。2、将X按执行顺序进行重新整数序规范。例：1222233：5则评价后重范的Xr是 表1各发货点坐标及货运01234567货运表2实验1GA、PSO方法结果对0实验2，采用VRPTW的例子，该问题有8项货物任务表 实验2GA、PSO方法结果对EvolvingEvolvingNeuralEvolveneuralnetworkcapableofbeinguniversalapproximator,suchasbackpropagationorradialbasisfunctionnetwork.Inbackpropagation,mostcommonPEtransferfunctionissigmoidalfunction:output=1/(1+e-input)PSOc sobeusedtoindirectlyevolvethestructureofanetwork.AnaddedbenefitisthatthepreprocessingofinputdataismadeEvolveboththenetworkweightsand slopesofsigmoidaltransferfunctionsofhiddenandoutputPEs.Iftransferfunctionnowis:output=1/(1+e-k*input)thenweareevo