改进的万有引力搜索算法

张秀玲,臧佳音,樊红敏,赵 亮

(1.燕山大学 河北省工业计算机控制工程重点实验室,河北 秦皇岛 066004;2.国家冷轧板带装备及工艺工程技术研究中心 秦皇岛 066004)

优化理论的研究一直是一个非常活跃的研究领域[1].它所研究的问题是在众多方案中寻求最优方案.人们关于优化问题的研究工作,随着历史的发展不断深入.近几十年来,启发式优化算法得到了很好的发展.启发式优化算法通常通过模拟自然现象、生物种群或自然物体的运动规律,以达到寻优的目的.典型的启发式优化算法有遗传算法(GA)[2]、粒子群算法(PSO)[3]、人工蜂群算法(ABC)[4]等.

万有引力搜索算法(Gravitational Search Algorithm,GSA)是Esmat Rashedi[5]等人在2009年提出的启发式优化算法.该算法先根据种群粒子的适应值计算出自身质量,然后基于万有引力定律使种群粒子产生相互作用力,各个粒子被其他的粒子吸引,每个被吸引的粒子根据牛顿第二定律运动.粒子之间的相互吸引力是种群优化的原动力,种群在引力作用下收敛到最优位置,从而达到寻优的目的.

近年来有关万有引力搜索算法的研究正在逐步展开.文献[6]将万有引力搜索算法与支持向量机相结合,用来提高二进制问题的分类精度.文献[7]用万有引力搜索算法来解决约束优化问题.文献[8]结合GSA与PSO的优势改进万有引力搜索算法,将其应用到水轮机调节系统的参数辨识.文献[9]提出了一种改进的GSA用于解决复杂作战环境下的无人机航路规划问题.文献[10]提出将K-means和引力搜索相结合的算法,该算法将全局搜索能力强的引力搜索算法和局部搜索能力较强的K-means算法结合在一起,减少了引力搜索算法的运行时间,解决了引力搜索易受初始种群影响的问题,并且避免了K-means陷入局部最优的问题.文献[11]将混沌变异添加到万有引力搜索算法中,避免其出现早熟问题.

与其他智能算法类似,GSA也存在局部优化能力差和早熟收敛等缺点.本文在对引力搜索算法中粒子的记忆性加以改进的基础上,结合生物界中雁群的飞行特征和加权平均法,对速度公式进行改进.为了验证改进的万有引力搜索算法(Improved Gravitational Search Algorithm,IGSA)的优化效果,用6个基准函数对其进行测试.仿真结果显示,改进后的算法优于GSA.

1 标准万有引力搜索算法

万有引力算法是一种基于万有引力定律和牛顿第二定律的种群优化算法.该算法通过种群的粒子位置移动来寻找最优解,即随着算法的循环,粒子靠它们之间的万有引力在搜索空间内不断运动,当粒子移动到最优位置时,便找到最优解.

在牛顿万有引力定律中,粒子之间由于万有引力[12-13]的作用而相互吸引.两个粒子间的万有引力的大小与两个粒子的惯性质量的乘积成正比,与两个粒子之间的欧氏距离的平方成反比.用公式表示为

(1)

式中:F表示万有引力的大小;G表示引力常数;M1和M2分别表示两个粒子的惯性质量;R表示两个粒子之间的欧氏距离.

牛顿第二定律指出:当作用到一个粒子上的力为F,那么这个粒子的加速度a依赖于作用力F和粒子的惯性质量M.

(2)

在第t次迭代,定义第i个粒子作用在第j个粒子上的引力大小为

(3)

式中,ε是一个很小的常量,Rij=‖Xi,Xj‖表示第i个粒子和第j个粒子之间的欧式距离.G为万有引力常数

(4)

式中,G0表示引力常数的初始值,通过α调节引力常数G的衰减速率来控制搜索的精度,T表示最大迭代次数,t表示当前迭代次数.

引力和惯性质量可以根据适应度函数值间接计算出来.粒子的惯性质量越大,则这个粒子所代表的优化问题的解越好.这意味着越好的粒子吸引力越大,移动速度越慢.假设引力和惯性质量相等,则惯性质量的值可以通过对应适应值被计算出来.通过以下的公式计算引力和惯性质量:

