覃　飛1,劉　杰

(1.西安科技大學(xué) 教務(wù)處，西安　710054; 2.西安科技大學(xué) 理學(xué)院，西安　710054)

?

一類求解箱式約束優(yōu)化問題的自適應(yīng)引力搜索算法

覃飛1,劉杰2

(1.西安科技大學(xué) 教務(wù)處，西安710054; 2.西安科技大學(xué) 理學(xué)院，西安710054)

為了改進(jìn)引力搜索算法求解箱式約束優(yōu)化問題的性能，提出了一類自適應(yīng)引力搜索算法，新算法定義了算法停滯系數(shù)，當(dāng)算法陷入停滯時(shí)，可以自適應(yīng)的修改引力參數(shù)，幫助算法跳出停滯狀態(tài)；定義了個(gè)體相似系數(shù)，當(dāng)種群陷入局部最優(yōu)時(shí)，通過變異策略改善種群的多樣性;數(shù)值試驗(yàn)結(jié)果表明，新算法有效的平衡了全局開發(fā)和局部搜索能力，具有更強(qiáng)的全局尋優(yōu)能力，適于求解復(fù)雜優(yōu)化問題。

引力搜索算法；全局優(yōu)化；自適應(yīng)；函數(shù)優(yōu)化

0　引言

基于某種自然隱喻的仿生算法近年來成為全局優(yōu)化領(lǐng)域的熱門研究方向，這些仿生算法大致可以分為兩類：一類是基于自然界的生物現(xiàn)象所設(shè)計(jì)的算法，如模擬人類社會(huì)進(jìn)化過程的遺傳算法(GA)[1]、模仿鳥類覓食的粒子群算法(PSO)[2]和模擬蟻群覓食的蟻群算法(ACO)[3]；一類是模擬自然界的物理現(xiàn)象、定律設(shè)計(jì)的仿生算法，如模仿宇宙天體運(yùn)行的中心引力算法(CFO)[4]、模擬電磁場(chǎng)中的吸引與排斥機(jī)制的類電磁算法(EM)[5]和模擬萬有引力定律的引力搜索算法(GSA)[6]等。由于模仿物理定律所設(shè)計(jì)的算法，具有運(yùn)行機(jī)制明確，運(yùn)行結(jié)果穩(wěn)定，受到了眾多科研工作者的關(guān)注。

引力搜索算法(gravitationalsearchalgorithm,GSA)是RashediE于2009年提出的一種新型自然仿生算法[6]：將個(gè)體看作宇宙中的天體，適應(yīng)度看作其質(zhì)量，個(gè)體的移動(dòng)服從萬有引力定律，最終質(zhì)量較小的個(gè)體圍繞著質(zhì)量較大的個(gè)體穩(wěn)定運(yùn)行，也就是個(gè)體最終收斂于全局最優(yōu)解。由于GSA具有明確的運(yùn)行機(jī)制，無論在收斂速度還是收斂精度上都優(yōu)于一般的自然仿生算法。

但是，與一般的進(jìn)化算法一樣，隨著問題復(fù)雜度的上升，GSA也易于陷入局部最優(yōu)，為了改進(jìn)GSA的性能，本文設(shè)計(jì)了一類自適應(yīng)的引力搜索算法(adaptivegravitationalsearchalgorithm,AGSA)。通過對(duì)種群個(gè)體的歷史信息的統(tǒng)計(jì)學(xué)習(xí)，判斷當(dāng)前種群是否陷入局部最優(yōu)，若陷入局部最優(yōu)，則對(duì)個(gè)體實(shí)施變異操作，從而增加種群的多樣性，幫助種群跳出當(dāng)前局部最優(yōu)。

1　相關(guān)知識(shí)

1.1問題模型

本文討論如下ND維全局優(yōu)化問題

其中S是一個(gè)箱式區(qū)域

1.2引力搜索算法

在ND維搜索空間內(nèi)，投放NP個(gè)個(gè)體xp=(xp,1,xp,2,...,xp,NP),p=1,2,...,NP，第p個(gè)個(gè)體在第t代根據(jù)如下公式運(yùn)行：

(1)

式(1)中，G(t)表示第t代的萬有引力系數(shù)，一般設(shè)置為單調(diào)遞減；Mp(t)與Mq(t)表示第p個(gè)個(gè)體與第q個(gè)體的質(zhì)量，由式(2)、(3)定義

(2)

(3)

則在第t代，個(gè)體p在k維上受到的合力和加速度分別為

其中：randi表示0到1之間的一個(gè)隨機(jī)數(shù)。由此，第p個(gè)個(gè)體的速度和位置按照如下公式更新

(4)

(5)

2　算法改進(jìn)策略

2.1參數(shù)定義

