張秀玲,臧佳音,樊紅敏,趙 亮

(1.燕山大學(xué) 河北省工業(yè)計(jì)算機(jī)控制工程重點(diǎn)實(shí)驗(yàn)室,河北 秦皇島 066004;2.國家冷軋板帶裝備及工藝工程技術(shù)研究中心 秦皇島 066004)

優(yōu)化理論的研究一直是一個(gè)非?；钴S的研究領(lǐng)域[1].它所研究的問題是在眾多方案中尋求最優(yōu)方案.人們關(guān)于優(yōu)化問題的研究工作,隨著歷史的發(fā)展不斷深入.近幾十年來,啟發(fā)式優(yōu)化算法得到了很好的發(fā)展.啟發(fā)式優(yōu)化算法通常通過模擬自然現(xiàn)象、生物種群或自然物體的運(yùn)動(dòng)規(guī)律,以達(dá)到尋優(yōu)的目的.典型的啟發(fā)式優(yōu)化算法有遺傳算法(GA)[2]、粒子群算法(PSO)[3]、人工蜂群算法(ABC)[4]等.

萬有引力搜索算法(Gravitational Search Algorithm,GSA)是Esmat Rashedi[5]等人在2009年提出的啟發(fā)式優(yōu)化算法.該算法先根據(jù)種群粒子的適應(yīng)值計(jì)算出自身質(zhì)量,然后基于萬有引力定律使種群粒子產(chǎn)生相互作用力,各個(gè)粒子被其他的粒子吸引,每個(gè)被吸引的粒子根據(jù)牛頓第二定律運(yùn)動(dòng).粒子之間的相互吸引力是種群優(yōu)化的原動(dòng)力,種群在引力作用下收斂到最優(yōu)位置,從而達(dá)到尋優(yōu)的目的.

近年來有關(guān)萬有引力搜索算法的研究正在逐步展開.文獻(xiàn)[6]將萬有引力搜索算法與支持向量機(jī)相結(jié)合,用來提高二進(jìn)制問題的分類精度.文獻(xiàn)[7]用萬有引力搜索算法來解決約束優(yōu)化問題.文獻(xiàn)[8]結(jié)合GSA與PSO的優(yōu)勢(shì)改進(jìn)萬有引力搜索算法,將其應(yīng)用到水輪機(jī)調(diào)節(jié)系統(tǒng)的參數(shù)辨識(shí).文獻(xiàn)[9]提出了一種改進(jìn)的GSA用于解決復(fù)雜作戰(zhàn)環(huán)境下的無人機(jī)航路規(guī)劃問題.文獻(xiàn)[10]提出將K-means和引力搜索相結(jié)合的算法,該算法將全局搜索能力強(qiáng)的引力搜索算法和局部搜索能力較強(qiáng)的K-means算法結(jié)合在一起,減少了引力搜索算法的運(yùn)行時(shí)間,解決了引力搜索易受初始種群影響的問題,并且避免了K-means陷入局部最優(yōu)的問題.文獻(xiàn)[11]將混沌變異添加到萬有引力搜索算法中,避免其出現(xiàn)早熟問題.

與其他智能算法類似,GSA也存在局部優(yōu)化能力差和早熟收斂等缺點(diǎn).本文在對(duì)引力搜索算法中粒子的記憶性加以改進(jìn)的基礎(chǔ)上,結(jié)合生物界中雁群的飛行特征和加權(quán)平均法,對(duì)速度公式進(jìn)行改進(jìn).為了驗(yàn)證改進(jìn)的萬有引力搜索算法(Improved Gravitational Search Algorithm,IGSA)的優(yōu)化效果,用6個(gè)基準(zhǔn)函數(shù)對(duì)其進(jìn)行測(cè)試.仿真結(jié)果顯示,改進(jìn)后的算法優(yōu)于GSA.

1 標(biāo)準(zhǔn)萬有引力搜索算法

萬有引力算法是一種基于萬有引力定律和牛頓第二定律的種群優(yōu)化算法.該算法通過種群的粒子位置移動(dòng)來尋找最優(yōu)解,即隨著算法的循環(huán),粒子靠它們之間的萬有引力在搜索空間內(nèi)不斷運(yùn)動(dòng),當(dāng)粒子移動(dòng)到最優(yōu)位置時(shí),便找到最優(yōu)解.