其中,fitnessi(t)表示粒子i在t时刻的适应值,对于求最小值问题,worst(t)和best(t)定义如下:

对于求最大值问题,worst(t)和best(t)定义如下:

在第d维空间上作用在第i个粒子的总的作用力来自其他所有粒子的作用力总和:

(12)

根据运动法则,粒子i在第d维空间上的加速度为

(13)

对于每一次的迭代过程,粒子都会更新它的速度和位置:

速度和位置更新后,进行下一个迭代直至最大迭代次数.

2 改进的万有引力搜索算法

2.1 基于群体信息共享的万有引力搜索算法

文献[9]通过引入PSO算法中的记忆和群体交流来改进GSA,改进后的空间搜索方法按照新的策略,既遵守运动定律,又加入记忆和群体信息交流.新的速度更新公式定义如下:

2.2 改进的万有引力搜索算法

在自然界中,雁群以“人”字或“一”字形飞行,其飞行方式非常高效,比孤雁单飞增加了71%的飞行距离.雁群飞行时,头雁扇动双翼产生尾涡,后面所有尾随的同伴可以借力飞行,所以头雁最为辛苦,雁群由最强壮的大雁作为头雁,其他大雁依次向后排.

这就是根据雁群飞行的特征对GSA全局极值的改进,速度更新公式为

在雁群飞行过程中,人们认为头雁只依靠自身经验进行决策,而后面的大雁不仅要依靠自身经验(个体极值),而且要借鉴其他大雁的经验,以其当前适应值作为借鉴的权重,因为当前适应值代表了其当前状态.因此将除了头雁之外的每只大雁的个体极值变换为所有个体极值Pi与其当前适应值f(Xi)的加权平均,公式如下:

(18)

(19)

2.3 IGSA的优化步骤

(1) 初始化N个质点的位置.

(2) 计算N个质点的适应度值.

(3) 更新个体极值及历史最优适应值:即将第i个粒子的当前适应值与该粒子个体极值的适应值(即该粒子的历史最优适应值)进行比较.若前者优,则更新个体极值和历史最优适应值;否则保持个体极值和历史最优适应值不变.

(4) 更新万有引力常数G,计算各质点的质量M,加速度a.

(5) 质点排序:将所有质点按历史最优适应值排序,选出历史最优适应值最好的质点作为头雁,其他质点依次向后排.

(6) 计算新的个体极值: 头雁的个体极值保持不变,用式(18)计算其他粒子的新个体极值.

(7) 根据式(19)和式(15),更新质点的速度及位置.

(8) 返回步骤(2),直到满足判断条件为止.

图1为改进的万有引力搜索算法流程图.

图1 IGSA的流程图Fig.1 The flow chart of IGSA

3 仿真实验与结果分析

3.1 基准测试函数

为了评估改进后算法的性能,本文应用6个基准函数对算法进行测试.表1给出了这些函数的定义式、取值范围及最小值,其中n指函数的维数.

表1 基准测试函数Table 1 Benchmark test functions

表1中,F1、F2为单峰函数,只有一个极值点,它们主要用于考察算法的收敛特性并测试算法的寻优精度.F3、F4为复杂的非线性多峰高维函数,包含许多的极值点,它们主要用于检验算法是否具备避免早熟并发现全局最优解的能力.F5、F6为多峰低维函数,其搜索维数较低.F1～F4的维数(n)被设定为30,F5维数被设定为2,F6维数被设定为4.

3.2 仿真结果及分析

为验证本文提出的 IGSA的优化性能,特将其与GSA算法进行比较实验.所有算法采用相同的群体规模,N均设为50,最大迭代次数均设为1 000次.

为了避免随机性的干扰,优化算法对单峰函数优化30次,该30个最优值的平均值和中间值如表2所示.其中平均值反映出了算法的优化结果的精确度,而中值反映出解的分布情况,中值与平均值越接近说明解的分布越集中.