1) 算法停滯系數(shù)。算法早熟收斂的一個(gè)重要表現(xiàn)是當(dāng)前種群最優(yōu)個(gè)體長(zhǎng)時(shí)間無法得到改善，因此為了衡量算法的進(jìn)化能力，定義算法停滯系數(shù)δ：若種群最優(yōu)個(gè)體適應(yīng)度連續(xù)n代沒有改善，則停滯系數(shù)δ=n。為了避免數(shù)值計(jì)算中的誤差對(duì)種群最優(yōu)個(gè)體的擾動(dòng)，只有當(dāng)前種群個(gè)體最優(yōu)解curVal與最優(yōu)個(gè)體bestVal之間的改善程度大于預(yù)期時(shí)，才認(rèn)為種群最優(yōu)個(gè)體得到了改善，否則認(rèn)為當(dāng)前種群最優(yōu)個(gè)體沒有得到改善。其中，改善程度定義為

2)個(gè)體相似參數(shù)。算法進(jìn)化到后期，種群的多樣性較差，為了衡量種群個(gè)體的相似程度，定義第p個(gè)個(gè)體與最優(yōu)個(gè)體的相似參數(shù)為

(6)

從(6)式可以看出，相似參數(shù)反映了一般個(gè)體與最優(yōu)個(gè)體之間各個(gè)維度上的差異，取值在0與1之間，相似參數(shù)越小，則個(gè)體與最優(yōu)個(gè)體差異越大，相似參數(shù)越大，則個(gè)體與最優(yōu)個(gè)體差異越小。

2.2引力系數(shù)的自適應(yīng)調(diào)整

在GSA中，引力系數(shù)G控制了個(gè)體所受到的合力的大小，起著一般進(jìn)化算法中步長(zhǎng)的作用，若G較大，則算法的全局開發(fā)能力較強(qiáng)，易于跳出局部最優(yōu)，但在一定程度上降低了算法的收斂速度；若G較小，則算法的局部搜索能力較強(qiáng)，易于改善當(dāng)前最優(yōu)解的精度，但在一定程度上增加了陷入局部最優(yōu)解的可能性。因此，為了平衡算法的全局開發(fā)能力與局部搜索能力，GSA沒有將G固定為常數(shù)，而是建議G的值單調(diào)遞減，即算法運(yùn)行的前期G的值較大，算法的全局開發(fā)能力較強(qiáng)，算法運(yùn)行后期G的值較小，算法的局部搜索能力較強(qiáng)。

為了使算法根據(jù)種群進(jìn)化的狀態(tài)自適應(yīng)的調(diào)整引力系數(shù)的G值，通過停滯系數(shù)δ對(duì)引力系數(shù)自適應(yīng)調(diào)整。當(dāng)算法趨于停滯時(shí)，則停滯系數(shù)δ逐漸增大，此時(shí)按照式(5)調(diào)整引力系數(shù)G的值，幫助算法增強(qiáng)全局開發(fā)能力，跳出局部最優(yōu)，

(7)

其中：G0為初始引力系數(shù)，ω為調(diào)整參數(shù)。從式(7)可以看出，引力系數(shù)G與停滯系數(shù)δ成正比關(guān)系，算法停滯代數(shù)越多，則引力系數(shù)G越大，使算法具有較強(qiáng)的全局開發(fā)能力，從而跳出局部最優(yōu)。若引力常數(shù)G調(diào)整后，種群的最優(yōu)個(gè)體得到了改善，則停滯系數(shù)δ歸零；若種群最優(yōu)個(gè)體持續(xù)未得到改善，則按(7)繼續(xù)增大引力系數(shù)G的值。

2.3變異策略

GSA由于在計(jì)算個(gè)體所受到的合力時(shí)，需要把當(dāng)前個(gè)體與種群其余個(gè)體逐一比較，從而使種群快速向種群最優(yōu)個(gè)體靠近，在加快了算法收斂速度的同時(shí)，也造成了種群多樣性的下降。為了改進(jìn)GSA的這一不足，本文在GSA中引入了變異策略：對(duì)種群中個(gè)體進(jìn)行相似性檢測(cè)，對(duì)于相似性非常大的個(gè)體則進(jìn)行變異，從而增加了種群的多樣性。

變異策略的具體操作為：當(dāng)停滯系數(shù)超過給定的閾值后，按照式(6)計(jì)算每個(gè)個(gè)體的相似參數(shù)，選出相似度最高的m個(gè)個(gè)體按照式(8)進(jìn)行變異操作:

(8)

2.4自適應(yīng)引力搜索算法(self-adaptive Gravity Search Algorithm, AGSA)流程

根據(jù)2.1-2.3節(jié)算法思想，設(shè)計(jì)了一類自適應(yīng)的引力搜索算法AGSA，算法流程圖如圖1所示。

