基于变异和交叉的改进粒子群算法

闫元元, 高兴宝, 周喜虎

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

0 引 言

1995年, 通过对鸟群捕食行为的研究, Eberhart和Kennedy[1，2]提出了粒子群优化算法(PSO)， 它基于群体智能理论, 通过群体中粒子跟踪自己和群体所发现的最优值, 修正前进的方向和速度, 实现寻优. PSO算法简单, 需调整的参数少且易于实现, 因此广泛应用于函数优化、神经网络优化、模糊系统控制以及其它领域[3]. 但是粒子群算法同其它进化算法一样存在早熟收敛的缺点, 其原因主要在于群体多样性的丧失. 本文首先介绍了标准粒子群算法, 然后基于变异和交叉提出了一种新的算法, 用4个基准函数测试, 试验结果表明新算法提高了标准粒子群算法克服早熟收敛的能力, 加快了收敛速度.

1 标准粒子群算法

标准粒子群算法首先对群体初始化, 然后通过迭代找到最优解. 在每一次迭代中, 每个粒子考虑自身搜索到的最优位置以及群体搜索到的最优位置进行速度与位置的更新.在D维目标搜索空间中, 由种群数N的粒子组成群体, 其中第i个粒子的位置为xi=(xi1,xi2,…,xiD), 飞行速度为vi=(vi1,vi2,…,viD), 该粒子当前搜索到的最优位置为pi=(pi1,pi2,…,piD), 整个粒子群的最优位置为pg=(pg1,pg2,…,pgD). 标准粒子群算法迭代公式如下:

vid(t+1)=wvid(t)+c1r1(pid-xid(t))+c2r2(pgd-xid(t))

(1)

xid(t+1)=xid(t)+vid(t+1)

(2)

其中i=1,2,3,…,N;d=1,2,3,…,D;t是当前迭代次数;学习因子c1、c2为非负常数, 描述了粒子向自己搜索到的最优位置及群体搜索到的最优位置的靠近程度;r1和r2为[0，1]上均匀分布的伪随机数, 其随机性使得整个粒子群表现出极复杂的特性;w为非负数, 称作惯性权重, 描述了上次迭代速度对当前速度的影响.w较大时算法有较强的全局搜索能力,w较小时算法有较强的局部搜索能力. 文献[4]通过大量试验表明, 如果w随算法迭代的进行而线性减小, 则将显著改善算法的收敛性能. 设TMax为最大迭代次数,wEnd为迭代至最大迭代次数时的惯性权重,wIni为初始惯性权重，则有

w(t)=(wIni-wEnd)(TMax-t)/TMax+wEnd

(3)

2 改进的PSO算法(TPSO)

早熟收敛是指在算法早期, 由于群体最优的吸引, 群体中大多数粒子聚集在群体最优的周围, 使得算法的寻优停滞在局部邻域而无法继续搜索全局最优. 因此, 在算法迭代过程中,要克服早熟收敛问题, 就要增加种群的粒子数或者减弱粒子对当前种群搜索到的局部最优位置的追逐[5]. 因为增加种群的粒子数量, 使得计算量大幅度提高, 因此本文的改进主要体现在减弱粒子对当前种群搜索到的群体最优的追逐. 根据式(1)和式(2), 粒子下一时刻的位置由当前位置和当前速度共同决定, 速度大小决定粒子移动距离, 速度方向决定粒子前进方向. 根据式(1), 粒子当前速度由3部分决定：第一部分是粒子的原来速度,说明了粒子目前的状态; 第二部分是认知项, 表示粒子自身的思考; 第三部分是社会部分, 体现了粒子间的信息共享与相互合作, 它引导粒子飞向粒子群中的最优位置. 因此, 如果将粒子飞向粒子群中最优位置修改为与最优位置反向, 即将式(1)中的(pgd-xid(t))修改为(pgd+xid(t)),就可以改变粒子的前进方向和速度, 从而使粒子进入其它区域进行搜索, 算法就可能发现新的个体极值pi以及全局极值pg, 我们把上述的操作称为速度变异操作. 其次考虑到粒子追随当前pg可能发现更好的位置, 因此新算法将速度变异操作设计成一个随机算子, 即对种群中粒子按一定的概率进行速度变异. 为了使粒子在迭代搜索前期有较强的全局搜索能力, 将搜索空间充满整个解空间, 我们在前期设计一个较大的变异概率, 后期则设计一个较小的变异概率, 以使更多粒子能在所发现的最优位置附近进行搜索.通过以上分析, 我们设计变异概率如下：

pk=pk0/t

(4)

其中,t是迭代次数,pk0是初始变异概率. 当群体中粒子发生速度变异时, 其速度更新公式修改为:

vid(t+1)=wvid(t)+c1r1(pid-xid(t))+c2r2(pgd+xid(t))

(5)

