一种万有引力优化算法及其收敛性分析

徐耀群，王长举

(哈尔滨商业大学计算机与信息工程学院，哈尔滨150028)

本文在分析了粒子群优化算法，万有引力及Rashedi E，Nezamabadi－pour H，Saryazdi S提出的引力搜索算法[5]的基础上，提出了一种万有引力优化算法，并与粒子群优化算法进行比较，之后又进行了收敛分析.

1 引力优化算法

引力优化算法(Universal gravitation optimization，UGO)是一种根据牛顿万有引力而提出的一种优化算法.在提出和完善引力优化算法的时候，借鉴了引力搜索算法和引力搜索算法的改进[6].前者是对每个质点都进行了计算，在速度更新的时候也用了随机因子和质点加速度俩个因子，质点的惯性质量是由适应值大小来计算的;后者在前者的基础上引入了加权值，通过改变质点的惯性质量对引力搜索算法进行的改进.在引力优化算法中，每个质点在各自的活动过程中搜索问题的解空间，并记录下已找到的最优值[7].在整个群体之中，各个质点之间存在着引力关系，找到最优点的质点会产生引力吸引其他质点向着该质点所在位置的方向飞行，找到次优点的质点会产生引力吸引其他质点向着该质点所在位置的方向飞行，找到第三优点的质点会产生引力吸引其他质点向着该质点所在位置的方向飞行，以此类推，在这种引力的作用下，质点会改变原有的飞行路线，在新的飞行中又将找到新的最优点，产生新的引力吸引其他质点，在这种迭代中，质点们将找到全局最优点.(在具体的应用中只取找到最优点的质点和找到次优点的质点，它们将对其他质点产生有效的引力.)质点之间按公式，(万有引力公式)产生引力，也就是，质点之间的万有引力等于引力常量G乘以两质点质量的乘积除以它们距离的平方.其中G代表引力常量，其值约为6.67×10－11，单位 N·m2/kg2.质点xi将按照公式(1)和(2)进行速度和位置的更新:

公式中的f1和f2分别是最优质点和次优质点对当前质点产生的引力，C1和C2为学习因子或加速常量(Learning Factor，Acceleration Constant).此外，为使质点速度不至于过大，还设置了速度上限Vmax，即公式(1)中的 V ＞Vmax时，V=Vmax;V ＜ －Vmax时，V=－Vmax.公式(1)中的第1部分为质点先前的速度;第2部分为最优质点对当前质点速度的影响;第3部分为次优质点对当前质点速度的影响.

引力优化算法的基本步骤如下:

步骤1:初始化，设定学习因子C1、C2，最大进化代数Tmax，当前的进化代数t=1:定义质点空间Rn中随机产生 m 个质点 x1，x2，…，xm，形成种群矩阵X(t);随机产生各个质点位移变化v1，v2，…，vm形成位移变化矩阵V(t).

步骤2:评价种群，计算每个质点的适应值F(Xi).

步骤3:比较质点的当前适应值F(Xi)和自身历史最优值 pbest，如果 F(Xi)优于 pbest，则置pbest为当前值F(Xi)，并置pbest的位置pbest为n维空间中的当前位置.

很多学生在参与中长跑活动后会出现一些副作用，包括胸闷、气短、脸色发白等，这些副作用让学生对中长跑活动存有一定的抵触心理。所以教师要云用合适的方法引导学生去“善后”，帮助学生去可致不良反应，这样能够让学生环节对中长跑活动的为难心理。如教师可以带领学生做一些保健按摩、放松操，适当的做一些简单的轻松的小游戏等，让学生对中长跑活动不再抵触。

步骤4:比较质点当前适应值F(Xi)与种群最优值gbest，如果 F(Xi)优于 gbest，则置 gbest为当前值F(Xi)，并置gbest的位置gbest为n维空间中的当前位置.

步骤5:按公式(1)和公式(2)更新质点的速度，并产生新种群X(t+1).

步骤6:检查评价函数值是否达到事先给定精度，若已达到或进化代数次数达到Tmax，则结束循环;否则令t+1，转步骤2.

2 引力优化算法收敛性分析

考虑全局收敛性

假设 1:f(D(z，ξ))≤f(Z)，并且如果 ξ∈S，则

假设2:对于S的任意Borel子集A，若其测度v(A) ＞0，则有