由表2可知,对于6个基准测试函数来说,改进的万有引力搜索算法在优化精度上都远远高于标准万有引力搜索算法.

表2 基准测试函数优化结果Table 2 The results of benchmark test functions

从图2可以看出,改进后的算法能够在标准算法寻优稳定的基础上进一步寻找最优值,获得的最优值更加接近最小值,克服了万有引力搜索算法搜索精度不高,容易出现早熟的问题.

图2 基准函数优化曲线Fig.2 Optimization curves of benchmark test functions(a)—F1;(b)—F2;(c)—F3;(d)—F4;(e)—F5;(f)—F6.

4 结 论

本文介绍了万有引力搜索算法的原理,在此基础上,结合雁群飞行特征和加权平均法,对标准万有引力搜索算法进行改进,提出了改进的万有引力搜索算法IGSA.改进的万有引力搜索算法保持了粒子的多样性,扩大了搜索范围,使算法的寻优精度进一步提高.为了验证算法的有效性,通过6个基准函数对IGSA优化能力进行测试.与GSA算法相比,无论是针对单峰函数还是多峰函数,IGSA均表现出更好的优化精度,这表明本文对GSA的改进取得了显著的效果.

参考文献:

[1] 王凌.智能优化算法及其应用[M].北京:清华大学出版社,2001:1-5.

(Wang Ling.Intelligent Optimization Algorithms with Applications[M].Beijing: Tsinghua University Press,2001:1-5.)

[2] Tang K S,Man K F,Kwong S,et al.Genetic Algorithms and Their Applications[J].IEEE Signal Processing Magazine,1996,13 (6):22-37.

[3] Karakuzu J,Eberhart R C.Particle Swarm Optimization[C]∥Proceedings of IEEE International Conference on Neural Networks,1995,4:1942-1948.

[4] Dorigo M,Maniezzo V,Colorni A.The Ant System:Optimization by a Colony of Cooperating Agents[J].IEEE Transactions on Systems,Man,and Cybernetics:Part B,1996,26(1):29-41.

[5] Esmat R,Hossein,N,Saeid S.GSA: A Gravitational Search Algorithm[J].Information Science,2009,179(13):2232-2248.

[6] Sarafrazi S,Nezamabadi-pour H.Facing the Classification of Binary Problems with a GSA-SVM Hybrid System[J].Mathematical and Computer Modelling,2013,57(1/2):270-278.

[7] Yadav A,Deep K.Constrained Optimization Using Gravitational Search Algorithm[J].National Academy Science Letters,2013,36(5):527-534.

[8] Li Chaoshun,Zhou Jianzhong.Parameters Identification of Hydraulic Turbine Governing System Using Improved Gravitational Search Algorithm[J].Energy Conversion and Management,2011,52(1):374-381.

[9] 李沛,段海滨.基于改进万有引力搜索算法的无人机航路规划[J].中国科学: 技术科学,2012,42(10):1130-1136.

(Li Pei,Duan Haibin.Path Planning of Unmanned Aerial Vehicle Based on Improved Gravitational Search Algorithm[J].Science China: Technological Sciences,2012,42(10):1130-1136.

[10] 刘伯颖,张素琪,张丽丽.一种引力搜索和K-means的混合聚类算法[J].河北工业大学学报,2013,42(3):23-27.

(Liu Boying,Zhang Suqi,Zhang Lili.A Hybrid Clustering Algorithm Based on Gravitational Search Algorithm and K-Means[J].Journal of Heibei University of Technology,2013,42(3):23-27.

[11] Chen Zhihuan,Yuan Xiaohui,Tian Hao,et al.Improved Gravitational Search Algorithm for Parameter Identification of Water Turbine Regulation System[J].Energy Conversion and Management,2014,78:306-315.

[12] Schutz B.Gravity from the Ground Up: An Introductory Guide to Gravity and General Relativity[M].Cambridge: Cambridge University Press,2003.

[13] Holliday D,Resnick R,Walker J.Fundamentals of Physics[M].Hoboken,NJ: John Wiley and Sons,1993.