圖1　AGSA算法流程

3　數(shù)值試驗(yàn)及結(jié)果分析

3.1參數(shù)設(shè)置

為了驗(yàn)證本文提出的AGSA的有效性，選擇了若干國(guó)際公認(rèn)的測(cè)試函數(shù)對(duì)算法進(jìn)行測(cè)試。實(shí)驗(yàn)環(huán)境為:Win7系統(tǒng)，IntelCoreCPU3.60GHz，RAM4.00GB；仿真軟件為Matlab2010。

選擇了4個(gè)測(cè)試函數(shù)，其中函數(shù)1、2為單峰函數(shù)，函數(shù)3、4為多峰函數(shù)[7]，測(cè)試函數(shù)具體信息見表1。所有測(cè)試函數(shù)的維數(shù)ND=30

表1　測(cè)試函數(shù)

AGSA的參數(shù)設(shè)置如下：種群個(gè)體數(shù)NP為50，算法終止條件為函數(shù)值評(píng)估次數(shù)Fval達(dá)到300 000，引力系數(shù)初始值G0為100，最優(yōu)解改善程度imp閾值為0.01，停滯系數(shù)閾值為20，變異個(gè)體個(gè)數(shù)為2。選取了兩個(gè)對(duì)比算法GSA[6]與DGSA[8]分別與原文獻(xiàn)相同。每種算法獨(dú)立運(yùn)行50次。

表2中，Mean表示適應(yīng)度的均值，Std.表示標(biāo)準(zhǔn)差；表3中，SR表示算法獨(dú)立運(yùn)行50次，最優(yōu)解達(dá)到可接受值的成功率，F(xiàn)val表示成功率為100%時(shí)函數(shù)值評(píng)估次數(shù)的平均值。對(duì)于單峰函數(shù)f1，AGSA、GSA和DGSA均表現(xiàn)出了較高的的尋優(yōu)精度和算法執(zhí)行能力，并且成功率均能達(dá)到百分之百。對(duì)于函數(shù)f2，3種算法的尋優(yōu)精度沒有較大的區(qū)別，但AGSA的成功率有了很大的提高，而GSA相對(duì)表現(xiàn)較差。對(duì)于函數(shù)f3，AGSA算法的平均值比GSA提高了3個(gè)數(shù)量級(jí)，比DGSA提高了一個(gè)數(shù)量級(jí)，同時(shí)成功率仍能保持百分之百。對(duì)于多峰函數(shù)f4，AGSA和DGSA無論在平均值還是成功率都優(yōu)于GSA，但算法性能的提高沒有DGSA明顯。

表2　AGSA與其它算法實(shí)驗(yàn)結(jié)果對(duì)比

表3　AGSA與其它算法成功率對(duì)比

3.2參數(shù)的靈敏度分析

在AGSA中，最優(yōu)解改善程度閾值、停滯系數(shù)閾值以及變異個(gè)體的個(gè)數(shù)的取值對(duì)算法有著重要的影響。為了分析這3個(gè)參數(shù)對(duì)AGSA穩(wěn)定性的影響，以確定最佳參數(shù)設(shè)置方案，以下通過數(shù)值試驗(yàn)對(duì)這些參數(shù)取值變化對(duì)AGSA的影響進(jìn)行詳細(xì)的實(shí)驗(yàn)與分析。實(shí)驗(yàn)方案為：最優(yōu)解改善程度閾值0.01，停滯系數(shù)閾值20，變異個(gè)體個(gè)數(shù)2為基準(zhǔn)參數(shù)設(shè)置，每次僅在特定區(qū)間內(nèi)改變其中某一參數(shù)，其余兩個(gè)參數(shù)保持不變。以下試驗(yàn)中，種群個(gè)體數(shù)為50，算法停止標(biāo)準(zhǔn)為函數(shù)值評(píng)估次數(shù)達(dá)到300 000次。

3.2.1最優(yōu)解改善程度閾值的靈敏度分析

最優(yōu)解改善程度閾值采用了如下的參數(shù)設(shè)計(jì)方案：imp=0.005，固定值；imp=0.01，固定值；imp=0.05，固定值；imp=0.1，固定值。實(shí)驗(yàn)結(jié)果如表4.

從表4可以看出，當(dāng)imp取較小的固定值0.005和0.01時(shí)，取得了較好的效果，但當(dāng)imp取值較大時(shí)，一定程度上就降低了算法的收斂精度，尤其對(duì)復(fù)雜函數(shù)f3和f4，imp取值較大，導(dǎo)致算法運(yùn)行后期無法有效的改進(jìn)當(dāng)前最優(yōu)解的精度，從而不能達(dá)到最優(yōu)解指定的精度，致使算法失敗。因此，為了方便起見，imp的設(shè)置應(yīng)該取較小的值，具體的取值可以均衡考慮算法的全局開發(fā)和局部搜索能力來確定，imp的取值范圍可以在0.005～0.01之間。

