PSO的改进<br/>——跳蚤算法

PSO的改进
——跳蚤算法

2015-02-20黄志钢赵晓寒

沈阳理工大学学报 2015年4期

关键词：跳蚤算例邻域

黄志钢，赵晓寒，孙泰

(1.沈阳理工大学信息科学与工程学院，辽宁沈阳 110159；2.香港中文大学，香港新界沙田)

PSO的改进
——跳蚤算法

黄志钢1，赵晓寒1，孙泰2

(1.沈阳理工大学信息科学与工程学院，辽宁沈阳 110159；2.香港中文大学，香港新界沙田)

PSO;斥力；跳蚤算法

粒子群算法(PSO)是由kennedy James和Eberhart Russell在1995年提出的一种模拟鸟类捕食行为的全局优化算法[1]。PSO算法的提出引起了演化计算领域国内外众多专家的兴趣，经过几十年的发展，PSO算法被广泛应用于优化和一些工程领域[2-3]。但PSO算法本身也存在一些固有缺陷，其中最主要的是容易产生早熟，在迭代后期，收敛速度慢、全局搜索能力差、粒子出现“趋同性”。提高算法的性能以及避免陷入局部最优点已经成为研究的热点。

1 PSO的早熟与斥力改进

1.1 PSO的早熟

文中，第i个粒子的当前函数值、位置，记为f(xi)、xi；第i个粒子的最优函数值及其位置，记为pibestF、pibestX，称为局部最优解；pibestF中的最优值及其位置，记为GbestF、GbestX，称为全局最优解；函数的全局最优值及其位置记为FbestF、GbestX，称为函数最优解。同时指代位置X和函数值F时不加后缀。

