萬有引力搜索算法的改進

(河海大學 理學院,江蘇 南京 211100)

20世紀80年代以來,越來越多的研究人員從自然界得到啟發,通過觀察自然界規律來模仿生物,并提出了一個新穎的優化算法。該算法能夠將復雜求解過程簡單化,表現出智能特征,因此被稱為智能優化算法[1-2]。與其他方法相比,智能優化算法具有較強的魯棒性、并行性、自適應性和隨機性,可以有效地解決集中控制的復雜分布式問題和傳統優化方法很難解決或無法解決的問題。

萬有引力搜索算法(GSA)是一種新型啟發式優化算法,由Rashedi等[3]在2009年提出。該算法啟蒙于自然界的物理現象,是一種基于萬有引力定律和牛頓第二定律的種群優化算法。研究發現,萬有引力搜索算法通過粒子之間的引力交互作用來完成最優解的尋找過程,萬有引力不需要借助任何傳播介質。處于搜索空間的粒子可獲知全局環境的信息,這使得粒子具有很強的全局搜索能力。在對標準測試函數進行優化時,萬有引力搜索算法的尋優精度和收斂速度都要明顯優于粒子群優化算法(PSO)[4]和遺傳算法(GA)[5]等。

然而,像其他全局搜索算法一樣,萬有引力搜索算法也存在一些缺點。國內外研究者對萬有引力搜索算法的改進主要集中在加強該算法的局部搜索能力、提高種群的收斂速度和尋優精度等方面。金林鵬等[6]對最大粒子位置移動的原因產生質疑,借助遺傳算法的思想通過對粒子交叉變異來影響最大粒子位置的變化。Kumar等[7]對萬有引力搜索算法中的引力系數做了非線性的動態調整,使得算法的搜索能力得到改善。在應用方面,文獻[8]中將萬有引力搜索算法用于解決流水線調度問題時獲得了較好的效果。文獻[9]中將K-means算法和萬有引力搜索算法相結合,在聚類的數據挖掘中利用新的算法解決問題。本文從理論和實驗2個角度對萬有引力搜索算法和改進萬有引力搜索算法(IGSA)展開研究,充分驗證改進萬有引力搜索算法的可行性和有效性。

1 萬有引力搜索算法

萬有引力搜索算法的基本原理為:將探索區域中的粒子看成空間里運動的物體,任意2個物體之間是相互吸引的,并且物體會朝著質量大的物體移動,質量大的物體占據最優位置。

在萬有引力搜索算法中,粒子通過位置的移動來尋找最優解。隨著算法的循環,粒子靠它們之間的萬有引力在搜索空間內不斷運動,當粒子移動到最優位置時,便找到最優解,即質量最大粒子的位置就是最優位置。設在一個D維搜索空間中包含n個粒子,定義第i個物體的位置

Xi=(xi1,xi2,…,xik,…,xin),i=1,2,…,n

式中:xik表示第i個物體在第k維上的位置。

t時刻在k維上粒子i所受的合力Fij,k決定了其在第k維上的移動方向。由牛頓萬有引力定律可知,t時刻粒子i受到粒子j的萬有引力

式中:ε表示一個很小的常量;Mi(t)表示作用在粒子i上的慣性質量,Mj(t)表示作用在粒子j上的慣性質量;G(t)代表引力常量。隨著宇宙實際年齡的變化G(t)會發生相應變化,具體關系如下所示:

G(t)=G0e-αt/T

式中:G0表示宇宙在最初t0時刻的萬有引力常數,一般取值為100;α取值為20;T為最大迭代次數。Rij(t)表示粒子i和粒子j之間的歐式距離,如下所示:

Rij(t)=‖Xi(t)-Xj(t)‖

為了讓萬有引力搜索算法具有隨機性的特點,通常給第k維空間作用在粒子i上萬有引力的合力設定一個[0,1]內的隨機數rj,定義如下所示:

根據上述所求合力以及由牛頓第二定律可知,粒子i在t時刻第k維空間上的加速度

萬有引力搜索算法中引力質量和慣性質量可以根據適應度函數間接計算出來,粒子的慣性質量越大,則這個粒子所代表的優化問題的解越好。設定引力質量與慣性質量相等,粒子i的引力質量和慣性質量分別為