另一方面受黑洞原理的启发, 我们将最优个体适应值吸收半径引入到算法中. 黑洞由于其密度较大, 靠近它的物体将被它的引力所约束. 类似地,对于粒子群, 由于pg点处的适应值较大. 则接近它的粒子将受到它的约束, 使探索能力减弱, 从而将pg看做一个黑洞, 吸收一定范围内的粒子.特别的, 为刻画其特性, 我们引入吸收半径, 即适应值吸收半径r.pg将吸收与其适应值之差小于半径r的粒子, 但为了保持种群规模, 我们将被吸收的粒子重新初始化. 在本文中, 为了使算法后期收敛不受影响, 我们只将黑洞引入前期迭代中, 即k0T次迭代中(0

此外, 由于在速度更新公式中加入了变异, 速度有可能过大, 因此在算法中引入了算术交叉算子来减缓位置的变化.算术交叉算子作用在xi(t)和更新后的位置xi(t+1)上, 特别的通过上面两个位置的线性组合产生新的位置, 作为下次迭代的初始位置, 即：

xi(t+1)=αxi(t+1)+(1-α)xi(t)

(6)

在本文中, 我们取α=1/2.

算法流程如下:

步1 随机初始化种群中每个粒子的位置和速度.

步2 计算每个粒子的适应值, 初始化粒子群的当前全局最优pg=(pg1,pg2,…,pgD)以及每个个体的当前全局最优pi=(pi1,pi2,…,piD).

步3 用(4)式更新pk及用(3)式更新w, 针对变异概率pk, 采用轮盘赌的方式判断粒子是否发生变异, 发生变异时利用(5)式进行速度更新, 否则用(1)式进行速度更新.

步4 用(2)式进行位置更新, 用(6)式作用于当前的位置和更新后的位置上.

步5 判断粒子的适应值是否在最优个体适应值吸收半径内, 如果不在, 转到步7.

步6 对粒子位置进行初始化.

步7 对每个粒子, 将其适应值与pi点处的适应值作比较,如果较好, 则将其作为当前的最优位置, 并比较pi和pg点处的适应值,进行pg更新.

步8 检验是否满足结束条件, 如果当前的迭代次数达到初始的最大次数, 则停止迭代, 输出最优解, 否则转到步3.

3 试验分析

下面通过4个基准函数[6，7]优化问题(求解最小值), 来测试本文算法的性能, 4个优化函数如下所示,其中f1(x)为单峰可分二次函数;f2(x)为旋转、不可分离的多峰函数;f3(x)为具有大量局部最优点的不可分离函数;f4(x)为具有强烈振荡的多峰函数.

F1： Sphere function

F2：Griewank function

F3： Ackley function

(n=30,xi∈[-32,32]) minf6=0

F4： Schaffer′s function

在试验中, 选取标准粒子群算法(linWPSO)作为对比算法. 试验参数设置如下: 两种算法的种群大小均为30, 最大迭代次数为1 000, 学习因子c1、c2均为2.0; 两种算法中wIni=0.9,wEnd=0.4; 在TPSO算法中,pk0和k0均取为1/2;为了消除随机干扰, 对每个优化函数独立运行30次. 所有试验均在lenovo昭阳 E43A具有 windows xp操作系统的计算机上运行,使用MATLAB 7.6编程.

表1 函数运行30次比较表

数值试验结果见表1. 从表中可以看出, 对于所有测试函数, 本文算法的优化结果好于对比算法, 其中对于f1(x)、f3(x), 本文算法并没有达到理论最优值, 但在30次平均最优和最优上要明显好于标准粒子群算法; 对于f2(x), 本文算法在30次中均达到了理论最优值,而标准粒子群算法在运行中均未达到理论最优值; 对于f4(x), 本文算法的优越性并不明显, 但在30次运行中, 本文算法有6次达到了理论最优值, 而标准粒子群算法仅有1次达到了理论最优.

图1 Sphere 图2 Griewank

图3 Ackley 图4 Schaffer

为了更加直观的了解两种算法的性能差异, 图1至图4给出了4个测试函数对于两种算法的最优函数值进化曲线图. 从曲线图中可以看出, 对于f1(x)、f2(x)、f3(x)本文算法明显克服了早熟收敛, 并且收敛速度较标准粒子群算法加快; 对于f4(x), 本文算法在收敛速度上明显快于标准粒子群算法, 但收敛精度同标准粒子群基本相同.

4 结束语

针对粒子群优化算法的早熟收敛问题, 本文提出了一种改进的算法(TPSO). 在新算法中, 引入了变异和交叉操作，分别用4个基准函数进行了试验, 并与标准粒子群算法做了比较, 结果表明新算法提高了标准粒子群算法克服早熟收敛的能力和收敛速率.

参考文献

[1] J.Kennedy,R.Eberhart.Particle Swarm Optimization[C].Proc.IEEE International Conf.on Neural Networks.Perth. Australia,1995:1 943-1 948.

[2] Eberhart R C, Kennedy J. A New Optimizer Using Particles Warm Theory[A].Proc.of the Sixth International Symposium on Micro Machine and Human Science[C].Nagoya,1955:39-43.

[3] Eberhart R.C,Shi Y. Particle Swarm Optimizer:Developments, Applications and Resources[C].Proceeding of IEEE Congress on Evolutionary Computation,2001:81-86.

[4] Shi Y H, Eberhart R C. A Modified Particle Swarm Optimizer[A].IEEE World Congress on Computational Intelligence[C]. Anchorage,1998:69-73.

[5] 刘丽芳.粒子群算法的改进及应用[D].太原:太原理工大学硕士学位论文,2008.

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

[7] 刘 伟, 周育人.一种改进惯性权重的算法[J]. 计算机工程与应用,2009, 22(45):46-48.