其中:μk(A)是由测度μk所得到的A的概率.

定理1:引力优化算法满足假设1.

证明:定义函数D为

其中:符号g(xi，k)表示引力优化的更新方程，具体为

其中:xi，k表示第k代时的质点位置，按照这里定义的函数D，引力优化满足假设1.

定理2:任意取ε＞0，存在N≥1，使得对于任意的 n≥N，如果选择 ω、φ1、φ2，使得 max(||α||，||β||) ＜1，则有 gn(xi，k) － gn+1(xi，k)‖ ＜ ε.证明:由于

且 X(t+1) －X(t)=V(t+1)，因此，当 max(||α||，||β||) ＜1 时，下式成立

两边取极限，从而有

3 仿真研究

3.1 实验设计

为了分析引力优化算法的性能，本文涉及了4个测试函数，如表1.通过对4个测试函数寻找最小值，可以分析本文提出的算法的优化能力.在本文的实验部分，为了减少大量的计算，而提出了此实验模型:只考虑引力最大点和引力第二大点对该质点产生有效的引力作用.通过对这三个模型的计算分析可以观察出，引力优化算法的寻优的最优值，速度，稳定性方面的寻优能力.

表1 四个标准测试函数

进行测试是求函数的最小值，种群大小为40，空间维数是10，每次测试独立运行10次.其中UGO中的引力系数Q、迭代次数Tmax、速度上限、速度下限，如表3，C1=2.05，C2=2.05，ω =0.729 8.PSO 中的学习因子 C1=2.05，C2=2.05，惯性权重为ω=0.729 8，迭代次数Tmax=1200.然后求其平均值、最大值、最小值、方差.得到各个函数分别用粒子群算法和引力优化进行优化的过程比较，得到的结果如表2，引力优化算法的参数值如表3，在引力优化算法中，随着迭代次数的增加函数适应值的变化如图1～4.在粒子群优化中，随着迭代次数的增加函数适应值的变化如图5～8.

表2 UGO与PSO性能比较

表3 函数的参数

图8 函数F4粒子群的适应值随迭代次数的变化

3.2 实验结果分析

从试验的结果看出来，UGO算法总体上看跟PSO算法的优化能力相近，在函数F1、F4中UGO稍好于 PSO，而在函数 F2、F3中 UGO表现的比PSO稍差一点.在求函数最小值的时候，UGO在一些函数中能够找到更小的最小值，找到最小值的速度也是挺快的，稳定性和求最优的能力上，还需要在以后的研究工作中继续探索和加以改进.

4 结语

本文借鉴了粒子群方法，针对粒子群早熟收敛和搜索能力差的问题，提出了引力优化该算法有着与粒子群相同的简单收敛快的优点，并对算法的收敛性进行分析.在与粒子群比较的过程中发现，该算法速度较快，对像F1、F3、F4这样的函数有着较好的寻优能力，但对像F2这样的函数经过多次运行其能找到最优的能力要比粒子群要好，但存在这不稳定性.在进一步的工作中将要调整算法，使其寻优能力更加稳定，提高其全局和局部搜索能力.

[1] EBERHART R C，KENNEDY J.Particles swarm optimization[C]//IEEE Int Conf on Neural Network，Perth，1995:1942－1948.

[2] EBERHART R C，KENNEDY J.A new optimizer using particle swarm theory[C]//The 6th Int Symposium on Micro Machine and Human Science，Nagoya，1995:39 －43.

[3] 高 浩，冷文浩，须文波.一种全局收敛的PSO算法及其收敛分析[J].控制与决策，2009，24(2):196－201.

[4] KALYAN V，LISA O，GANAPATHI K.Probabilistically driven particle swarms for optimization of multi valued discrete problems:Design an analysis[C]//Proc of IEEE Swarm Intelligence Symposium(SIS).Honolulu，2007:141－149.

[5] RASHEDI E，NEZAMABADIPOUR H，SARYAZDI S.GSA:a gravitational search algorithm[J].Information Sciences，2009，179(13):2232－2248.

[6] 徐 遥，王士同.引力搜索算法的改进[J].计算机工程与应用，2011，47(35):188－192.

[7] 许 楠，徐耀群.反三角函数混沌神经网络的模拟退火策略[J].哈尔滨商业大学学报:自然科学版，2011，27(6):814－818.