一类求解箱式约束优化问题的自适应引力搜索算法

覃　飞1,刘　杰

(1.西安科技大学 教务处，西安　710054; 2.西安科技大学 理学院，西安　710054)



一类求解箱式约束优化问题的自适应引力搜索算法

覃飞1,刘杰2

(1.西安科技大学 教务处，西安710054; 2.西安科技大学 理学院，西安710054)

为了改进引力搜索算法求解箱式约束优化问题的性能，提出了一类自适应引力搜索算法，新算法定义了算法停滞系数，当算法陷入停滞时，可以自适应的修改引力参数，帮助算法跳出停滞状态；定义了个体相似系数，当种群陷入局部最优时，通过变异策略改善种群的多样性;数值试验结果表明，新算法有效的平衡了全局开发和局部搜索能力，具有更强的全局寻优能力，适于求解复杂优化问题。

引力搜索算法；全局优化；自适应；函数优化

0　引言

基于某种自然隐喻的仿生算法近年来成为全局优化领域的热门研究方向，这些仿生算法大致可以分为两类：一类是基于自然界的生物现象所设计的算法，如模拟人类社会进化过程的遗传算法(GA)[1]、模仿鸟类觅食的粒子群算法(PSO)[2]和模拟蚁群觅食的蚁群算法(ACO)[3]；一类是模拟自然界的物理现象、定律设计的仿生算法，如模仿宇宙天体运行的中心引力算法(CFO)[4]、模拟电磁场中的吸引与排斥机制的类电磁算法(EM)[5]和模拟万有引力定律的引力搜索算法(GSA)[6]等。由于模仿物理定律所设计的算法，具有运行机制明确，运行结果稳定，受到了众多科研工作者的关注。

引力搜索算法(gravitationalsearchalgorithm,GSA)是RashediE于2009年提出的一种新型自然仿生算法[6]：将个体看作宇宙中的天体，适应度看作其质量，个体的移动服从万有引力定律，最终质量较小的个体围绕着质量较大的个体稳定运行，也就是个体最终收敛于全局最优解。由于GSA具有明确的运行机制，无论在收敛速度还是收敛精度上都优于一般的自然仿生算法。

但是，与一般的进化算法一样，随着问题复杂度的上升，GSA也易于陷入局部最优，为了改进GSA的性能，本文设计了一类自适应的引力搜索算法(adaptivegravitationalsearchalgorithm,AGSA)。通过对种群个体的历史信息的统计学习，判断当前种群是否陷入局部最优，若陷入局部最优，则对个体实施变异操作，从而增加种群的多样性，帮助种群跳出当前局部最优。

1　相关知识

1.1问题模型

本文讨论如下ND维全局优化问题

其中S是一个箱式区域

1.2引力搜索算法

在ND维搜索空间内，投放NP个个体xp=(xp,1,xp,2,...,xp,NP),p=1,2,...,NP，第p个个体在第t代根据如下公式运行：

(1)

式(1)中，G(t)表示第t代的万有引力系数，一般设置为单调递减；Mp(t)与Mq(t)表示第p个个体与第q个体的质量，由式(2)、(3)定义

(2)

(3)

则在第t代，个体p在k维上受到的合力和加速度分别为

其中：randi表示0到1之间的一个随机数。由此，第p个个体的速度和位置按照如下公式更新

(4)

(5)

2　算法改进策略

2.1参数定义

1) 算法停滞系数。算法早熟收敛的一个重要表现是当前种群最优个体长时间无法得到改善，因此为了衡量算法的进化能力，定义算法停滞系数δ：若种群最优个体适应度连续n代没有改善，则停滞系数δ=n。为了避免数值计算中的误差对种群最优个体的扰动，只有当前种群个体最优解curVal与最优个体bestVal之间的改善程度大于预期时，才认为种群最优个体得到了改善，否则认为当前种群最优个体没有得到改善。其中，改善程度定义为

2)个体相似参数。算法进化到后期，种群的多样性较差，为了衡量种群个体的相似程度，定义第p个个体与最优个体的相似参数为

(6)

从(6)式可以看出，相似参数反映了一般个体与最优个体之间各个维度上的差异，取值在0与1之间，相似参数越小，则个体与最优个体差异越大，相似参数越大，则个体与最优个体差异越小。

2.2引力系数的自适应调整

在GSA中，引力系数G控制了个体所受到的合力的大小，起着一般进化算法中步长的作用，若G较大，则算法的全局开发能力较强，易于跳出局部最优，但在一定程度上降低了算法的收敛速度；若G较小，则算法的局部搜索能力较强，易于改善当前最优解的精度，但在一定程度上增加了陷入局部最优解的可能性。因此，为了平衡算法的全局开发能力与局部搜索能力，GSA没有将G固定为常数，而是建议G的值单调递减，即算法运行的前期G的值较大，算法的全局开发能力较强，算法运行后期G的值较小，算法的局部搜索能力较强。

为了使算法根据种群进化的状态自适应的调整引力系数的G值，通过停滞系数δ对引力系数自适应调整。当算法趋于停滞时，则停滞系数δ逐渐增大，此时按照式(5)调整引力系数G的值，帮助算法增强全局开发能力，跳出局部最优，

