采用反向变异机制的万有引力搜索算法

陈　欣,刘　朔

(武汉轻工大学 数学与计算机学院,湖北 武汉 430023)



采用反向变异机制的万有引力搜索算法

陈欣,刘朔

(武汉轻工大学 数学与计算机学院,湖北 武汉 430023)

和许多经典的群智能算法一样，万有引力搜索算法在解决很多优化问题的时候，容易陷入局部最优解并且收敛精度不高。针对这样的情况，提出一种基于变异策略和反向评估机制的改进万有引力搜索算法。该算法通过引入反向评估机制和变异策略，显著地提高了万有引力搜索算法中粒子的局部寻优能力和全局探索能力。通过对三个标准测试函数进行仿真实验，表明其与基本的万有引力搜索算法、传统粒子群算法相比，提出的基于变异策略和反向评估机制的改进万有引力搜索算法在函数优化问题上具有更好的优化性能。

反向评估机制;变异策略;万有引力搜索算法

1　引言

万有引力搜索算法(Gravitation search algorithm,简称GSA)是2009年由伊朗学者Esmat Rashedi等人[1]提出的一种新的启发式算法，其源于对物理学中的万有引力进行模拟产生的群体智能优化算法。与粒子群算法(Particle swarm optimization，简称PSO)类似，GSA也是一种元启发算法，算法原理是将搜索粒子看作宇宙空间运转的一组物体，这组物体彼此之间通过万有引力相互作用，导致物体的运动看作是严格遵循天体动力学的规律。将适应度值看作是微粒的质量，适应度大的粒子所对应的质量就越大。因此，万有引力定律会促使物体体现出向质量较大的物体移动的趋势，从而逐渐逼近求出优化问题的最优解。随着GSA理论的不断深入发展，以及其在各个领域广泛的应用，越来越多的国内外学者开始关注GSA。文献[2-5]就给出了对传统的GSA算法的一些改进。但是，和其他全局搜索的群体智能算法一样，GSA也容易陷入局部解和优化精度不高等问题。

为了解决以上的不足，笔者对传统万有引力搜索算法做了以下两个方面的改进：一是为了使初始种群中的微粒具有更均匀的分布，在种群初始化的时候引入反向评估机制；二是为了提高迭代搜索过程中的精度，采用类似于遗传算法中交叉变异机制的策略。为了验证本算法的优化效果，通过仿真实验，利用常见的三个标准测试函数进行测试和比较。

2　传统的万有引力搜索算法

GSA算法将所有粒子当作具有质量的物体，在寻优过程中，所有粒子做着理想的无阻力运动。每个物体在其运动过程中都会受到解空间中来自其他物体的引力的影响，并且在牛顿第二运动定律的作用下，以一定的加速度向质量更大的粒子靠近。由于GSA算法中，微粒的质量是与微粒的适应度的值相关，适应度更优的粒子其质量也会更大，因此质量相对较小的粒子在朝着质量大的粒子趋近的过程中逐渐逼近所分析问题的最优解。

假设在一个D维的搜索空间中包含N个物体，则第i个物体的位置为：

2.1惯性质量计算

粒子Xi的惯性质量直接和粒子所在位置所求的适应度值有关，在时刻t时，粒子Xi的质量用Mi(t)来表示。其计算公式如下：

其中fiti(t)表示时刻t粒子Xi的适应度值。best(t)表示时刻t中的最佳解，worst(t)表示时刻t中的最差解。

2.2引力计算

时刻t，物体j在第k维上受到物体i的引力为：

其中，ε表示一个很微小的常数； Mi(t),Mj(t)分别表示物体i，物体j的质量。G(t)表示引力随宇宙时间变换的万有引力常数，它的值通常是由宇宙的真实年龄所决定的，随着宇宙年龄的增大，它的值反而会变小，具体如下式：

通常G0=100,a=20。而Rij(t)表示物体i和物体j的欧氏距离，具体如下式：

Rij(t)=‖Xi(t),Xj(t)‖2

因此在时刻t，第k维上作用于微粒Xi的作用力总和等于其他所有物体对其作用之和。其计算公式如下所示：

2.3位置更新

根据牛顿第二运动定律，物体受到外力的作用就会产生加速度，因此当粒子受到其他粒子的引力作用后也会产生加速度。根据以上的分析，物体i在第k维上获得的加速度为其作用力与惯性质量的比值。具体如下式表示：

在每一次迭代过程中，根据得到的加速度来更新物体i的速度和位置，其更新公式如下：

3　基于反向变异机制的万有引力搜索算法

3.1采用反向评估机制的种群初始化和更新