式中:fi(t)為t時刻粒子i的適應度函數。對于最小值問題求解,b(t)和w(t)分別定義如下:

對于最大值問題求解,b(t)和w(t)分別定義如下:

在每一次的迭代更新過程中,都將對粒子i進行速度和位置的更新,其中粒子i在t時刻第k維上的速度及位置更新公式分別為

2 改進萬有引力搜索算法

在生物學中,小生境指特定環境中的一種組織結構,“物以類聚,人以群分”就是它的一種自然現象。在小生境中,同種生物之間既存在相互競爭,又存在信息交換。自然界的小生境為新物種的形成提供了可能性,是生物界保持近乎無限多樣性的根本原因之一[10]。

Goldberg等[11]在1987年提出了基于共享機制的小生境實現方法,一些研究者又對其進行了改進[12-13]。這種實現方法的基本思想是:通過反映個體之間相似程度的共享函數來調節群體中個體的適應度,在粒子運動過程中,算法能夠依據調整后的新適應度來進行選擇運算,以維持粒子的多樣性。具體的實施方法是:在每一次產生下一代之前,根據群體間的個體濃度確定小生境子種群,利用共享函數調整適應值,并懲罰其中個體濃度較大的小生境子種群。

基于共享機制萬有引力搜索算法的步驟如下所示:

步驟1初始化n個粒子,將粒子隨機地分布在解空間中,并給每個粒子隨機賦予一個初始速度。

步驟2計算n個粒子的適應值,設置每個粒子的當前位置為最優位置,然后找出初始群體中的最佳粒子。

步驟3確定小生境種群。

步驟4按萬有引力搜索算法對小生境群體進行慣性質量、引力和加速度的更新,利用共享函數調整適應值,并懲罰其中個體濃度較大的小生境種群。

步驟5更新并保存每個粒子歷史最好的適應值和歷史最好的位置,更新并保存全局最優值和全局最優位置。

步驟6當條件滿足時結束搜索,然后輸出全局歷史最優值和全局歷史最優位置,否則返回步驟4繼續搜索。

3 仿真實驗與結果分析

3.1 基準測試函數

為了驗證改進算法的有效性,本文選取4個經典測試函數對萬有引力搜索算法和改進萬有引力搜索算法的優化性能進行測試。表1給出了這4個函數的定義式以及取值范圍,其中N是指函數的維數。

表1中,Y1(x)、Y2(x)為單峰函數,只有一個極值點,它們主要用于考察算法的收斂特征并測試算法的尋優精度;Y3(x)、Y4(x)為多峰函數,包含許多個極值點,它們主要用于驗證算法是否具有避免早熟并發現全局最優解的能力。

3.2 參數設置

為了評估改進萬有引力算法的性能,將其與萬有引力算法進行比較。為有效地減小隨機干擾的影響,2個算法采用相同的群體規模,n均設為100,最大迭代次數也均設為100。

參數G0的取值為100,α的取值為20,測試函數的維數均選為3維,小生境的半徑設為0.5,罰函數設為10。

表1 基準測試函數

3.3 仿真結果與分析

為了驗證本文提出的改進萬有引力搜索算法的優化性能,圖1～4直觀地給出了測試函數的優化性能比較曲線。從圖中可以看出,改進萬有引力搜索算法獲得的最優值更加接近最小值,克服了萬有引力搜索算法的搜索精度不高且容易出現早熟的問題。

圖1 2種方法Y1(x)的優化性能比較Fig.1 Optimization performance comparison of Y1(x) between two methods

圖2 2種方法Y2(x)的優化性能比較Fig.2 Optimization performance comparison of Y2(x) between two methods

圖3 2種方法Y3(x)的優化性能比較Fig.3 Optimization performance comparison of Y3(x) between two methods

表2給出了每個測試函數的平均值、標準差和最優值,本文將依據此表的結果來比較并分析不同算法優化性能的差異。從實驗得出的平均值來看,改進萬有引力搜索算法的優化精度更高;從標準差來看,改進萬有引力搜索算法的穩定性也更好。從表2可以看出,改進萬有引力搜索算法在優化精度上高于萬有引力搜索算法。

圖4 2種方法Y4(x)的優化性能比較Fig.4 Optimization performance comparison of Y4(x) between two methods

