万有引力搜索算法的改进

(河海大学 理学院,江苏 南京 211100)

20世纪80年代以来,越来越多的研究人员从自然界得到启发,通过观察自然界规律来模仿生物,并提出了一个新颖的优化算法。该算法能够将复杂求解过程简单化,表现出智能特征,因此被称为智能优化算法[1-2]。与其他方法相比,智能优化算法具有较强的鲁棒性、并行性、自适应性和随机性,可以有效地解决集中控制的复杂分布式问题和传统优化方法很难解决或无法解决的问题。

万有引力搜索算法(GSA)是一种新型启发式优化算法,由Rashedi等[3]在2009年提出。该算法启蒙于自然界的物理现象,是一种基于万有引力定律和牛顿第二定律的种群优化算法。研究发现,万有引力搜索算法通过粒子之间的引力交互作用来完成最优解的寻找过程,万有引力不需要借助任何传播介质。处于搜索空间的粒子可获知全局环境的信息,这使得粒子具有很强的全局搜索能力。在对标准测试函数进行优化时,万有引力搜索算法的寻优精度和收敛速度都要明显优于粒子群优化算法(PSO)[4]和遗传算法(GA)[5]等。

然而,像其他全局搜索算法一样,万有引力搜索算法也存在一些缺点。国内外研究者对万有引力搜索算法的改进主要集中在加强该算法的局部搜索能力、提高种群的收敛速度和寻优精度等方面。金林鹏等[6]对最大粒子位置移动的原因产生质疑,借助遗传算法的思想通过对粒子交叉变异来影响最大粒子位置的变化。Kumar等[7]对万有引力搜索算法中的引力系数做了非线性的动态调整,使得算法的搜索能力得到改善。在应用方面,文献[8]中将万有引力搜索算法用于解决流水线调度问题时获得了较好的效果。文献[9]中将K-means算法和万有引力搜索算法相结合,在聚类的数据挖掘中利用新的算法解决问题。本文从理论和实验2个角度对万有引力搜索算法和改进万有引力搜索算法(IGSA)展开研究,充分验证改进万有引力搜索算法的可行性和有效性。

1 万有引力搜索算法

万有引力搜索算法的基本原理为:将探索区域中的粒子看成空间里运动的物体,任意2个物体之间是相互吸引的,并且物体会朝着质量大的物体移动,质量大的物体占据最优位置。

在万有引力搜索算法中,粒子通过位置的移动来寻找最优解。随着算法的循环,粒子靠它们之间的万有引力在搜索空间内不断运动,当粒子移动到最优位置时,便找到最优解,即质量最大粒子的位置就是最优位置。设在一个D维搜索空间中包含n个粒子,定义第i个物体的位置

Xi=(xi1,xi2,…,xik,…,xin),i=1,2,…,n

式中:xik表示第i个物体在第k维上的位置。

t时刻在k维上粒子i所受的合力Fij,k决定了其在第k维上的移动方向。由牛顿万有引力定律可知,t时刻粒子i受到粒子j的万有引力

式中:ε表示一个很小的常量;Mi(t)表示作用在粒子i上的惯性质量,Mj(t)表示作用在粒子j上的惯性质量;G(t)代表引力常量。随着宇宙实际年龄的变化G(t)会发生相应变化,具体关系如下所示:

G(t)=G0e-αt/T

式中:G0表示宇宙在最初t0时刻的万有引力常数,一般取值为100;α取值为20;T为最大迭代次数。Rij(t)表示粒子i和粒子j之间的欧式距离,如下所示:

Rij(t)=‖Xi(t)-Xj(t)‖

为了让万有引力搜索算法具有随机性的特点,通常给第k维空间作用在粒子i上万有引力的合力设定一个[0,1]内的随机数rj,定义如下所示:

根据上述所求合力以及由牛顿第二定律可知,粒子i在t时刻第k维空间上的加速度

万有引力搜索算法中引力质量和惯性质量可以根据适应度函数间接计算出来,粒子的惯性质量越大,则这个粒子所代表的优化问题的解越好。设定引力质量与惯性质量相等,粒子i的引力质量和惯性质量分别为

