萬有引力搜索算法的改進

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

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

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

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

1 萬有引力搜索算法

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

在萬有引力搜索算法中,粒子通過位置的移動來尋找最優(yōu)解。隨著算法的循環(huán),粒子靠它們之間的萬有引力在搜索空間內(nèi)不斷運動,當粒子移動到最優(yōu)位置時,便找到最優(yōu)解,即質(zhì)量最大粒子的位置就是最優(yōu)位置。設(shè)在一個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上的慣性質(zhì)量,Mj(t)表示作用在粒子j上的慣性質(zhì)量;G(t)代表引力常量。隨著宇宙實際年齡的變化G(t)會發(fā)生相應變化,具體關(guān)系如下所示:

G(t)=G0e-αt/T

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

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

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

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

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

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

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

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

2 改進萬有引力搜索算法

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

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

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

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

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

步驟3確定小生境種群。

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

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

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

3 仿真實驗與結(jié)果分析

3.1 基準測試函數(shù)

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

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

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

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

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

表1 基準測試函數(shù)

3.3 仿真結(jié)果與分析

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

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

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

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

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

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

函數(shù)萬有引力搜索算法改進萬有引力搜索算法平均值標準差最優(yōu)值平均值標準差最優(yōu)值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 結(jié)語

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

[1] 呂聰穎.智能優(yōu)化方法的研究及應用[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] 金林鵬,李均利,魏平,等.用于函數(shù)優(yōu)化的最大引力優(yōu)化算法[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] 谷文祥,李向濤,朱磊,等.求解流水線調(diào)度問題的萬有引力搜索算法[J].智能系統(tǒng)學報,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] 陳云飛,劉玉樹,范潔,等.火力優(yōu)化分配問題的小生境遺傳螞蟻算法[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.