一种动态调整加速因子的微粒群优化算法

摘要:提出了一种动态调整加速因子的微粒群优化算法。针对微粒群算法中不同搜索时期的微粒所需要的搜索能力不同,引入余弦函数来动态调整加速因子,平衡算法的全局和局部搜索能力。利用三个Benchmark函数进行数值试验,仿真结果表明,算法稳定,具有较好的收敛性能。

关键词:群智能;微粒群优化;加速因子

中图分类号:TP18 文献标识码:A文章编号:1009-3044(2009)34-9816-03

Particle Swarm Optimization Algorithm with Dynamically Adjusting Acceleration Coefficients

LIN Mu-gang1, LIU Fang-ju2, JIANG Xiao-qi1

(1.Department of Computer Science, Hengyang Normal University, Hengyang 421008, China; 2. School of Computer Science and Technology, University of South China, Hengyang 421001, China)

Abstract: Aiming at particles in different search stage needing for different search capabilities, this paper presents a particle swarm optimization algorithm with dynamically adjusting acceleration coefficients based on cosine function, which improves the performance of the globe search and local search. Experiment simulations of three benchmark functions show that the proposed algorithm has powerful convergence ability and good stability.

Key words: swarm intelligence; particle swarm optimization; acceleration coefficient

微粒群优化算法(Particle Swarm Optimization, PSO)是1995年由Eberhart博士和Kennedy博士受鸟群捕食行为启发而提出的一种基于群体智能的进化计算技术[1]。该算法具有如下优点:原理简单,容易实现;算法通用,不依赖于问题信息;群体协同搜索和记忆能力,保留局部个体和全局种群的最优信息,同时利用个体局部信息和群体全局信息指导算法下一步的搜索,高效而快速。PSO算法所具有的分布式、自组织性、协作性、鲁棒性和实现简单方便等特点,使之在没有全局信息的情况下,为解决复杂问题提供了快速可靠的基础。现在微粒群算法在工程设计与优化、电力系统领域、机器人控制和工业生产优化领域等取得了较为成功的应用,已经成为进化计算领域的研究热点。

在微粒群算法中,加速因子用来分别表示群体中每个个体的个人学习能力和社会学习能力,它们反映了粒子本身经验信息和其他粒子的经验信息对粒子运动轨迹的影响,反映了粒子群之间的信息交流,是调整全局搜索与局部搜索的重要参数。在标准的微粒群算法中,加速因子的取值是固定的,这样不能体现在不同时期,自身的经验和社会的因素对微粒运动的影响,不同时期的全局、局部搜索能力的程度不同。为了找到一种能在全局搜索和局部搜索之间取得最佳平衡的加速因子选取方法,有效提高微粒的学习能力,许多学者提出多种解决方案,文献[2]提出利用线性调整加速因子,该方法在取得一定的效果,但也存在粒子易过早收敛于局部极值的缺点。本文在分析加速因子对算法性能影响的基础上,根据在PSO算法初期应加强社会知识的搜索,使粒子尽可能的飞跃整个搜索空间,以期获得粒子的多样性;而在搜索末期,粒子则应该保持一定的速度,从而尽可能摆脱局部极值的干扰,提出了一种运用余弦函数动态调整加速因子的微粒群算法。数值试验的仿真结果表明,该算法稳定有效,具有较好的收敛性能。

1 微粒群算法原理

微粒群算法是对鸟类捕食行为的模拟,群体中的鸟被抽象为没有质量和体积的“微粒”,通过群体内微粒间的合作与竞争产生的群体智能指导优化搜索,微粒根据其自身“经验”和群体中微粒的最佳“经验”在问题空间中向更好的位置“飞行”,以便搜索最优解。微粒群算法的数学模型如下,假定一个包含m个微粒的微粒群在D维空间运动,群中第i个微粒的当前位置为xi=(xi1,xi2,…,xiD),微粒当前速度为vi=(vi1,vi2,…,viD),微粒的历史最优位置pi(pi1,pi2,…,piD)(将微粒的位置代入到适应度函数计算出适应度值,根据其适应度值的大小就可以判断其位置的优劣);群体中所有微粒中的历史最优位置pg=(pg1,pg2,…,pgD)。标准PSO算法中,微粒的位置和速度根据如下迭代方程进行变化:

式中:i=1,2,…,m,d=1,2,…,D,r1,r2为[0,1]上的均匀分布的伪随机数,w是惯性权重,表明微粒上一代速度对当代速度的影响,c1,c2称为加速因子,为正常数,分别用以调节微粒飞向自身最好位置方向和全局最好位置方向的步长。

2 动态调整加速因子的微粒群算法