式中:fi(t)为t时刻粒子i的适应度函数。对于最小值问题求解,b(t)和w(t)分别定义如下:

对于最大值问题求解,b(t)和w(t)分别定义如下:

在每一次的迭代更新过程中,都将对粒子i进行速度和位置的更新,其中粒子i在t时刻第k维上的速度及位置更新公式分别为

2 改进万有引力搜索算法

在生物学中,小生境指特定环境中的一种组织结构,“物以类聚,人以群分”就是它的一种自然现象。在小生境中,同种生物之间既存在相互竞争,又存在信息交换。自然界的小生境为新物种的形成提供了可能性,是生物界保持近乎无限多样性的根本原因之一[10]。

Goldberg等[11]在1987年提出了基于共享机制的小生境实现方法,一些研究者又对其进行了改进[12-13]。这种实现方法的基本思想是:通过反映个体之间相似程度的共享函数来调节群体中个体的适应度,在粒子运动过程中,算法能够依据调整后的新适应度来进行选择运算,以维持粒子的多样性。具体的实施方法是:在每一次产生下一代之前,根据群体间的个体浓度确定小生境子种群,利用共享函数调整适应值,并惩罚其中个体浓度较大的小生境子种群。

基于共享机制万有引力搜索算法的步骤如下所示:

步骤1初始化n个粒子,将粒子随机地分布在解空间中,并给每个粒子随机赋予一个初始速度。

步骤2计算n个粒子的适应值,设置每个粒子的当前位置为最优位置,然后找出初始群体中的最佳粒子。

步骤3确定小生境种群。

步骤4按万有引力搜索算法对小生境群体进行惯性质量、引力和加速度的更新,利用共享函数调整适应值,并惩罚其中个体浓度较大的小生境种群。

步骤5更新并保存每个粒子历史最好的适应值和历史最好的位置,更新并保存全局最优值和全局最优位置。

步骤6当条件满足时结束搜索,然后输出全局历史最优值和全局历史最优位置,否则返回步骤4继续搜索。

3 仿真实验与结果分析

3.1 基准测试函数

为了验证改进算法的有效性,本文选取4个经典测试函数对万有引力搜索算法和改进万有引力搜索算法的优化性能进行测试。表1给出了这4个函数的定义式以及取值范围,其中N是指函数的维数。

表1中,Y1(x)、Y2(x)为单峰函数,只有一个极值点,它们主要用于考察算法的收敛特征并测试算法的寻优精度;Y3(x)、Y4(x)为多峰函数,包含许多个极值点,它们主要用于验证算法是否具有避免早熟并发现全局最优解的能力。

3.2 参数设置

为了评估改进万有引力算法的性能,将其与万有引力算法进行比较。为有效地减小随机干扰的影响,2个算法采用相同的群体规模,n均设为100,最大迭代次数也均设为100。

参数G0的取值为100,α的取值为20,测试函数的维数均选为3维,小生境的半径设为0.5,罚函数设为10。

表1 基准测试函数

3.3 仿真结果与分析

为了验证本文提出的改进万有引力搜索算法的优化性能,图1～4直观地给出了测试函数的优化性能比较曲线。从图中可以看出,改进万有引力搜索算法获得的最优值更加接近最小值,克服了万有引力搜索算法的搜索精度不高且容易出现早熟的问题。

图1 2种方法Y1(x)的优化性能比较Fig.1 Optimization performance comparison of Y1(x) between two methods

图2 2种方法Y2(x)的优化性能比较Fig.2 Optimization performance comparison of Y2(x) between two methods

图3 2种方法Y3(x)的优化性能比较Fig.3 Optimization performance comparison of Y3(x) between two methods

表2给出了每个测试函数的平均值、标准差和最优值,本文将依据此表的结果来比较并分析不同算法优化性能的差异。从实验得出的平均值来看,改进万有引力搜索算法的优化精度更高;从标准差来看,改进万有引力搜索算法的稳定性也更好。从表2可以看出,改进万有引力搜索算法在优化精度上高于万有引力搜索算法。

图4 2种方法Y4(x)的优化性能比较Fig.4 Optimization performance comparison of Y4(x) between two methods