在牛頓萬有引力定律中,粒子之間由于萬有引力[12-13]的作用而相互吸引.兩個(gè)粒子間的萬有引力的大小與兩個(gè)粒子的慣性質(zhì)量的乘積成正比,與兩個(gè)粒子之間的歐氏距離的平方成反比.用公式表示為

(1)

式中:F表示萬有引力的大小;G表示引力常數(shù);M1和M2分別表示兩個(gè)粒子的慣性質(zhì)量;R表示兩個(gè)粒子之間的歐氏距離.

牛頓第二定律指出:當(dāng)作用到一個(gè)粒子上的力為F,那么這個(gè)粒子的加速度a依賴于作用力F和粒子的慣性質(zhì)量M.

(2)

在第t次迭代,定義第i個(gè)粒子作用在第j個(gè)粒子上的引力大小為

(3)

式中,ε是一個(gè)很小的常量,Rij=‖Xi,Xj‖表示第i個(gè)粒子和第j個(gè)粒子之間的歐式距離.G為萬有引力常數(shù)

(4)

式中,G0表示引力常數(shù)的初始值,通過α調(diào)節(jié)引力常數(shù)G的衰減速率來控制搜索的精度,T表示最大迭代次數(shù),t表示當(dāng)前迭代次數(shù).

引力和慣性質(zhì)量可以根據(jù)適應(yīng)度函數(shù)值間接計(jì)算出來.粒子的慣性質(zhì)量越大,則這個(gè)粒子所代表的優(yōu)化問題的解越好.這意味著越好的粒子吸引力越大,移動(dòng)速度越慢.假設(shè)引力和慣性質(zhì)量相等,則慣性質(zhì)量的值可以通過對(duì)應(yīng)適應(yīng)值被計(jì)算出來.通過以下的公式計(jì)算引力和慣性質(zhì)量:

其中,fitnessi(t)表示粒子i在t時(shí)刻的適應(yīng)值,對(duì)于求最小值問題,worst(t)和best(t)定義如下:

對(duì)于求最大值問題,worst(t)和best(t)定義如下:

在第d維空間上作用在第i個(gè)粒子的總的作用力來自其他所有粒子的作用力總和:

(12)

根據(jù)運(yùn)動(dòng)法則,粒子i在第d維空間上的加速度為

(13)

對(duì)于每一次的迭代過程,粒子都會(huì)更新它的速度和位置:

速度和位置更新后,進(jìn)行下一個(gè)迭代直至最大迭代次數(shù).

2 改進(jìn)的萬有引力搜索算法

2.1 基于群體信息共享的萬有引力搜索算法

文獻(xiàn)[9]通過引入PSO算法中的記憶和群體交流來改進(jìn)GSA,改進(jìn)后的空間搜索方法按照新的策略,既遵守運(yùn)動(dòng)定律,又加入記憶和群體信息交流.新的速度更新公式定義如下:

2.2 改進(jìn)的萬有引力搜索算法

在自然界中,雁群以“人”字或“一”字形飛行,其飛行方式非常高效,比孤雁單飛增加了71%的飛行距離.雁群飛行時(shí),頭雁扇動(dòng)雙翼產(chǎn)生尾渦,后面所有尾隨的同伴可以借力飛行,所以頭雁最為辛苦,雁群由最強(qiáng)壯的大雁作為頭雁,其他大雁依次向后排.

這就是根據(jù)雁群飛行的特征對(duì)GSA全局極值的改進(jìn),速度更新公式為

在雁群飛行過程中,人們認(rèn)為頭雁只依靠自身經(jīng)驗(yàn)進(jìn)行決策,而后面的大雁不僅要依靠自身經(jīng)驗(yàn)(個(gè)體極值),而且要借鑒其他大雁的經(jīng)驗(yàn),以其當(dāng)前適應(yīng)值作為借鑒的權(quán)重,因?yàn)楫?dāng)前適應(yīng)值代表了其當(dāng)前狀態(tài).因此將除了頭雁之外的每只大雁的個(gè)體極值變換為所有個(gè)體極值Pi與其當(dāng)前適應(yīng)值f(Xi)的加權(quán)平均,公式如下:

(18)

(19)

