2004年5月第
6卷第5期
中国工程科学May.2004Vol16No15
综合述评
杨 维,(250061)
[摘要] (PSO)算法是一种新兴的优化技术,其思想来源于人工生命和演化计算理论。PSO通
。该算法简单易实现,可调参数少,已得到广泛研究和应用。详细介绍了PSO的基本原理、各种改进技术及其应用等,并对其未来的研究提出了一些建议。群体智能;演化算法;粒子群优化[关键词]
[中图分类号]TP30116 [文献标识码]A [文章编号]1009-1742(2004)05-0087-08
1 前言
从20世纪90年代初,就产生了模拟自然生物
群体(swarm)行为的优化技术。Dorigo等从生物进化的机理中受到启发,通过模拟蚂蚁的寻径行为,提出了蚁群优化方法;Eberhart和Kennedy于1995年提出的粒子群优化算法是基于对鸟群、鱼群的模拟。这些研究可以称为群体智能(swarmintelligence)。通常单个自然生物并不是智能的,但是整个生物群体却表现出处理复杂问题的能力,群体智能就是这些团体行为在人工智能问题中的应用。粒子群优化(PSO)最初是处理连续优化问题的,目前其应用已扩展到组合优化问题[1]。由于其简单、有效的特点,PSO已经得到了众多学者的重视和研究。
的控制之下,即复杂的全局行为是由简单规则的相互作用引起的。PSO即源于对鸟群捕食行为的研究,一群鸟在随机搜寻食物,如果这个区域里只有一块食物,那么找到食物的最简单有效的策略就是搜寻目前离食物最近的鸟的周围区域。PSO算法就是从这种模型中得到启示而产生的,并用于解决优化问题。另外,人们通常是以他们自己及他人的经验来作为决策的依据,这就构成了PSO的一个基本概念。
PSO求解优化问题时,问题的解对应于搜索空间中一只鸟的位置,称这些鸟为“粒子”(particle)或“主体”(agent)。每个粒子都有自己的位置和速度(决定飞行的方向和距离),还有一个由被优化函数决定的适应值。各个粒子记忆、追随当前的最优粒子,在解空间中搜索。每次迭代的过程不是完全随机的,如果找到较好解,将会以此为依据来寻找下一个解。
令PSO初始化为一群随机粒子(随机解),在每一次迭代中,粒子通过跟踪两个“极值”来更新自己:第一个就是粒子本身所找到的最好解,叫做个体极值点(用pbest表示其位置),全局版PSO中的另一个极值点是整个种群目前找到的最好解,
2 PSO基本原理
211 基本PSO原理
粒子群优化算法是基于群体的演化算法,其思想来源于人工生命和演化计算理论。Reynolds对鸟群飞行的研究发现,鸟仅仅是追踪它有限数量的邻居,但最终的整体结果是整个鸟群好像在一个中心
[收稿日期] 2003-08-05;修回日期 2003-09-08
[基金项目] “八六三”高技术资助项目(2001AA413420),山东省自然科学基金资助项目(2003G01)[作者简介] 杨 维(1978-),女(满族),山东济南市人,山东大学控制科学与工程学院硕士研究生
88中国工程科学第6卷
Step3粒子的更新 用式(1)和式(2)对每
称为全局极值点(用gbest表示其位置),而局部
版PSO不用整个种群而是用其中一部分作为粒子的邻居,所有邻居中的最好解就是局部极值点(用lbest表示其位置)。在找到这两个最好解后,粒子
一个粒子的速度和位置进行更新。
Step4检验是否符合结束条件 如果当前的迭
根据如下的式(1)和式(2)来更新自己的速度和位置。粒子i的信息可以用D维向量表示,位置表示为Xi=(xi1,xi2,...,xiD)T,速度为Vi=
(vi1,vi2,...,viD)T,其他向量类似。则速度和
代次数达到了预先设定的最大次数(或达到最小错误要求),则停止迭代,,否则转到Step2。
PSO2)类似于遗传算法(GA)PSO也是多点搜索。
3)式(1)的第一项对应多样化(diversification)的特点,第二项、第三项对应于搜索过程的集中化(intensification)特点,因此这个方法在多样化和集中化之间建立均衡[1]。
PSO有全局版和局部版两种,全局版收敛快,但有时会陷入局部最优。局部版PSO通过保持多个吸引子来避免早熟,假设每一个粒子在大小l的邻域内定义为一个集合
Ni={pbesti-l,pbesti-l+1,...,pbesti-1,pbesti,
pbesti+1,...,pbesti+l-1,pbesti+l}
(3)
位置更新方程为
vid
k+1
=vid+c1rand1(pbestidxc2rand2(xid)x1
k
kkkk
(1)(2)
xidvid
kk1
vkid是粒子i在第kd维的速度;c1,c2
是加速系数(或称学习因子),分别调节向全局最好粒子和个体最好粒子方向飞行的最大步长,若太小,则粒子可能远离目标区域,若太大则会导致突然向目标区域飞去,或飞过目标区域[2]。合适的
c1,c2可以加快收敛且不易陷入局部最优,通常
令c1=c2=2;rand1,2是[0,1]之间的随机数;
xid是粒子i在第k次迭代中第d维的当前位置;
k
pbestid是粒子i在第d维的个体极值点的位置(即
坐标);gbestd是整个群在第d维的全局极值点的位置。为防止粒子远离搜索空间,粒子的每一维速度vd都会被钳位在[-vdmax,+vdmax]之间,
vdmax太大,粒子将飞离最好解,太小将会陷入局
部最优[2]。假设将搜索空间的第d维定义为区间
[-xdmax,+xdmax],则通常vdmax=kxdmax,011
≤k≤110,每一维都用相同的设置方法。基本PSO的流程可以描述为:
Step1初始化 初始搜索点的位置X0i及其速
度V0i通常是在允许的范围内随机产生的,每个粒子的pbest坐标设置为其当前位置,且计算出其相应的个体极值(即个体极值点的适应度值),而全局极值(即全局极值点的适应度值)就是个体极值中最好的,记录该最好值的粒子序号,并将gbest设置为该最好粒子的当前位置。
Step2评价每一个粒子 计算粒子的适应度
从Ni中选出最好的,将其位置作为lbest代替公式
中的gbest,其他与全局版PSO相同。实验表明,局部版比全局版收敛慢,但不容易陷入局部最优[3]。在实际应用中,可以先用全局PSO找到大致的结果,再用局部PSO进行搜索。212 二进制PSO
最初的PSO是从解决连续优化问题发展起来的,Eberhart等又提出了PSO的离散二进制版,用来解决工程实际中的组合优化问题[4]。他们在提出的模型中将每一维xid和pbestid限制为1或者为0,而速度vid不作这种限制。用速度来更新位置时,如果vid高一些,粒子的位置xid更有可能选1,vid低一点则选0,阈值在[0,1]之间,而有这种特点的函数就是Sigmoid函数:
k
sig(vkid)=1/(1+exp(-vid))
(4)
二进制版本PSO的公式为
k+1k+1k+1ifρ
+1
else
xkid=0
值,如果好于该粒子当前的个体极值,则将pbest
设置为该粒子的位置,且更新个体极值。如果所有粒子的个体极值中最好的好于当前的全局极值,则将gbest设置为该粒子的位置,记录该粒子的序号,且更新全局极值。
(5)
k+1
向量ρid的各个分量是[0,1]之间的随机
数[1]。为了防止Sigmoid函数饱和,可以将vkid钳位在[-410,+410]之间。二进制PSO其他部分与基本连续PSO类似。实验结果显示,在大多
第5期杨 维等:粒子群优化算法综述
vid
k+1
89
k
k
k
k
数测试函数中,二进制PSO都比遗传算法速度快,尤其在问题的维数增加时。
213 解决混和整数非线性规划(MINLP)问题的
PSO
=wvid+c1rand1(pbestid-xid)+
c2rand2(gbestd-xid)
k
k
k
(6)
如果用离散数字来表达当前的位置和速度,或者在速度更新完成后对整数变量进行取整运算,则可以在算法中同时处理连续和离散变量。这就为解决MINLP等问题提供了广阔天地,文献[5]中已将解决MINLP的PSO制问题。
用惯性权重来控制前面的速度对当前速度的影
响,较大的w可以加强PSO的全局搜索能力,而较小的w[9]。基本的PSO可以看作1,力,1,112]之间PSO[10]中试验了将w设到014的线性下降,使得PSO在开始,较快地定位最优解的大致位置,随着w逐渐减小,粒子速度减慢,开始精细的局部搜索(这里w类似于模拟退火中的温度参数)。该方法加快了收敛速度,提高了PSO算法的性能。当待解问题很复杂时,该法使得PSO在迭代后期全局搜索能力不足,导致不能找到要求的最优解,这可以用自适应改变惯性权重来克服。31112 模糊惯性权重(fuzzyinertiaweight)法 Shi等提出用模糊控制器来动态自适应地改变惯性
3 PSO PSO与GA,两者都随机初始化种群,使用适应值来评价系统和进行一定的随机搜索。但PSO是根据自己的速度来决定搜索,没有GA的明显的交叉和变异。如果将pbest也看作是种群的成员,那么PSO也有一种很弱形式的选择[6]。速度更新方程中如果没有vkid项,可以解释为一种代数交叉,而对vkid更好的理解是把每次迭代看成是一种不断适应的过程。GA中染色体共享信息,故整个种群较均匀地向最优区域移动。在
PSO中gbest(或者lbest)将信息传给其他粒子,是单向的信息流动,多数情况下,所有的粒子可能更快地收敛于最优解。由于每个粒子在算法结束时仍然保持着其个体极值,因此,如将PSO用于调度和决策问题时,可以给出多种有意义的选择方案。而基本遗传算法在结束时,只能得到最后一代个体的信息,前面迭代的信息没有保留。另外,PSO算法对种群大小不十分敏感,即种群数目下
权重的技术[11]。控制器的输入是当前惯性权重w和当前最好性能评价值(CBPE),CBPE衡量PSO目前找到的最好候选解的性能;输出是w的改变量。由于不同的问题有不同范围的性能评价值,因此需要对CBPE进行如下的规范化
NCBPE=
CBPEmax-CBPEmin
(7)
NCBPE是规范化后的评价值,CBPEmin和CBPEmax
降时性能下降不是很大。
PSO收敛快,特别是在算法的早期,但也存
依问题而定,且需事先得知或者可估计。
模糊w法与线性下降w方法的比较结果显示,后者不知道应该降低w的合适时机,而自适应模糊控制器能预测使用什么样的w更合适,可以动态地平衡全局和局部搜索能力。但是由于需知道CBPEmin和CBPEmax等,使得模糊权重法的实现较为困难,因而无法广泛使用[3]。
31113 压缩因子(constrictionfactor)法 Clerc得出结论:压缩因子有助于确保PSO算法收敛[12]。这种方法的速度更新方程为
k+1kkkk
vid=χ(vid+c1rand1(pbestid-xid)+
k
c2rand2(gbestd-
xkid))
在着精度较低,易发散等缺点。若加速系数、最大速度等参数太大,粒子群可能错过最优解,算法不收敛;而在收敛的情况下,由于所有的粒子都向最
优解的方向飞去,所以粒子趋向同一化(失去了多样性),使得后期收敛速度明显变慢,同时算法收敛到一定精度时,无法继续优化,所能达到的精度也比GA低[7],因此很多学者都致力于提高PSO算法的性能。311 收敛速度的改进
31111 惯性权重(inertiaweight)法 Shi等提出
(8)
其中χ=2/|2-φ-(φ2-4φ)1/2|为压缩因子,
φ=c1+c2,且φ>4。
约束因子法控制系统行为最终收敛,且可以有效搜索不同的区域,该法能得到高质量的解,如果与此同时将每维vdmax设置为一维搜索空间的大小
了惯性权重的方法[8]。惯性权重w是与前一次速度有关的一个比例因子,而速度更新方程为
90
xdmax,则可以得到更好的效果。
中国工程科学第6
卷
31114 选择(selection)法 Angeline提出的混和PSO主要应用PSO的基本机制以及演化计算所采
粒子b的距离。而选择阈值frac根据迭代次数而变
化。当另一粒子b满足‖Xa-Xb‖/dmax
31 (topologies)法 (3))每个粒子左右两边,实际上这是应用了环形拓Kennedy测试了如图2所示的几种邻域拓扑结构[15]
。
用的自然选择机制[6]。由于PSO搜索过程依赖pbest和gbest,所以搜索区域有可能被他们限制住了。自然选择机制的引入将会逐渐减弱其影响[1]。测试结果显示,虽然在大多数测试函数中选择法取得了比基本PSO更好的效果,却在Griewank函数上得到了较差的结果。因此该法提高了PSO部搜索能力,]。31115 繁殖(Breeding)局版PSO中,Pi选出的粒子进行如下式
child1(Xi)=piparent1(Xi)+
(110-pi)parent2(Xi)
(9)(10)
child2(Xi)=piparent2(Xi)+
(110-pi)parent1(Xi)
child1(Vi)=
()()
・
|parent1(Vi)+parent2(Vi)|
|parent1(Vi)|
(11)
child2(Vi)=
()()
・
|parent1(Vi)+parent2(Vi)|
|parent2(Vi)|
(12)
的代数杂交操作,产生子代的粒子取代父代。选择父代没有基于适应值,防止了基于适应值的选择对那些多局部极值的函数带来潜在问题[3]。pi是(0,1)间的随机数(经验值约为012)。理论上讲繁殖法可以更好地搜索粒子间的空间,2个在不同次优峰处的粒子经繁殖后,可以从局部最优逃离。结果显示,对单峰函数,繁殖法虽略加快了收敛速度,却不如基本PSO和GA找到的解好,而对于多局部极值的函数,繁殖PSO不仅加快了收敛速度,而且找到了同样好或更好的解[13]。312 增加多样性的改进31211 空间邻域(spatialneighborhoods)法 基本的局部版PSO中(见式(3))粒子的邻域是基于粒子序号划分的。Suganthan提出了基于粒子的空间位置划分的方案[14]。在迭代中,计算每一个粒子与群中其他粒子的距离,记录任何2个粒子间的最大距离为dmax。对每一粒子按照
(13)‖Xa-Xb‖/dmax计算一个比值,其中‖Xa-Xb‖是当前粒子a到
图1 两种可能的邻域拓扑在有些边
被随机改变前后的图形
Fig11 Adiagrammaticrepresentationoftwopossibleneighbourhoodtopologies,beforeandafteredgeshavebeenrandomlyexchanged
结果表明,拓扑非常影响算法的性能,且最佳的拓扑形式因问题而定。如对有很多局部最优的函数,轮形拓扑邻域算法能得到最好的结果,Kennedy推测,这是由于较慢的信息流动;而对于单峰函数,星形拓扑邻域算法可以产生较好的结果,因为它有较快的信息流动(这里的拓扑都是在粒子序号空间下的拓扑)。
31213 社会趋同(socialstereotyping)法 Kenney提出了混和空间邻域和环形拓扑方法的另一个局部PSO版本,称为社会趋同法[16]。因为生活中人们往往是试图追随一个群体的共同观点,而不是群体中某个人的立场。将该思想应用到PSO中,即不用每个粒子的经验而是用它所属空间聚类的共同经验来更新自己。
第5期313 全局方法
杨 维等:粒子群优化算法综述91
是该改进同基本PSO一样不能保证算法收敛到全局最优。
31512 协同PSO(cooperativePSO)
31311 序列生境技术(SNT,sequentialnichetechnique)法 Beasley等提出的最初使用在遗传
文献[20]
算法中的序列生境技术可以系统地访问每一个全局极值[17]。其思想是在找到每一个极值后,都用下降函数来自适应地改变适应值函数,如此算法就不会再回到该极值。虽然将SNT引入PSO会带来诸如参数选择、引入更多局部极值等问题,但是该法能够枚举所有全局极值,很有意义的[3]。
31312 函数延伸(提出了一种协同PSO,该方法是将n维向量分到n个粒子群中,,评价适应例如针对第j个粒,j-1个分量都设为,j个,j维的最好值,其他维相同。为将有,可将n维向量分到k个粒子群来优化,则前nmodk个粒子群是「n/k
2004年5月第
6卷第5期
中国工程科学May.2004Vol16No15
综合述评
杨 维,(250061)
[摘要] (PSO)算法是一种新兴的优化技术,其思想来源于人工生命和演化计算理论。PSO通
。该算法简单易实现,可调参数少,已得到广泛研究和应用。详细介绍了PSO的基本原理、各种改进技术及其应用等,并对其未来的研究提出了一些建议。群体智能;演化算法;粒子群优化[关键词]
[中图分类号]TP30116 [文献标识码]A [文章编号]1009-1742(2004)05-0087-08
1 前言
从20世纪90年代初,就产生了模拟自然生物
群体(swarm)行为的优化技术。Dorigo等从生物进化的机理中受到启发,通过模拟蚂蚁的寻径行为,提出了蚁群优化方法;Eberhart和Kennedy于1995年提出的粒子群优化算法是基于对鸟群、鱼群的模拟。这些研究可以称为群体智能(swarmintelligence)。通常单个自然生物并不是智能的,但是整个生物群体却表现出处理复杂问题的能力,群体智能就是这些团体行为在人工智能问题中的应用。粒子群优化(PSO)最初是处理连续优化问题的,目前其应用已扩展到组合优化问题[1]。由于其简单、有效的特点,PSO已经得到了众多学者的重视和研究。
的控制之下,即复杂的全局行为是由简单规则的相互作用引起的。PSO即源于对鸟群捕食行为的研究,一群鸟在随机搜寻食物,如果这个区域里只有一块食物,那么找到食物的最简单有效的策略就是搜寻目前离食物最近的鸟的周围区域。PSO算法就是从这种模型中得到启示而产生的,并用于解决优化问题。另外,人们通常是以他们自己及他人的经验来作为决策的依据,这就构成了PSO的一个基本概念。
PSO求解优化问题时,问题的解对应于搜索空间中一只鸟的位置,称这些鸟为“粒子”(particle)或“主体”(agent)。每个粒子都有自己的位置和速度(决定飞行的方向和距离),还有一个由被优化函数决定的适应值。各个粒子记忆、追随当前的最优粒子,在解空间中搜索。每次迭代的过程不是完全随机的,如果找到较好解,将会以此为依据来寻找下一个解。
令PSO初始化为一群随机粒子(随机解),在每一次迭代中,粒子通过跟踪两个“极值”来更新自己:第一个就是粒子本身所找到的最好解,叫做个体极值点(用pbest表示其位置),全局版PSO中的另一个极值点是整个种群目前找到的最好解,
2 PSO基本原理
211 基本PSO原理
粒子群优化算法是基于群体的演化算法,其思想来源于人工生命和演化计算理论。Reynolds对鸟群飞行的研究发现,鸟仅仅是追踪它有限数量的邻居,但最终的整体结果是整个鸟群好像在一个中心
[收稿日期] 2003-08-05;修回日期 2003-09-08
[基金项目] “八六三”高技术资助项目(2001AA413420),山东省自然科学基金资助项目(2003G01)[作者简介] 杨 维(1978-),女(满族),山东济南市人,山东大学控制科学与工程学院硕士研究生
88中国工程科学第6卷
Step3粒子的更新 用式(1)和式(2)对每
称为全局极值点(用gbest表示其位置),而局部
版PSO不用整个种群而是用其中一部分作为粒子的邻居,所有邻居中的最好解就是局部极值点(用lbest表示其位置)。在找到这两个最好解后,粒子
一个粒子的速度和位置进行更新。
Step4检验是否符合结束条件 如果当前的迭
根据如下的式(1)和式(2)来更新自己的速度和位置。粒子i的信息可以用D维向量表示,位置表示为Xi=(xi1,xi2,...,xiD)T,速度为Vi=
(vi1,vi2,...,viD)T,其他向量类似。则速度和
代次数达到了预先设定的最大次数(或达到最小错误要求),则停止迭代,,否则转到Step2。
PSO2)类似于遗传算法(GA)PSO也是多点搜索。
3)式(1)的第一项对应多样化(diversification)的特点,第二项、第三项对应于搜索过程的集中化(intensification)特点,因此这个方法在多样化和集中化之间建立均衡[1]。
PSO有全局版和局部版两种,全局版收敛快,但有时会陷入局部最优。局部版PSO通过保持多个吸引子来避免早熟,假设每一个粒子在大小l的邻域内定义为一个集合
Ni={pbesti-l,pbesti-l+1,...,pbesti-1,pbesti,
pbesti+1,...,pbesti+l-1,pbesti+l}
(3)
位置更新方程为
vid
k+1
=vid+c1rand1(pbestidxc2rand2(xid)x1
k
kkkk
(1)(2)
xidvid
kk1
vkid是粒子i在第kd维的速度;c1,c2
是加速系数(或称学习因子),分别调节向全局最好粒子和个体最好粒子方向飞行的最大步长,若太小,则粒子可能远离目标区域,若太大则会导致突然向目标区域飞去,或飞过目标区域[2]。合适的
c1,c2可以加快收敛且不易陷入局部最优,通常
令c1=c2=2;rand1,2是[0,1]之间的随机数;
xid是粒子i在第k次迭代中第d维的当前位置;
k
pbestid是粒子i在第d维的个体极值点的位置(即
坐标);gbestd是整个群在第d维的全局极值点的位置。为防止粒子远离搜索空间,粒子的每一维速度vd都会被钳位在[-vdmax,+vdmax]之间,
vdmax太大,粒子将飞离最好解,太小将会陷入局
部最优[2]。假设将搜索空间的第d维定义为区间
[-xdmax,+xdmax],则通常vdmax=kxdmax,011
≤k≤110,每一维都用相同的设置方法。基本PSO的流程可以描述为:
Step1初始化 初始搜索点的位置X0i及其速
度V0i通常是在允许的范围内随机产生的,每个粒子的pbest坐标设置为其当前位置,且计算出其相应的个体极值(即个体极值点的适应度值),而全局极值(即全局极值点的适应度值)就是个体极值中最好的,记录该最好值的粒子序号,并将gbest设置为该最好粒子的当前位置。
Step2评价每一个粒子 计算粒子的适应度
从Ni中选出最好的,将其位置作为lbest代替公式
中的gbest,其他与全局版PSO相同。实验表明,局部版比全局版收敛慢,但不容易陷入局部最优[3]。在实际应用中,可以先用全局PSO找到大致的结果,再用局部PSO进行搜索。212 二进制PSO
最初的PSO是从解决连续优化问题发展起来的,Eberhart等又提出了PSO的离散二进制版,用来解决工程实际中的组合优化问题[4]。他们在提出的模型中将每一维xid和pbestid限制为1或者为0,而速度vid不作这种限制。用速度来更新位置时,如果vid高一些,粒子的位置xid更有可能选1,vid低一点则选0,阈值在[0,1]之间,而有这种特点的函数就是Sigmoid函数:
k
sig(vkid)=1/(1+exp(-vid))
(4)
二进制版本PSO的公式为
k+1k+1k+1ifρ
+1
else
xkid=0
值,如果好于该粒子当前的个体极值,则将pbest
设置为该粒子的位置,且更新个体极值。如果所有粒子的个体极值中最好的好于当前的全局极值,则将gbest设置为该粒子的位置,记录该粒子的序号,且更新全局极值。
(5)
k+1
向量ρid的各个分量是[0,1]之间的随机
数[1]。为了防止Sigmoid函数饱和,可以将vkid钳位在[-410,+410]之间。二进制PSO其他部分与基本连续PSO类似。实验结果显示,在大多
第5期杨 维等:粒子群优化算法综述
vid
k+1
89
k
k
k
k
数测试函数中,二进制PSO都比遗传算法速度快,尤其在问题的维数增加时。
213 解决混和整数非线性规划(MINLP)问题的
PSO
=wvid+c1rand1(pbestid-xid)+
c2rand2(gbestd-xid)
k
k
k
(6)
如果用离散数字来表达当前的位置和速度,或者在速度更新完成后对整数变量进行取整运算,则可以在算法中同时处理连续和离散变量。这就为解决MINLP等问题提供了广阔天地,文献[5]中已将解决MINLP的PSO制问题。
用惯性权重来控制前面的速度对当前速度的影
响,较大的w可以加强PSO的全局搜索能力,而较小的w[9]。基本的PSO可以看作1,力,1,112]之间PSO[10]中试验了将w设到014的线性下降,使得PSO在开始,较快地定位最优解的大致位置,随着w逐渐减小,粒子速度减慢,开始精细的局部搜索(这里w类似于模拟退火中的温度参数)。该方法加快了收敛速度,提高了PSO算法的性能。当待解问题很复杂时,该法使得PSO在迭代后期全局搜索能力不足,导致不能找到要求的最优解,这可以用自适应改变惯性权重来克服。31112 模糊惯性权重(fuzzyinertiaweight)法 Shi等提出用模糊控制器来动态自适应地改变惯性
3 PSO PSO与GA,两者都随机初始化种群,使用适应值来评价系统和进行一定的随机搜索。但PSO是根据自己的速度来决定搜索,没有GA的明显的交叉和变异。如果将pbest也看作是种群的成员,那么PSO也有一种很弱形式的选择[6]。速度更新方程中如果没有vkid项,可以解释为一种代数交叉,而对vkid更好的理解是把每次迭代看成是一种不断适应的过程。GA中染色体共享信息,故整个种群较均匀地向最优区域移动。在
PSO中gbest(或者lbest)将信息传给其他粒子,是单向的信息流动,多数情况下,所有的粒子可能更快地收敛于最优解。由于每个粒子在算法结束时仍然保持着其个体极值,因此,如将PSO用于调度和决策问题时,可以给出多种有意义的选择方案。而基本遗传算法在结束时,只能得到最后一代个体的信息,前面迭代的信息没有保留。另外,PSO算法对种群大小不十分敏感,即种群数目下
权重的技术[11]。控制器的输入是当前惯性权重w和当前最好性能评价值(CBPE),CBPE衡量PSO目前找到的最好候选解的性能;输出是w的改变量。由于不同的问题有不同范围的性能评价值,因此需要对CBPE进行如下的规范化
NCBPE=
CBPEmax-CBPEmin
(7)
NCBPE是规范化后的评价值,CBPEmin和CBPEmax
降时性能下降不是很大。
PSO收敛快,特别是在算法的早期,但也存
依问题而定,且需事先得知或者可估计。
模糊w法与线性下降w方法的比较结果显示,后者不知道应该降低w的合适时机,而自适应模糊控制器能预测使用什么样的w更合适,可以动态地平衡全局和局部搜索能力。但是由于需知道CBPEmin和CBPEmax等,使得模糊权重法的实现较为困难,因而无法广泛使用[3]。
31113 压缩因子(constrictionfactor)法 Clerc得出结论:压缩因子有助于确保PSO算法收敛[12]。这种方法的速度更新方程为
k+1kkkk
vid=χ(vid+c1rand1(pbestid-xid)+
k
c2rand2(gbestd-
xkid))
在着精度较低,易发散等缺点。若加速系数、最大速度等参数太大,粒子群可能错过最优解,算法不收敛;而在收敛的情况下,由于所有的粒子都向最
优解的方向飞去,所以粒子趋向同一化(失去了多样性),使得后期收敛速度明显变慢,同时算法收敛到一定精度时,无法继续优化,所能达到的精度也比GA低[7],因此很多学者都致力于提高PSO算法的性能。311 收敛速度的改进
31111 惯性权重(inertiaweight)法 Shi等提出
(8)
其中χ=2/|2-φ-(φ2-4φ)1/2|为压缩因子,
φ=c1+c2,且φ>4。
约束因子法控制系统行为最终收敛,且可以有效搜索不同的区域,该法能得到高质量的解,如果与此同时将每维vdmax设置为一维搜索空间的大小
了惯性权重的方法[8]。惯性权重w是与前一次速度有关的一个比例因子,而速度更新方程为
90
xdmax,则可以得到更好的效果。
中国工程科学第6
卷
31114 选择(selection)法 Angeline提出的混和PSO主要应用PSO的基本机制以及演化计算所采
粒子b的距离。而选择阈值frac根据迭代次数而变
化。当另一粒子b满足‖Xa-Xb‖/dmax
31 (topologies)法 (3))每个粒子左右两边,实际上这是应用了环形拓Kennedy测试了如图2所示的几种邻域拓扑结构[15]
。
用的自然选择机制[6]。由于PSO搜索过程依赖pbest和gbest,所以搜索区域有可能被他们限制住了。自然选择机制的引入将会逐渐减弱其影响[1]。测试结果显示,虽然在大多数测试函数中选择法取得了比基本PSO更好的效果,却在Griewank函数上得到了较差的结果。因此该法提高了PSO部搜索能力,]。31115 繁殖(Breeding)局版PSO中,Pi选出的粒子进行如下式
child1(Xi)=piparent1(Xi)+
(110-pi)parent2(Xi)
(9)(10)
child2(Xi)=piparent2(Xi)+
(110-pi)parent1(Xi)
child1(Vi)=
()()
・
|parent1(Vi)+parent2(Vi)|
|parent1(Vi)|
(11)
child2(Vi)=
()()
・
|parent1(Vi)+parent2(Vi)|
|parent2(Vi)|
(12)
的代数杂交操作,产生子代的粒子取代父代。选择父代没有基于适应值,防止了基于适应值的选择对那些多局部极值的函数带来潜在问题[3]。pi是(0,1)间的随机数(经验值约为012)。理论上讲繁殖法可以更好地搜索粒子间的空间,2个在不同次优峰处的粒子经繁殖后,可以从局部最优逃离。结果显示,对单峰函数,繁殖法虽略加快了收敛速度,却不如基本PSO和GA找到的解好,而对于多局部极值的函数,繁殖PSO不仅加快了收敛速度,而且找到了同样好或更好的解[13]。312 增加多样性的改进31211 空间邻域(spatialneighborhoods)法 基本的局部版PSO中(见式(3))粒子的邻域是基于粒子序号划分的。Suganthan提出了基于粒子的空间位置划分的方案[14]。在迭代中,计算每一个粒子与群中其他粒子的距离,记录任何2个粒子间的最大距离为dmax。对每一粒子按照
(13)‖Xa-Xb‖/dmax计算一个比值,其中‖Xa-Xb‖是当前粒子a到
图1 两种可能的邻域拓扑在有些边
被随机改变前后的图形
Fig11 Adiagrammaticrepresentationoftwopossibleneighbourhoodtopologies,beforeandafteredgeshavebeenrandomlyexchanged
结果表明,拓扑非常影响算法的性能,且最佳的拓扑形式因问题而定。如对有很多局部最优的函数,轮形拓扑邻域算法能得到最好的结果,Kennedy推测,这是由于较慢的信息流动;而对于单峰函数,星形拓扑邻域算法可以产生较好的结果,因为它有较快的信息流动(这里的拓扑都是在粒子序号空间下的拓扑)。
31213 社会趋同(socialstereotyping)法 Kenney提出了混和空间邻域和环形拓扑方法的另一个局部PSO版本,称为社会趋同法[16]。因为生活中人们往往是试图追随一个群体的共同观点,而不是群体中某个人的立场。将该思想应用到PSO中,即不用每个粒子的经验而是用它所属空间聚类的共同经验来更新自己。
第5期313 全局方法
杨 维等:粒子群优化算法综述91
是该改进同基本PSO一样不能保证算法收敛到全局最优。
31512 协同PSO(cooperativePSO)
31311 序列生境技术(SNT,sequentialnichetechnique)法 Beasley等提出的最初使用在遗传
文献[20]
算法中的序列生境技术可以系统地访问每一个全局极值[17]。其思想是在找到每一个极值后,都用下降函数来自适应地改变适应值函数,如此算法就不会再回到该极值。虽然将SNT引入PSO会带来诸如参数选择、引入更多局部极值等问题,但是该法能够枚举所有全局极值,很有意义的[3]。
31312 函数延伸(提出了一种协同PSO,该方法是将n维向量分到n个粒子群中,,评价适应例如针对第j个粒,j-1个分量都设为,j个,j维的最好值,其他维相同。为将有,可将n维向量分到k个粒子群来优化,则前nmodk个粒子群是「n/k