李 娥, 高兴宝

(陕西师范大学数学与信息科学学院， 陕西 西安 710062)

0 引 言

群体智能产生于20世纪90年代, 它通过模拟生物群体行为来解决优化问题的演化计算技术. 基于群体智能理论,Kennedy和Eberhart 提出了粒子群算法(PSO)[1-2], 其基本原理是通过群体中粒子跟踪自己和群体所发现的最优值, 修正前进方向和速度, 实现寻优. PSO算法由于理论简单、易于实现、需要设置的参数少、收敛速度较快等特点,被广泛应用于函数优化、神经网络优化、模糊系统控制、电力系统优化、车间调度、负荷经济分配[3-7]等领域. 然而在处理多局部极值问题时, 其存在难以跳出局部极值, 收敛效率低等缺陷. 针对这些问题, 作者提出了一种基于阶段进化适应性策略的粒子群算法. 该算法把整个进化过程分为三个阶段, 每个阶段采用不同的进化策略. 与标准粒子群算法相比, 该算法的全局搜索能力、避免早熟的能力均有了显著提高, 同时也提高了收敛速度.

粒子群算法[8]是一种模拟鸟类捕食行为的群体智能优化算法. 鸟类在寻找食物的过程中, 每只鸟都会根据自己的飞行经验以及同群体中的其它个体的交流来改变自己的飞行方向或者调整飞行速度, 以便能更快速有效地找到食物所在地， PSO就是通过粒子间的相互作用和对解空间的并行搜索寻找最优解. 用vi=(vi1,vi2,…,vin)表示第i个粒子的飞行速度,xi=(xi1,xi2,…，xim)表示其位置;pbesti表示粒子i所经过的最好位置, 称为个体最优;gbest表示群体中所有粒子当前最优位置, 称为全局最优;t表示进化代. 为讨论方便, 设f(x)为适应度函数,PSO流程如下:

步(1)迭代开始t=0，初始化粒子群: 给定群体规模n, 随机产生每个粒子的速度vi和位置xi.

步(2)计算每个个体的适应值f(xi(t)).

步(3)确定个体最优位置(pbesti(t)), 粒子i当前最优位置由下式来确定:

步(4)确定群体最优位置(gbest(t)), 它由下式确定:

gbest(t)∈{pbest1(t),pbest2(t),…,pbestn(t)}|f(gbest(t))

=max{f(pbest1(t)),pbest2(t)),…,pbestn(t))}

步(5)更新速度和位置:

vi(t+1)=vi(t)+c1r1(pbesti(t)-xi(t))+c2r2(gbest(t)-xi(t))

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

其中c1,c2是学习因子, 且为[0,2]上的常数;r1,r2是[0,1]之间的随机数.

步(6)判断是否达到终止条件. 若终止条件成立则停止; 否则t=t+1，转步(2).

由于基本PSO的参数是固定的, 在求解某些优化问题时精度较差，因此通过长期的研究, 人们对速度更新公式进行改进. 特别地, 文献[9]在速度更新公式中加入了惯性权重w,即vi(t+1)=wvi(t)+c1r1(pbesti-xi)+c2r2(gbest-xi) ,其中w∈[0,1.4]是一常数. 为了进一步提高粒子群算法的性能, 文献[10,11]提出了如下惯性权重w线性递减的改进:

其中T为最大迭代次数,wmax为迭代至最大迭代次数时的惯性权重,wmin为初始惯性权重. 该算法在搜索初期具有较强的搜索能力, 而在后期又能够得到较精确的结果, 从而大大提高了基本PSO的性能, 因此被称为标准粒子群算法. 但对于多峰函数优化问题, 易出现早熟现象. 为克服这一缺点, 本文提出了一种基于阶段进化适应性策略的改进算法.

1 改进的粒子群算法