2.3 IGSA的優(yōu)化步驟

(1) 初始化N個(gè)質(zhì)點(diǎn)的位置.

(2) 計(jì)算N個(gè)質(zhì)點(diǎn)的適應(yīng)度值.

(3) 更新個(gè)體極值及歷史最優(yōu)適應(yīng)值:即將第i個(gè)粒子的當(dāng)前適應(yīng)值與該粒子個(gè)體極值的適應(yīng)值(即該粒子的歷史最優(yōu)適應(yīng)值)進(jìn)行比較.若前者優(yōu),則更新個(gè)體極值和歷史最優(yōu)適應(yīng)值;否則保持個(gè)體極值和歷史最優(yōu)適應(yīng)值不變.

(4) 更新萬有引力常數(shù)G,計(jì)算各質(zhì)點(diǎn)的質(zhì)量M,加速度a.

(5) 質(zhì)點(diǎn)排序:將所有質(zhì)點(diǎn)按歷史最優(yōu)適應(yīng)值排序,選出歷史最優(yōu)適應(yīng)值最好的質(zhì)點(diǎn)作為頭雁,其他質(zhì)點(diǎn)依次向后排.

(6) 計(jì)算新的個(gè)體極值: 頭雁的個(gè)體極值保持不變,用式(18)計(jì)算其他粒子的新個(gè)體極值.

(7) 根據(jù)式(19)和式(15),更新質(zhì)點(diǎn)的速度及位置.

(8) 返回步驟(2),直到滿足判斷條件為止.

圖1為改進(jìn)的萬有引力搜索算法流程圖.

圖1 IGSA的流程圖Fig.1 The flow chart of IGSA

3 仿真實(shí)驗(yàn)與結(jié)果分析

3.1 基準(zhǔn)測(cè)試函數(shù)

為了評(píng)估改進(jìn)后算法的性能,本文應(yīng)用6個(gè)基準(zhǔn)函數(shù)對(duì)算法進(jìn)行測(cè)試.表1給出了這些函數(shù)的定義式、取值范圍及最小值,其中n指函數(shù)的維數(shù).

表1 基準(zhǔn)測(cè)試函數(shù)Table 1 Benchmark test functions

表1中,F1、F2為單峰函數(shù),只有一個(gè)極值點(diǎn),它們主要用于考察算法的收斂特性并測(cè)試算法的尋優(yōu)精度.F3、F4為復(fù)雜的非線性多峰高維函數(shù),包含許多的極值點(diǎn),它們主要用于檢驗(yàn)算法是否具備避免早熟并發(fā)現(xiàn)全局最優(yōu)解的能力.F5、F6為多峰低維函數(shù),其搜索維數(shù)較低.F1～F4的維數(shù)(n)被設(shè)定為30,F5維數(shù)被設(shè)定為2,F6維數(shù)被設(shè)定為4.

3.2 仿真結(jié)果及分析

為驗(yàn)證本文提出的 IGSA的優(yōu)化性能,特將其與GSA算法進(jìn)行比較實(shí)驗(yàn).所有算法采用相同的群體規(guī)模,N均設(shè)為50,最大迭代次數(shù)均設(shè)為1 000次.

為了避免隨機(jī)性的干擾,優(yōu)化算法對(duì)單峰函數(shù)優(yōu)化30次,該30個(gè)最優(yōu)值的平均值和中間值如表2所示.其中平均值反映出了算法的優(yōu)化結(jié)果的精確度,而中值反映出解的分布情況,中值與平均值越接近說明解的分布越集中.

由表2可知,對(duì)于6個(gè)基準(zhǔn)測(cè)試函數(shù)來說,改進(jìn)的萬有引力搜索算法在優(yōu)化精度上都遠(yuǎn)遠(yuǎn)高于標(biāo)準(zhǔn)萬有引力搜索算法.

表2 基準(zhǔn)測(cè)試函數(shù)優(yōu)化結(jié)果Table 2 The results of benchmark test functions

從圖2可以看出,改進(jìn)后的算法能夠在標(biāo)準(zhǔn)算法尋優(yōu)穩(wěn)定的基礎(chǔ)上進(jìn)一步尋找最優(yōu)值,獲得的最優(yōu)值更加接近最小值,克服了萬有引力搜索算法搜索精度不高,容易出現(xiàn)早熟的問題.