函数万有引力搜索算法改进万有引力搜索算法平均值标准差最优值平均值标准差最优值Y1(x)0．0962730．213872．6705×10-50．00908480．01956101．61450×10-9Y2(x)11．99410013．968501．08444．16470005．80990000．22247Y3(x)5．8291004．734901．07023．51430002．69660000．96560Y4(x)2．7892001．079901．59611．18860000．91480000．51839

4 结语

本文介绍了万有引力搜索算法的原理,并在此基础上进行了改进,提出了改进万有引力搜索算法。给出了万有引力搜索算法寻优过程,然后通过引入小生境技术中的共享机制对万有引力搜索算法进行改进。改进万有引力搜索算法保持了粒子的多样性,扩大了搜索范围,使算法的寻优精度得到进一步提高。最后,通过4个测试函数对改进万有引力搜索算法优化能力进行测试,和万有引力搜索算法相比,无论是针对单峰函数还是多峰函数,改进万有引力搜索算法都表现出了更好的优化精度,这表明本文对万有引力搜索算法提出的改进取得了显著效果。

[1] 吕聪颖.智能优化方法的研究及应用[M]. 北京:中国水利水电出版社,2014.

LÜ Congying.Research and application of intelligent optimization method [M].Beijing:China Water & Power Press,2014.

[2] 刘勇,马良.引力搜索算法及其应用[M].上海:上海人民出版社,2014.

LIU Yong,MA Liang.Gravitational search algorithm and its application [M].Shanghai:Shanghai Renmin Chubanshe,2014.

[3] RASHEDI E,NEZAMABADI-POUR H,SARYAZDI S.GSA:a gravitational search algorithm[J]. Information Sciences,2009,179(13):2232-2248.

[4] KENNEDY J,EBERHART R C.Particle swarm optimization[C]//Proceedings of IEEE International Conference on Neural Networks.Perth:IEEE,1995:1942-1948.

[5] HOLLAND J H.Adaptation in natural and artificial systems[M].Ann Arbor:MIT Press,1975.

[6] 金林鹏,李均利,魏平,等.用于函数优化的最大引力优化算法[J]. 模式识别与人工智能,2010,23(5):653-662.

JIN Linpeng,LI Junli,WEI Ping,et al.Maximum gravitational optimization algorithm for function optimization[J].Pattern Recognition and Artificial Intelligence,2010,23(5):653-662.

[7] KUMAR J V,KUMAR D M V,EDUKONDALU K. Strategic bidding using fuzzy adaptive gravitational search algorithm in a pool based electricity market[J]. Applied Soft Computing,2013,13(5):2445-2455.

[8] 谷文祥,李向涛,朱磊,等.求解流水线调度问题的万有引力搜索算法[J].智能系统学报,2010,5(5):411-418.

GU Wenxiang,LI Xiangtao,ZHU Lei,et al.A gravitational search algorithm for flow shop scheduling[J].CAAI Transactions on Intelligent System,2010,5(5):411-418.

[9] HATAMLOU A,ABDULLAH S,NEZAMABADI-POUR H. A combined approach for clustering based onK-means and gravitational search algorithms[J]. Swarm and Evolutionary Computation,2012,6:47-52.

[10] 陈云飞,刘玉树,范洁,等.火力优化分配问题的小生境遗传蚂蚁算法[J].计算机应用,2005,25(1):206-209.

CHEN Yunfei,LIU Yushu,FAN Jie,et al.Niche-based genetic & ant colony optimization algorithm for generalized assignment problem[J].Journal of Computer Application,2005,25(1):206-209.

[11] GOLDBERG D E,RICHARDSON J.Genetic algorithms with sharing for multimodal function optimization[C]// International Conference on Genetic Algorithms and Their Application.[S.l.]:Lawrence Erlbaum Associates Inc.,1987:27-36.

[12] CIOPPA A D,STEFANO C D,MARCELLI A. On the role of population size and niche radius in fitness sharing[J]. IEEE Transactions of Evolutionary Computation,2004,8(6):580-592.

[13] JEONGHW M,ANDREAS A L. A hybrid sequential niche algorithm for optimal engineering design with solution multiplicity[J]. Computers & Chemical Engingeering,2009,33(7):1261-1271.