(7)

其中：G0为初始引力系数，ω为调整参数。从式(7)可以看出，引力系数G与停滞系数δ成正比关系，算法停滞代数越多，则引力系数G越大，使算法具有较强的全局开发能力，从而跳出局部最优。若引力常数G调整后，种群的最优个体得到了改善，则停滞系数δ归零；若种群最优个体持续未得到改善，则按(7)继续增大引力系数G的值。

2.3变异策略

GSA由于在计算个体所受到的合力时，需要把当前个体与种群其余个体逐一比较，从而使种群快速向种群最优个体靠近，在加快了算法收敛速度的同时，也造成了种群多样性的下降。为了改进GSA的这一不足，本文在GSA中引入了变异策略：对种群中个体进行相似性检测，对于相似性非常大的个体则进行变异，从而增加了种群的多样性。

变异策略的具体操作为：当停滞系数超过给定的阈值后，按照式(6)计算每个个体的相似参数，选出相似度最高的m个个体按照式(8)进行变异操作:

(8)

2.4自适应引力搜索算法(self-adaptive Gravity Search Algorithm, AGSA)流程

根据2.1-2.3节算法思想，设计了一类自适应的引力搜索算法AGSA，算法流程图如图1所示。

图1　AGSA算法流程

3　数值试验及结果分析

3.1参数设置

为了验证本文提出的AGSA的有效性，选择了若干国际公认的测试函数对算法进行测试。实验环境为:Win7系统，IntelCoreCPU3.60GHz，RAM4.00GB；仿真软件为Matlab2010。

选择了4个测试函数，其中函数1、2为单峰函数，函数3、4为多峰函数[7]，测试函数具体信息见表1。所有测试函数的维数ND=30

表1　测试函数

AGSA的参数设置如下：种群个体数NP为50，算法终止条件为函数值评估次数Fval达到300 000，引力系数初始值G0为100，最优解改善程度imp阈值为0.01，停滞系数阈值为20，变异个体个数为2。选取了两个对比算法GSA[6]与DGSA[8]分别与原文献相同。每种算法独立运行50次。

表2中，Mean表示适应度的均值，Std.表示标准差；表3中，SR表示算法独立运行50次，最优解达到可接受值的成功率，Fval表示成功率为100%时函数值评估次数的平均值。对于单峰函数f1，AGSA、GSA和DGSA均表现出了较高的的寻优精度和算法执行能力，并且成功率均能达到百分之百。对于函数f2，3种算法的寻优精度没有较大的区别，但AGSA的成功率有了很大的提高，而GSA相对表现较差。对于函数f3，AGSA算法的平均值比GSA提高了3个数量级，比DGSA提高了一个数量级，同时成功率仍能保持百分之百。对于多峰函数f4，AGSA和DGSA无论在平均值还是成功率都优于GSA，但算法性能的提高没有DGSA明显。

表2　AGSA与其它算法实验结果对比

表3　AGSA与其它算法成功率对比

3.2参数的灵敏度分析

在AGSA中，最优解改善程度阈值、停滞系数阈值以及变异个体的个数的取值对算法有着重要的影响。为了分析这3个参数对AGSA稳定性的影响，以确定最佳参数设置方案，以下通过数值试验对这些参数取值变化对AGSA的影响进行详细的实验与分析。实验方案为：最优解改善程度阈值0.01，停滞系数阈值20，变异个体个数2为基准参数设置，每次仅在特定区间内改变其中某一参数，其余两个参数保持不变。以下试验中，种群个体数为50，算法停止标准为函数值评估次数达到300 000次。

3.2.1最优解改善程度阈值的灵敏度分析

最优解改善程度阈值采用了如下的参数设计方案：imp=0.005，固定值；imp=0.01，固定值；imp=0.05，固定值；imp=0.1，固定值。实验结果如表4.

从表4可以看出，当imp取较小的固定值0.005和0.01时，取得了较好的效果，但当imp取值较大时，一定程度上就降低了算法的收敛精度，尤其对复杂函数f3和f4，imp取值较大，导致算法运行后期无法有效的改进当前最优解的精度，从而不能达到最优解指定的精度，致使算法失败。因此，为了方便起见，imp的设置应该取较小的值，具体的取值可以均衡考虑算法的全局开发和局部搜索能力来确定，imp的取值范围可以在0.005～0.01之间。

表4　imp的灵敏度分析

3.2.2停滞系数阈值的灵敏度分析

停滞系数阈值采用了如下的参数设计方案：δ=10，固定值；δ=20，固定值；δ=30，固定值；δ=40，固定值。实验结果如表5。

表5　停滞系数阈值δ的灵敏度分析

从表5可以看出，停滞系数阈值δ取值较小时对AGSA算法的影响较小，这是由于算法实际运行约在200代左右，变异个体的总数也10～40之间变化，但同时还影响引力常数G的取值，若δ取值过大，间接导致引力系数过大，从而使算法运行后期不能很好地收敛到全局最优解，从而使算法失效，这在δ取值为40时得到体现，对于复杂函数f3和f4，AGSA无法得到有效结果。因此，在AGSA中，停滞系数阈值δ取值不宜过大，建议在10～20之间。