圖2 基準(zhǔn)函數(shù)優(yōu)化曲線Fig.2 Optimization curves of benchmark test functions(a)—F1;(b)—F2;(c)—F3;(d)—F4;(e)—F5;(f)—F6.

4 結(jié) 論

本文介紹了萬有引力搜索算法的原理,在此基礎(chǔ)上,結(jié)合雁群飛行特征和加權(quán)平均法,對(duì)標(biāo)準(zhǔn)萬有引力搜索算法進(jìn)行改進(jìn),提出了改進(jìn)的萬有引力搜索算法IGSA.改進(jìn)的萬有引力搜索算法保持了粒子的多樣性,擴(kuò)大了搜索范圍,使算法的尋優(yōu)精度進(jìn)一步提高.為了驗(yàn)證算法的有效性,通過6個(gè)基準(zhǔn)函數(shù)對(duì)IGSA優(yōu)化能力進(jìn)行測(cè)試.與GSA算法相比,無論是針對(duì)單峰函數(shù)還是多峰函數(shù),IGSA均表現(xiàn)出更好的優(yōu)化精度,這表明本文對(duì)GSA的改進(jìn)取得了顯著的效果.

參考文獻(xiàn):

[1] 王凌.智能優(yōu)化算法及其應(yīng)用[M].北京:清華大學(xué)出版社,2001:1-5.

(Wang Ling.Intelligent Optimization Algorithms with Applications[M].Beijing: Tsinghua University Press,2001:1-5.)

[2] Tang K S,Man K F,Kwong S,et al.Genetic Algorithms and Their Applications[J].IEEE Signal Processing Magazine,1996,13 (6):22-37.

[3] Karakuzu J,Eberhart R C.Particle Swarm Optimization[C]∥Proceedings of IEEE International Conference on Neural Networks,1995,4:1942-1948.

[4] Dorigo M,Maniezzo V,Colorni A.The Ant System:Optimization by a Colony of Cooperating Agents[J].IEEE Transactions on Systems,Man,and Cybernetics:Part B,1996,26(1):29-41.

[5] Esmat R,Hossein,N,Saeid S.GSA: A Gravitational Search Algorithm[J].Information Science,2009,179(13):2232-2248.

[6] Sarafrazi S,Nezamabadi-pour H.Facing the Classification of Binary Problems with a GSA-SVM Hybrid System[J].Mathematical and Computer Modelling,2013,57(1/2):270-278.

[7] Yadav A,Deep K.Constrained Optimization Using Gravitational Search Algorithm[J].National Academy Science Letters,2013,36(5):527-534.

[8] Li Chaoshun,Zhou Jianzhong.Parameters Identification of Hydraulic Turbine Governing System Using Improved Gravitational Search Algorithm[J].Energy Conversion and Management,2011,52(1):374-381.

[9] 李沛,段海濱.基于改進(jìn)萬有引力搜索算法的無人機(jī)航路規(guī)劃[J].中國科學(xué): 技術(shù)科學(xué),2012,42(10):1130-1136.

(Li Pei,Duan Haibin.Path Planning of Unmanned Aerial Vehicle Based on Improved Gravitational Search Algorithm[J].Science China: Technological Sciences,2012,42(10):1130-1136.

[10] 劉伯穎,張素琪,張麗麗.一種引力搜索和K-means的混合聚類算法[J].河北工業(yè)大學(xué)學(xué)報(bào),2013,42(3):23-27.

(Liu Boying,Zhang Suqi,Zhang Lili.A Hybrid Clustering Algorithm Based on Gravitational Search Algorithm and K-Means[J].Journal of Heibei University of Technology,2013,42(3):23-27.

[11] Chen Zhihuan,Yuan Xiaohui,Tian Hao,et al.Improved Gravitational Search Algorithm for Parameter Identification of Water Turbine Regulation System[J].Energy Conversion and Management,2014,78:306-315.

[12] Schutz B.Gravity from the Ground Up: An Introductory Guide to Gravity and General Relativity[M].Cambridge: Cambridge University Press,2003.

[13] Holliday D,Resnick R,Walker J.Fundamentals of Physics[M].Hoboken,NJ: John Wiley and Sons,1993.