与许多群体智能算法一样，种群中微粒的初始位置对算法整体的运行起到非常重要的作用。为了使初始种群的微粒位置具有更好的分布性,在初始种群的分布上采用Tizhoosh提出的反向学习双向评估机制[6]。假设x∈[a,b],则它相对应的反向粒子x′=a+b-x。采用双向评估机制的种群初始化和更新的具体步骤如下：

1)随机产生N个位于D维搜索空间内的粒子的初始位置，从而构成初始种群记为IP,其中每个微粒的位置表示为：

2)遵循反向学习机制。根据初始种群IP产生相对应的反向种群EP，即X′∈EP，其中：

3)将初始种群IP与反向种群EP合并成一个容量为2N的扩展种群，将这2N的微粒所对应的适应度值按照大小进行排序，再结合下文所描述的基于变异的精英机制相结合来更新种群。反向学习机制不仅考虑初始种群而且考虑其反向种群的适应度值，这种机制实际上是一种双向评估机制，这种机制使得微粒的搜索范围更加均匀，搜寻到全局最优解的几率变得更大。

3.2基于变异策略的优化

为了避免算法陷入局部最优解，张维平等人[7]曾经提出一种基于传统精英策略的优化方法，但是其方法仍然具有一定的局限性。笔者提出一种类似遗传算法的变异机制的精英策略。首先根据传统的引力搜索算法计算出各个微粒的适应度值，并且完成微粒位置的更新。此时在该轮迭代结束后，将2N个粒子的适应度值进行排序，记录下此时刻最好的适应度值和对应的微粒位置Xbest(t)，并且选取适应度最差的10%的微粒进行进化变异操作。之所以选取适应度排在最后10%的微粒进行进化变异操作，是因为在传统的引力搜索算法中，随着物体之间的引力作用，一方面对于所有的微粒而言已经体现出向当前最优解靠近的趋势，另一方面对于那些适应度比较差的微粒而言，应该只是在一部分的维度上体现出与当前最优解有较大的差距，在另一些维度上则相差无几。在其他的一些群体智能算法中，也经常出现这种情况，为了克服这种情况，借鉴遗传算法中的对若干个基因片段进行突变的变异操作。传统的遗传算法，是在保留了父代优良基因的情况下，对个别基因片段产生变异，在变异基因片段的选择上仍然具有一定的盲目性。而笔者提出的基于靠近全局最优解的位置变异可以保证当前粒子以一定概率在所有维度上向当前最优解靠近，可以使得原来适应度较差的微粒经过基因突变之后向当前最优解靠拢的几率大大增加。具体的变异操作思想如下：

我们求出所有微粒和当前处于最佳位置的微粒的平均距离DT(t)，如果当前粒子Xp(t)与此时最佳的微粒位置Xbest(t)的距离小于DT,则进行局部靠近的探索阶段,，位置更新公式如下：

Xp(t+1)=(1+α*U(-0.5,0.5))Xp(t)

其中α是(0,1)之间均匀分布的随机数。如果当前粒子Xp(t)与此时最佳的微粒位置Xbest(t)的距离大于DT，则进行相对大范围的开发阶段，此时采取对当前粒子施加一定的扰动的方式来进行微粒的更新，扰动的结果是一定概率保证微粒在所有维度上靠近全局最优解。位置更新公式如下：

其中r1,r2为服从U(0,1)分布的随机数，k表示位置的第k维度，t表示当前迭代轮数，T表示最大迭代次数。变异后得到的新微粒与原个微粒进行比较，并保留适应度较好的个体。随着迭代次数的增加，扰动逐渐转移到最优个体，再通过对最优个体的扰动来与原来适应度较差而距离相对较远的微粒进行交叉变异，如此不断的扰动，可以避免种群陷入早熟而导致搜索停滞不前。

3.3算法具体步骤

Step 1:通过反向学习机制，将初始种群IP扩展成种群{IP∪EP}，并且由变异策略替换扩展种群中最后10%的微粒；

Step 2:计算各个微粒的适应度的值；

Step 3:更新G(t),Mi(t),best(t),worst(t)变量；

Step 4:计算各个维度上微粒所受的合力；

Step 5:计算各个微粒的加速度；

Step 6:更新种群内所有微粒的位置；

Step 7:通过反向学习机制，以一定的概率将初始种群IP扩展成种群{IP∪EP}，并且由变异策略替换扩展种群中最后10%的微粒；

Step 8:返回至步骤2，直到满足判断条件后停止。

4　仿真实验