3.2.3变异个体个数m的灵敏度分析

变异个体个数采用了如下的参数设计方案：m=2，固定值；m=5，固定值；m=7，固定值；m=10，固定值。实验结果如表6。

表6　变异个体个数m的灵敏度分析

从表6可以看出，变异个体的个数m对AGSA的影响随着个数的增大而逐渐增大，即变异个体个数越大，则解的精度也越差，这是由于变异个体是选出当前种群中相似个体最高的前m个个体进行变异，在算法运行后期，种群聚集在最优解附近，变异操作可能会对当前种群中适应度最好的m个个体进行变异，如果变异个体较多的话，降低了算法的收敛速度，甚至会导致算法不收敛，这在函数f4中得到了体现。因此，变异个体的个数不宜过大，建议设置在5以内。

4　结束语

本文针对求解箱式约束条件下连续函数优化问题的GSA算法进行了改进：通过种群的进化状态，对引力系数进行自适应的调整；引入变异策略，当算法陷入停滞状态时，通过变异操作，增加种群的多样性，帮助算法跳出局部最优。数值试验表明，AGSA相比GSA和DGSA无论在寻优精度还是成功率都有所提高。由于对复杂多峰函数f4，AGSA的效果弱于DGSA，如何提高AGSA对复杂不可分多峰函数的收敛速度和收敛精度有待于进一步研究，通过灵敏度分析，对算法中最优解改善程度阈值、停滞系数的阈值和变异策略中变异个体的个数等参数的设置进行了分析，给出了这些参数设置的建议。

AGSA有效平衡了GSA的全局开发和局部搜索能力，使算法可以广泛应用在云计算资源调度、排序优化、图像识别和系统检测等需要求解复杂优化模型的工程优化问题。下一步的研究工作是结合实际问题，在满足用户需求的前提下希望能进一步提高算法的运行效率和缩短任务的执行时间。

[1]StornR,PriceK.Asimpleandefficientheuristicforglobaloptimizationovercontinuousspaces[J].JournalofGlobalOptimization, 1997, 11(4): 341-359.

[2]JingC,DavidWP.Onfastandaccurateblock-basedmotionestimationalgorithmsusingparticleswarmoptimization[J].InformationScience, 2012, 197(15): 53-64．

[3]TavaresRFN,GodlnhoMF.Anantcolonyoptimizationapproachtoapermutationalflowshopschedulingproblemwithoutsourcingallowed[J].Computers&OperationsResearch, 2011, 38(9): 1286-1293.

[4] 刘杰, 王宇平. 一种基于单纯形法的改进中心引力优化算法[J]. 浙江大学学报(工学版), 2014, 48(12): 2115-2122.

[5]BirbilSI,FangSC.Anelectromagnetism-likemechanismforglobaloptimization[J].JournalofGlobaloptimization, 2003, 25(3): 263-282.

[6]EsmatRashedi,HosseinNezamabadi-pour,SaeidSaryazdi.GSA:Agravitationalsearchalgorithm[J].InformationScience, 2009, 179: 2232-2248.

[7]QinAK,HuangVL,SuganthanPN.Differentialevolutionalgorithmwithstrategyadaptationforglobalnumericaloptimization[J].IEEETransonEvolutionaryComputation, 2009, 13(2): 398-417.

[8]LiXiangtao,YinMinghao,MaZhiqiang.Hybriddifferentialevolutionandgravitationsearchalgorithmforunconstrainedoptimization[J].InternationalJournalofPhysicalScience, 2011, 6(25): 5961-5981.

Self-adaptiveGravitationalSearchAlgorithmforBox-constrainedOptimizationProblems

QinFei1,LiuJie2

(1Dean’soffice,Xi’anUniversityofScienceandTechnology,Xi’an710054,China;2CollegeofScience,Xi’anUniversityofScienceandTechnology,Xi’an710054,China)

ToimprovetheperformanceofGravitationalSearchAlgorithm(GSA)forbox-constrainedoptimizationproblems,animprovedalgorithmbasedonself-adaptivegravitationalsearchalgorithmwasproposed.Stagnationcoefficientandsimilaritycoefficientaredefined.Whenalgorithmhasbeeninstagnationbehavior,gravitationparameterisrevisedadaptivelytojumpoutofstageofstagnation.Whenswarmfallintolocaloptimal,diversityofswarmwillbeimprovedbymutationstrategy.Thenumericalexperimentonbenchmarkfunctionsshowsthattheimprovealgorithmefficientlybalancestheexploitandexplorer,especiallysuitableforsolvinghighdimensionandmultimodalfunctionoptimizationproblem,

gravitationalsearchAlgorithm;globaloptimization;self-adaptive;functionoptimization

2015-08-03；

2015-09-16。

国家自然科学基金资助项目(11301414；11226173)。

覃飞(1979-)，男，广西桂林人，硕士，主要从事建模、优化算法方向的研究。

1671-4598(2016)01-0273-04DOI：10.16526/j.cnki.11-4762/tp.2016.01.076

TP301

A