vi(t+1)=wvi(t)+c1×r1(0,1)×(PibestX(t)-xi(t)+c2×r2(0,1)×(GbestX(t)-xi(t))

x1(t+1)=xi(t)+vi(t+1)

根据上述标准PSO算法的迭代公式可知粒子总是受到PibestX和GbestX的吸引，此种只设计了引力没有设计斥力的寻优方法使得粒子一旦陷入局部最优解时，没有斥力把陷入早熟的粒子分散开。另外，PSO算法假设函数最优解在粒子群的运动轨迹包络体中，当函数最优解不在这个包络体中时，粒子有可能无法找到函数最优解。

1.2 R斥力改进

针对早熟问题，研究者们基于参数、位置公式、速度公式等角度对单一的引力进行了各种改进[4]。其中特别引起笔者注意的是范超赞等人[4]，在PSO算法中引进的r斥力，即引入排斥半径r和排斥因子，以最优粒子位置为超圆心设定一个排斥半径r，将进入r区域的粒子依照排斥因子参数排斥出去。

R斥力算法的思路与问题：

(1)如果最优粒子的r范围内仅有一个峰值即函数最优解，没有谷值，则该粒子可以寻优到这个峰值。而且有一个粒子逼近最优解就足够，所以可以驱动其余粒子离开r范围去寻找其他可能的更优解，以此来避免趋同和早熟问题。

(2)但是，如果最优粒子的r范围内有多个峰值和谷值，则该粒子可能早熟于某个峰值，而无法到达函数最优解。同时r斥力阻止其它粒子进入r范围寻找函数最优解。

(3)如果Fbest不在Gbest的r范围内，那么斥力PSO仅仅是把其他粒子排斥离开Gbest。

(4)但是并没有在其余粒子之间设置斥力，其余粒子有可能聚集在一个局部范围内，依然处于早熟趋同状态。例如聚集在Gbest的R边界处，这时的r太小。

(5)若r过大，则可能把FbestX包括进来，这时最优粒子有可能早熟于Gbest，并阻止其他粒子进入FbestX的附近寻优，从而没有粒子去寻找Fbest。

2 寻优算法改进分析

2.1 多峰值函数的特征邻域与可寻优性

2.2 寻优算法对特征邻域的遍历性、粘着性和脱离性

Fbest的特征邻域为空集的函数是不可寻优函数，只有寻优算法恰好取到这个孤立位置才能求得Fbest，因此任何寻优算法只能以零概率求得这种函数的Fbest。

Fbest的特征邻域非空的函数是可寻优函数，某些寻优算法能以正概率进入这个特征邻域并由此寻优到Fbest。

若每个特征邻域内都粘着一个粒子进行寻优，则必然能寻得Fbest[6]。

一个寻优算法如果能按概率遍历所有特征邻域并粘着寻优，则它能按概率寻到Fbest。

粒子群寻优计算时，如果粒子数少于特征邻域数，则寻优算法必须具备脱离性才有可能遍历所有特征邻域。

因此，寻优算法应该具有对特征邻域的遍历性、粘着性和脱离性。

遍历性的作用是防止漏掉Fbest的邻域，粘着性的作用是保障粒子能停留在特征领域内逼近最优点，脱离性的作用是预防和克服趋同现象。

从标准PSO的迭代公式可知，其遍历性、脱离性都不够好，一旦陷入局部最优，粒子群就可能会趋同早熟，导致粒子群无法遍历整个求解域，漏掉Fbest。

3 跳蚤算法

3.1 跳蚤算法的原理

针对标准PSO存在的早熟和趋同性等缺点，提出一种新的优化方法—跳蚤算法。此种算法模拟跳蚤的运动模式，跳蚤体重越大，跳距越短，体重越小，跳距越长，跳蚤对应粒子，体重对应函数值，根据函数值的优劣按一定的关系式动态分配各个粒子的步长，最优粒子分配最小步长细致地寻找最优解，最劣粒子分配最大步长按概率去遍历真优解的特征邻域。每个粒子根据算法规则分配的步长进行寻优操作，使得每个粒子都无法聚集在同一点上，从而使整个粒子群不会出现趋同于局部最优解的现象[7]。

3.2 步长的设定

步长是人为设定的，在本文的算例中，第top(k)个粒子的步长为A·αk，A的值决定了精度，αn(n粒子总数)决定最大步长即穿越谷区的宽度，取1.1～1.5，其中，k代表粒子号。例如：当取α=1.4时，通过对步长的数学表达式的分析可知，若取步长最小为0.01，当粒子的个数为20时，最大步长为10，步长倍数为1000。

3.3 跳蚤算法迭代公式

跳蚤算法的更新迭代公式为

若f(xi)>PibestF则更新Pibest

若有PibestF>GbestF则更新Gbest

stepi=step0·αtop(f(xi))

topi：从小到大的排序；

Pibest：第i个粒子已走过的最优解；

Gbest：全局最优解；

由公式可知跳蚤算法中，粒子的更新迭代是和粒子的当前位置、全局的最优位置有关，并与函数优性有关的步长量。

变步长主要体现粒子间的排斥力，使粒子不能陷入早熟困境，并且粒子的下次方向依据当代方向信息而定。另一方面，在粒子群中加入Gbest的吸引力，暂定其作用强度是Pibest的十分之一。

从两个过程的比较可知，标准PSO的迭代过程只和引力有关，粒子的飞行是被Pibest和Gbest吸引着，而没有排斥力，从而容易陷入局部最优点的早熟困境。相比之下，跳蚤算法，在更新迭代的过程当中，不但存在着吸引力，而且最主要的是存在着排斥力，正是由于这种排斥力，即使所有粒子已经落在一个点上，也能够由于各个粒子不同的步长而分散开，退出局部早熟。

4 算例

其峰谷阻碍寻优算法向函数最优值移动。

图1为二维函数y=r·cosr进行寻优处理的结果，所有粒子的初始位置都在(10，10)处。

图1 二维测试函数时优化算法的算例1

由图1可以清晰地看出，粒子的踪迹比较集中于Gbest的峰值圈，而在其它位置上，粒子基本都是以较大的步长进行搜索，所以密度较小，会显得比较疏散。

图2 二维测试函数时优化算法的算例2

5 结束语

由算例可知，即使粒子全部初始于同一点时，由于步长的不同使得某些粒子可以摆脱局部最优点去寻找更好的点，所以，跳蚤算法可以有效克服早熟问题，特别是对于一些多峰值函数，跳蚤算法能够克服标准PSO算法的不足之处。

但是，跳蚤算法还存在一些缺陷。当步长分配不合理时，比如步长比较小，则很可能粒子无法跳跃“峰谷”到达对面特征邻域。另外，跳蚤算法的精度受限于最小步长step0。在后续的研究中，主要方向是如何预先确定step0或运算中修改最大步长和最小步长来改善整个算法的效果。

[1]Kennedy J，Eberhart R.Particle Swarm Optimization[C].Proceeding of IEEE international conference on neutral networks，Perth，Australia，1995：1942-1948.

[2]谭皓，沈春林，李锦.混合粒子群算法在高维复杂函数寻优中的应用[J].系统工程与电子技术，2005，27(8)：1471-1474.

[3]FAN K S，LIANG Y C，ZAHARA E.Hybrid simplex search and particle swarm optimization for the global optimization of multimodal functions[J].Engineering Optimization，2004，36(4)：401-418.

[4]李宁.粒子群优化算法的理论分析与应用研究[D].武汉：华中科技大学，2007：24-67.

[5]张杰，范超赞.改进粒子群算法研究[D].北京：北方工业大学，2010：11-17.

[6]倪勤.最优化方法与程序设计[M].北京：科学出版社，2009：1-15.

[7]张晓清，张建科，方敏.多峰搜索的动态微粒群算法[J].计算机应用，2005，25(1)：266-267.

(责任编辑：马金发)

Flea Algorithm Based on An Improved Particle Swarm Optimization

HUANG Zhigang1，ZHAO Xiaohan1，SUN Tai2

(1.Shenyang Ligong University，Shenyang 110159，China;2.Chinese University of Hong Kong，Shatin，New Territories，Hong Kong)