为了验证本文算法的有效性，选取了三个标准测试函数[8]与传统粒子群算法(PSO)和传统引力搜索算法(GSA)来进行仿真实验的对比。实验函数选取如表1所示。

表1三个标准测试函数

函数搜索空间最优值Ackley[-32,32]0Rastrigrin[-5.12,5.12]0Schaffer[-10,10]0

在仿真实验中，为了消除偶然性的影响，每个算法均独立运行30次，维度选择为30维，记Ackley函数为f1，Rastrigrin函数为f2，Schaffer函数为f3，其平均最佳适应度的结果如表2所示：

表2仿真实验结果

函数传统PSO算法传统GSA算法本文算法f10.00353127-0.00539183-0.00043771f20.000440800.335271360.00034647f30.030340230.073463300.00013073

为了分析几种算法的动态收敛情况，图1，图2，图3给出了传统PSO算法、传统GSA算法和本文算法在几个典型测试函数上的收敛曲线。

图1　Ackley函数图

图2　Rastrigrin函数图

图3　Schaffer函数图

从图1可以看出，对于多峰值Ackley函数，本文算法与传统PSO算法和传统GSA算法相比，优势是比较明显，具有更快的收敛速度和收敛精度；从图2可以看出，对于多峰值Rastrigrin函数，本文算法比传统PSO算法具有明显优势，在算法初期具有更好的收敛速度，在算法后期具有更好的收敛精度。与传统GSA算法相比，具有更好的稳定性；从图3可以看出，传统PSO算法掉入了局部收敛的陷阱，而本文则具有明显的更准确的收敛精度。与传统的GSA算法相比，本文算法的收敛速度也有了明显的提高。

5　结束语

针对传统引力搜索算法GSA在函数优化过程中容易出现早熟的问题，笔者提出一种基于变异策略和双向评估机制的改进万有引力搜索算法。该算法在演化过程中以一定的概率生成反向种群，在双向评估机制下对适应度较低的个体进行位置变异，并且通过与当前种群进行比较，保证最优个体进入下一代种群。并且通过选取若干个标准测试函数，将本文算法与传统粒子群算法和传统引力搜索算法相比较。实验结果表明，本文算法在收敛速度和寻优精度上具有更大的优势。

[1]Rashedi E, Nezamabadi-pour H, Saryazdi S.GSA:A Gravitational search algorithm[J].Information Sciences,2009,179(13):2232-2248.

[2]王彩霞.基于改进引力搜索的混合K-调和均值聚类算法研究[J].计算机应用研究,2016,33(1):118-121.

[3]覃飞.一类求解箱式约束优化问题的自适应引力搜索算法[J].计算机测量与控制,2016,24(1):273-276.

[4]杨青,张金格,吉孟然.万有引力搜索算法改进及仿真验证[J].沈阳理工大学学报,2015,34(6):66-71.

[5]董新燕,丁学明,王健.基于改进的引力搜索算法的T-S模型辨识[J].电子科技,2015,28(11):16-20.

[6]Tizhoosh H R.Opposition-based learning：a new scheme for machine intelligence[C].Int.Conf.on Computational Intelligence for Modeling Control and Automation-CIMCA 2005.Vienna，Austria,2005,(1):695-701.

[7]张维平,任雪飞,李国强,等.改进的万有引力搜索算法在函数优化中的作用[J].计算机应用,2013,33(5):1317-1320.

[8]马力，刘丽涛.万有引力搜索算法的分析与改进[J].微电子学与计算机,2015,32(9):76-80.

Improvement of universal gravitation search algorithm based on reverse evaluation mechanism

CHENXin1,LIUShuo2

(School of Mathematics and Computer Science, Wuhan Polytechnic University,Wuhan 430023,China)

Like many of the classic swarm intelligence algorithm, gravitational search algorithm is easy to fall into local optimal solution and convergence precision that is not high in solving many optimization problems.In this situation, this paper proposes an improved universal gravitation search algorithm based on reverse evaluation mechanism. The local optimization ability and the global exploration ability of the particle in the gravitational search algorithm are significantly improved by introducing the reverse evaluation mechanism and variation strategy.Simulation experiment of three standard test functions,show that improvement of universal gravitation search algorithm based on reverse evaluation mechanism on this paper has better functions in function optimization problem，compared with basic gravity search algorithm and the traditional particle swarm algorithm.

reverse evaluation mechanism; mutation strategy;gravitation search algorithm

2016-03-24.

2016-04-25.

陈欣(1978-),男,讲师,E-mail:2924892402@qq.com.

2095-7386(2016)03-0060-04

10.3969/j.issn.2095-7386.2016.03.011

TP 391

A