表4　imp的靈敏度分析

3.2.2停滯系數(shù)閾值的靈敏度分析

停滯系數(shù)閾值采用了如下的參數(shù)設(shè)計(jì)方案：δ=10，固定值；δ=20，固定值；δ=30，固定值；δ=40，固定值。實(shí)驗(yàn)結(jié)果如表5。

表5　停滯系數(shù)閾值δ的靈敏度分析

從表5可以看出，停滯系數(shù)閾值δ取值較小時(shí)對(duì)AGSA算法的影響較小，這是由于算法實(shí)際運(yùn)行約在200代左右，變異個(gè)體的總數(shù)也10～40之間變化，但同時(shí)還影響引力常數(shù)G的取值，若δ取值過大，間接導(dǎo)致引力系數(shù)過大，從而使算法運(yùn)行后期不能很好地收斂到全局最優(yōu)解，從而使算法失效，這在δ取值為40時(shí)得到體現(xiàn)，對(duì)于復(fù)雜函數(shù)f3和f4，AGSA無法得到有效結(jié)果。因此，在AGSA中，停滯系數(shù)閾值δ取值不宜過大，建議在10～20之間。

3.2.3變異個(gè)體個(gè)數(shù)m的靈敏度分析

變異個(gè)體個(gè)數(shù)采用了如下的參數(shù)設(shè)計(jì)方案：m=2，固定值；m=5，固定值；m=7，固定值；m=10，固定值。實(shí)驗(yàn)結(jié)果如表6。

表6　變異個(gè)體個(gè)數(shù)m的靈敏度分析

從表6可以看出，變異個(gè)體的個(gè)數(shù)m對(duì)AGSA的影響隨著個(gè)數(shù)的增大而逐漸增大，即變異個(gè)體個(gè)數(shù)越大，則解的精度也越差，這是由于變異個(gè)體是選出當(dāng)前種群中相似個(gè)體最高的前m個(gè)個(gè)體進(jìn)行變異，在算法運(yùn)行后期，種群聚集在最優(yōu)解附近，變異操作可能會(huì)對(duì)當(dāng)前種群中適應(yīng)度最好的m個(gè)個(gè)體進(jìn)行變異，如果變異個(gè)體較多的話，降低了算法的收斂速度，甚至?xí)?dǎo)致算法不收斂，這在函數(shù)f4中得到了體現(xiàn)。因此，變異個(gè)體的個(gè)數(shù)不宜過大，建議設(shè)置在5以內(nèi)。

4　結(jié)束語(yǔ)

本文針對(duì)求解箱式約束條件下連續(xù)函數(shù)優(yōu)化問題的GSA算法進(jìn)行了改進(jìn)：通過種群的進(jìn)化狀態(tài)，對(duì)引力系數(shù)進(jìn)行自適應(yīng)的調(diào)整；引入變異策略，當(dāng)算法陷入停滯狀態(tài)時(shí)，通過變異操作，增加種群的多樣性，幫助算法跳出局部最優(yōu)。數(shù)值試驗(yàn)表明，AGSA相比GSA和DGSA無論在尋優(yōu)精度還是成功率都有所提高。由于對(duì)復(fù)雜多峰函數(shù)f4，AGSA的效果弱于DGSA，如何提高AGSA對(duì)復(fù)雜不可分多峰函數(shù)的收斂速度和收斂精度有待于進(jìn)一步研究，通過靈敏度分析，對(duì)算法中最優(yōu)解改善程度閾值、停滯系數(shù)的閾值和變異策略中變異個(gè)體的個(gè)數(shù)等參數(shù)的設(shè)置進(jìn)行了分析，給出了這些參數(shù)設(shè)置的建議。

AGSA有效平衡了GSA的全局開發(fā)和局部搜索能力，使算法可以廣泛應(yīng)用在云計(jì)算資源調(diào)度、排序優(yōu)化、圖像識(shí)別和系統(tǒng)檢測(cè)等需要求解復(fù)雜優(yōu)化模型的工程優(yōu)化問題。下一步的研究工作是結(jié)合實(shí)際問題，在滿足用戶需求的前提下希望能進(jìn)一步提高算法的運(yùn)行效率和縮短任務(wù)的執(zhí)行時(shí)間。

[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ìn)中心引力優(yōu)化算法[J]. 浙江大學(xué)學(xué)報(bào)(工學(xué)版), 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。

國(guó)家自然科學(xué)基金資助項(xiàng)目(11301414；11226173)。

覃飛(1979-)，男，廣西桂林人，碩士，主要從事建模、優(yōu)化算法方向的研究。

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

TP301

A