函數萬有引力搜索算法改進萬有引力搜索算法平均值標準差最優值平均值標準差最優值Y1(x)0．0962730．213872．6705×10-50．00908480．01956101．61450×10-9Y2(x)11．99410013．968501．08444．16470005．80990000．22247Y3(x)5．8291004．734901．07023．51430002．69660000．96560Y4(x)2．7892001．079901．59611．18860000．91480000．51839

4 結語

本文介紹了萬有引力搜索算法的原理,并在此基礎上進行了改進,提出了改進萬有引力搜索算法。給出了萬有引力搜索算法尋優過程,然后通過引入小生境技術中的共享機制對萬有引力搜索算法進行改進。改進萬有引力搜索算法保持了粒子的多樣性,擴大了搜索范圍,使算法的尋優精度得到進一步提高。最后,通過4個測試函數對改進萬有引力搜索算法優化能力進行測試,和萬有引力搜索算法相比,無論是針對單峰函數還是多峰函數,改進萬有引力搜索算法都表現出了更好的優化精度,這表明本文對萬有引力搜索算法提出的改進取得了顯著效果。

[1] 呂聰穎.智能優化方法的研究及應用[M]. 北京:中國水利水電出版社,2014.

Lü Congying.Research and application of intelligent optimization method [M].Beijing:China Water & Power Press,2014.

[2] 劉勇,馬良.引力搜索算法及其應用[M].上海:上海人民出版社,2014.

LIU Yong,MA Liang.Gravitational search algorithm and its application [M].Shanghai:Shanghai Renmin Chubanshe,2014.

[3] RASHEDI E,NEZAMABADI-POUR H,SARYAZDI S.GSA:a gravitational search algorithm[J]. Information Sciences,2009,179(13):2232-2248.

[4] KENNEDY J,EBERHART R C.Particle swarm optimization[C]//Proceedings of IEEE International Conference on Neural Networks.Perth:IEEE,1995:1942-1948.

[5] HOLLAND J H.Adaptation in natural and artificial systems[M].Ann Arbor:MIT Press,1975.

[6] 金林鵬,李均利,魏平,等.用于函數優化的最大引力優化算法[J]. 模式識別與人工智能,2010,23(5):653-662.

JIN Linpeng,LI Junli,WEI Ping,et al.Maximum gravitational optimization algorithm for function optimization[J].Pattern Recognition and Artificial Intelligence,2010,23(5):653-662.

[7] KUMAR J V,KUMAR D M V,EDUKONDALU K. Strategic bidding using fuzzy adaptive gravitational search algorithm in a pool based electricity market[J]. Applied Soft Computing,2013,13(5):2445-2455.

[8] 谷文祥,李向濤,朱磊,等.求解流水線調度問題的萬有引力搜索算法[J].智能系統學報,2010,5(5):411-418.

GU Wenxiang,LI Xiangtao,ZHU Lei,et al.A gravitational search algorithm for flow shop scheduling[J].CAAI Transactions on Intelligent System,2010,5(5):411-418.

[9] HATAMLOU A,ABDULLAH S,NEZAMABADI-POUR H. A combined approach for clustering based onK-means and gravitational search algorithms[J]. Swarm and Evolutionary Computation,2012,6:47-52.

[10] 陳云飛,劉玉樹,范潔,等.火力優化分配問題的小生境遺傳螞蟻算法[J].計算機應用,2005,25(1):206-209.

CHEN Yunfei,LIU Yushu,FAN Jie,et al.Niche-based genetic & ant colony optimization algorithm for generalized assignment problem[J].Journal of Computer Application,2005,25(1):206-209.

[11] GOLDBERG D E,RICHARDSON J.Genetic algorithms with sharing for multimodal function optimization[C]// International Conference on Genetic Algorithms and Their Application.[S.l.]:Lawrence Erlbaum Associates Inc.,1987:27-36.

[12] CIOPPA A D,STEFANO C D,MARCELLI A. On the role of population size and niche radius in fitness sharing[J]. IEEE Transactions of Evolutionary Computation,2004,8(6):580-592.

[13] JEONGHW M,ANDREAS A L. A hybrid sequential niche algorithm for optimal engineering design with solution multiplicity[J]. Computers & Chemical Engingeering,2009,33(7):1261-1271.