不像遗传算法, 粒子群优化算法一般采用实数编码, 并且大多数情况也没有选择、交叉和变异操作, 因此算法结构相对简单, 运行速度较快. 但在算法运行过程中, 如果某粒子发现一个当前最优位置, 其他粒子将迅速向其靠拢. 如果该最优位置为一局部最优点,粒子群就无法在解空间重新搜索, 因此算法陷入局部最优, 出现了所谓的早熟收敛现象以及由此导致的收敛精度低和不易收敛等缺点, 尤其对高维问题更易出现上述现象. 针对上述问题, 受人类进化过程的启发, 我们将文献[13]中遗传算法的基于阶段进化的适应性策略引入到粒子群算法, 提出了一种如下的改进方案, 称为阶段进化适应性策略粒子群算法(记作EPSO). 按照遗传算法阶段进化适应性策略, 我们将进化过程分为三个阶段: 探索阶段，开发阶段和收敛阶段. 在探索阶段, 采用较大的群体规模、 惯性权重以增强粒子的探索能力, 并引入变异操作保持群体的多样性; 在开发阶段, 由于群体逐渐转入面向局部的开发过程, 所以采用较小的群体规模和变化的惯性权重; 在收敛阶段, 由于粒子要逐渐收敛到最优解， 故采用小的群体规模和惯性权重, 且为避免早熟收敛, 引入变异操作. 根据多次反复试验, 基于阶段进化的适应性策略模型如下:

(1) 进化阶段: 设α∈[0,0.5]最大进化代数为T, 三阶段划分如下:

第一阶段(探索阶段):I1=[0,T1],T1=αT.第二阶段(开发阶段):I2=[T1+1,T2],T2=T(1-α).第三阶段(收敛阶段):I3=[T2+1,T].

一般地, 取α=0.382.

(2) 群体规模: 固定参数群体规模为n, 在进化第一阶段采用较大群体规模n1, 第二、三阶段采用较小群体n2,n3,它们的选取不能过大也不能过小. 根据多次反复实验，可取n1=n,n2=0.7n,n3=0.5n.

(3) 惯性权重: 第一阶段采用较大的惯性权重, 一般可取w=0.8, 第二阶段采用线性递减的惯性权重[11], 即

第三阶段采用较小的惯性权重, 一般可取w=0.4.

(4) 变异操作: 第一、第三阶段引入变异操作，增加搜索空间多样性和避免早熟现象. 因为搜索空间的多样性同时受w和变异概率pm的影响, 且第一阶段w取值较大，所以其变异概率相对要小一点, 一般可取pm=0.01; 第三阶段w较小, 但由于粒子在这一阶段要收敛, 还要避免早熟, 因此变异概率相对要大一点，但不能过大. 经反复试验, 可取pm=0.05. 变异操作按照如下公式进行:

其中r1,r2是[0,1]内的随机数.

2 数值仿真

本文用4个基准测试函数[14]在Matlab上进行数值仿真, 其参数设置如下: 群体规模为30, 最大迭代次数为1 000, 学习因子c1,c2均为2;wmax=0.9，wmin=0.4.为消除随机干扰， 每个函数独立运行30次, 然后取其平均值. 在同样的参数设置下, 与标准粒子群算法进行比较.

例 1 Sphere Model 函数

显然它是单峰可分的二次函数, 且仅有一个全局极小点x*=(0,0,…,0),最优值为f1(x*)=0. 图1显示了标准PSO算法和改进 PSO算法的最优值随迭代次数的变化曲线.

例2 Griewank函数

它具有大量局部极值点, 是不可分离的多峰函数，有一个全局极小点x*=(0,0,…,0), 最优值为f2(x*)=0. 图2显示了标准PSO算法和改进PSO算法的最优值随迭代次数的变化曲线.

图1 例1中最优值随迭代次数的变化曲线 图2 例2中最优值随迭代次数的变化曲线

例3 Rastrigin函数

它是多峰函数, 有一个全局极小点x*(0,0,…,0), 最优值为f3(x*)=0. 图3显示了标准PSO算法和改进PSO算法的最优值随迭代次数的变化曲线.

图3 例 3中最优值随迭代次数的变化曲线 图4 例 4中最优值随迭代次数的变化曲线

例4 Schaffer's f6函数.