在微粒群算法中,加速因子c1,c2是用来调节微粒自身最好位置和群体最优位置对微粒运动的影响。在标准微粒群算法中,c1,c2取固定值来使得算法在全局和局部的搜索能力之间达到平衡的,但这样并不能满足在不同时期的全局、局部搜索能力的相互均衡。若c1取较大值,会使微粒过多的在局部徘徊,相反c2取较大值会使微粒过早收敛到局部极值,因此算法在不同的搜索时期合适的选择c1,c2可以加快收敛且不易陷入局部极值,从而调节全局搜索与局部搜索的平衡。研究发现,算法在理想状态下,搜索初期要使微粒尽可能地飞跃整个搜索空间,以期获得粒子的多样性,而在搜索末期,使微粒以较快的速度、精确地收敛于全局最优解。文献[2]提出利用线性调整加速因子取值的方法来改正微粒群算法,但该方法因为在搜索的前期过大的c1和过小的c2而容易使得粒子在全局徘徊,而后期阶段过小的c1和过大的c2而使得粒子缺乏多样性,导致过早的收敛到局部最优。

本文采用余弦函数来动态调整加速因子,根据c1,c2在不同的时期变化趋势不同,利用余弦函数的变化来调整加速因子,以促进全局搜索和局部搜索之间达到最佳的平衡。c1,c2的取值公式分别为:

式中: C1start和C2start分别是c1和c2的初值,C1end和C2end分别是c1和c2的终值;kmax为算法的最大迭代次数,k为当前迭代次数。

动态调整加速因子的微粒群优化算法具体流程如下:

STEP1 初始化微粒群,即随机产生m个微粒的位置和速度。

STEP2 计算每个微粒的适应度值。

STEP3 对每一个微粒,比较其适应度值和它经历过的最好位置pi的适应度值,如果更好,则更新pi;

STEP4 对每一个微粒,比较其适应度值和种群经历过的最好位置pg的适应度值,如果更好,则更新pg;

STEP5 由式(3)、(4)计算每个微粒的Ck1、Ck2;

STEP6 根据式(1)、(2)更新微粒的速度和位置;

STEP7 如果达到结束条件(足够好的位置或最大迭代次数),则停止,输出相关结果;否则,转STEP 2。

3 数值实验及分析

使用三个Benchmark优化问题来测试利用余弦函数来动态调整加速因子的有效性。表1给出3个Benchmark函数的定义和搜索空间,其中Sphere函数是单峰函数,其余两个函数均为经典的多峰函数,它们的理论最小值均为0,收敛于(0,0,…,0)。

用两种加速因子策略方法与本文提出的正弦调整策略进行性能比较。方法1为标准PSO(c1=2,c2=2),方法2为线性调整加速因子策略,方法3为本文的正弦调整加速因子策略,方法2和方法3中加速因子的起始值分别为c1start=2.75, c1end=1.25, c2start=0.5, c2end=2.25。所有实验取维数D=30,种群规模m=40,最大迭代次数kmax=1000,惯性因子都随着算法迭代次数的增加从0.4线性变化到0.9[3]。考虑到算法的随机性,对每个函数每种算法都取不同随机初始群体进行了 20次试验。实验结果见表2。表中最优值、最差值、平均最优值分别是20次实验中最优适应值中最好值、最差值和平均值。

图1-图3是试验中函数极值随迭代次数变化图,图中横坐标为迭代次数,纵坐标为函数当代最好适应值的对数。

从图1-图3可以看出,本文算法在搜索初期有较快的收敛速度,搜索曲线比较平滑,在搜索末期搜索精度比较精细,算法的性能明显好于方法1和方法2,这说明本文提出的余弦函数调整加速因子,能较好地反映微粒群算法在搜索初期微粒尽可能地飞跃整个搜索空间,以期获得粒子的多样性,而在搜索末期,使微粒以较快的速度、精确地收敛于全局最优解。同时从表2实验结果可知,本文算法具有较好的平均最优值,这说明整个算法比较稳定。

4 结束语

微粒群优化算法是一种新颖的智能优化算法,本文在分析加速因子对算法性能影响的基础上,针对微粒群算法中不同搜索时期的微粒所需要的搜索能力不同,提出了一种运用余弦函数动态调整加速因子的微粒群算法。算法通过引入余弦函数来动态调整加速因子,在每次迭代中,微粒根据迭代次数的余弦变化来动态调整加速因子,有效地调节算法的全局和局部搜索能力。与其他的算法相比,测试结果表明,本文提出的算法稳定,具有较好的收敛性能。

参考文献:

[1] Kennedy J, Eberhart R C. Particle swarm optimization[C]. Proc of IEEE International Conference on Neural Networks . Piscataway : IEEE Press, 1995:1942-1948.

[2] Ratnaweera A, Halgamuge S K, Watson H C. Self-Organizing Hierarchical Particle Swarm Optimizer With Time-Varying Acceleration Coefficients[J]. IEEE Transactions on Evolutionary Computation, 2004,8(3):240-255.

[3] Shi.Y, Eberhart.R.C.A modified particle swarm optimizer[C].Proc. ofthe IEEE International Conference on Evolutionary Computation. NJ:IEEE Press,1998: 69-73.