译员由于不能确认被告的意思而与被告展开了对话——对电话号码的事情进行了澄清，以便把完整的意思翻译给法官听。这种澄清的行为对避免误译时是必要的。但是，本例中的问题是译员自行与被告展开了对话，法官可能因此对译员产生不信任并提出批评。比较好的调解策略是译员先获得法庭的许可。由于口译过程一般以第一人称进行，译员应该让法庭知道下面的请求是译员提出的：“法官大人，译员不是很明白被告的话，请允许译员要求被告澄清。”在法官许可后再要求说话者澄清。译员也会因为其专业性的调解行为而赢得法庭的尊重。

它是多峰函数, 有一个全局极小点x*=(0,0), 最优值为f4(x*)=0. 图4显示了标准PSO算法和改进PSO算法的最优值随迭代次数的变化曲线.

4个函数在标准PSO算法和改进PSO算法下的数值结果见表1.

表1 函数运行30次比较表

从表1可以看出，改进的PSO在F4函数上的效果明显好于标准PSO，达到了理论最优值. 其余3个函数虽没有达到理论最优值，但是从图1至图3可以看出，它们避免了早熟现象, 在要求的精度内收敛到了全局最优, 其结果好于标准PSO的结果. 改进的PSO在单峰函数上的效果不是很明显，但它和标准的PSO相比提高了收敛速度.

3 结束语

PSO 算法理论简单、易实现、需要设置的参数少、收敛较快等优点, 但也存在着早熟收敛、收敛效率低的缺点， 本文针对这一缺点提出了一种改进算法, 即基于阶段进化适应性策略的粒子群算法. 该算法把进化过程分为三个阶段, 每个阶段采用不同的惯性权重、 群体规模, 并在第一阶段和第三阶段引入了不同的变异操作, 以增强粒子跳出局部最优的能力. 通过和标准粒子群算法比较的实验结果可以看出, 该算法收敛到了全局最优解, 具有较好的收敛性和收敛效率, 克服了PSO算法易“早熟”的缺点.

参考文献

[1] Kennedy J, Eberhart R C. Particle swarm optimization[A]. Proc IEEE Conf on Neural Networks[C]. Piscataway: IEEE Press, 1995：1 942-1 948.

[2] Eberhart R C, Kennedy J. A new optimizer using particles warm theory[A]. Proc of the 6th International Symposium on Micro Machine and Human Science[C]. Nagoya, 1995：39-43.

[3] 刘华蓥, 林月娥, 齐名军. 求解约束优化问题的改进的粒子群算法[J]. 大庆石油学院学报, 2005, 29(4):73-75.

[4] He Z, Wei C, Yang L. Extracting rules from fuzzy neural network by particle swarm optimization[A]. Proc IEEE Conf on Evolutionary Computation[C]. Piscataway: IEEE Press, 1999：1 927-1 930.

[6] Pan Q K, Tasgetiren M F, Liang Y C. A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem[J]. Computers and Operations Research, 2008, 35:2 807-2 839.

[7] Panigrahi B K, Pandi V R, Sanjoy Das. Adaptive particle swarm optimization approach for static and dynamical economic load dispatch[J]. Energy Conversion and Management, 2008, 49: 1 407-1 415.

[8] 凡 涛, 陈光喜. 多目标粒子群优化算法的改进及其应用[D]. 桂林：桂林电子科技大学硕士学位论文, 2010.

[9] Shi Y H, Eberhart R C. A modified particle swarm optimizer[A]. IEEE World Congress on Computational Intelligence [C]. Anchorage, 1998：69-73.

[10] Eberhart R C, Shi Y H. Comparing inertia weights and constriction factors in particle swarm optimization[A]. Proc 2000 Congress Evolutionary Computation[C]. Piscataway: IEEE Press, 2000：84-88.

[11] Kennedy J, Eberhart R C, Shi Y H. Swarm Intelligence[M]. San Francisco: Morgan Kaufman Publishers, 2001.

[12] 吕振肃, 侯志荣. 自适应变异的粒子群优化算法[J]. 电子学报, 2004，(3): 416-420.

[13] 李敏强, 寇纪淞, 林 丹,等. 遗传算法的基本理论与应用[M]. 北京: 科学出版社, 2002.

[14] 纪 震, 廖惠连, 吴青华. 粒子群算法及其应用[M]. 北京: 科学出版社, 2009.