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

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

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

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

1 萬(wàn)有引力搜索算法

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

在萬(wàn)有引力搜索算法中,粒子通過(guò)位置的移動(dòng)來(lái)尋找最優(yōu)解。隨著算法的循環(huán),粒子靠它們之間的萬(wàn)有引力在搜索空間內(nèi)不斷運(yùn)動(dòng),當(dāng)粒子移動(dòng)到最優(yōu)位置時(shí),便找到最優(yōu)解,即質(zhì)量最大粒子的位置就是最優(yōu)位置。設(shè)在一個(gè)D維搜索空間中包含n個(gè)粒子,定義第i個(gè)物體的位置

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

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

t時(shí)刻在k維上粒子i所受的合力Fij,k決定了其在第k維上的移動(dòng)方向。由牛頓萬(wàn)有引力定律可知,t時(shí)刻粒子i受到粒子j的萬(wàn)有引力

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

G(t)=G0e-αt/T

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

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

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

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

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

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

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

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

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

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

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

基于共享機(jī)制萬(wàn)有引力搜索算法的步驟如下所示:

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

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

步驟3確定小生境種群。

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

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

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

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

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

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

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

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

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

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

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

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

為了驗(yàn)證本文提出的改進(jìn)萬(wàn)有引力搜索算法的優(yōu)化性能,圖1～4直觀地給出了測(cè)試函數(shù)的優(yōu)化性能比較曲線。從圖中可以看出,改進(jìn)萬(wàn)有引力搜索算法獲得的最優(yōu)值更加接近最小值,克服了萬(wàn)有引力搜索算法的搜索精度不高且容易出現(xiàn)早熟的問(wè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給出了每個(gè)測(cè)試函數(shù)的平均值、標(biāo)準(zhǔn)差和最優(yōu)值,本文將依據(jù)此表的結(jié)果來(lái)比較并分析不同算法優(yōu)化性能的差異。從實(shí)驗(yàn)得出的平均值來(lái)看,改進(jìn)萬(wàn)有引力搜索算法的優(yōu)化精度更高;從標(biāo)準(zhǔn)差來(lái)看,改進(jìn)萬(wàn)有引力搜索算法的穩(wěn)定性也更好。從表2可以看出,改進(jìn)萬(wàn)有引力搜索算法在優(yōu)化精度上高于萬(wàn)有引力搜索算法。

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

函數(shù)萬(wàn)有引力搜索算法改進(jìn)萬(wàn)有引力搜索算法平均值標(biāo)準(zhǔn)差最優(yōu)值平均值標(biāo)準(zhǔn)差最優(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é)語(yǔ)

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

[1] 呂聰穎.智能優(yōu)化方法的研究及應(yīng)用[M]. 北京:中國(guó)水利水電出版社,2014.

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

[2] 劉勇,馬良.引力搜索算法及其應(yīng)用[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]. 模式識(shí)別與人工智能,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)度問(wèn)題的萬(wàn)有引力搜索算法[J].智能系統(tǒng)學(xué)報(bào),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] 陳云飛,劉玉樹(shù),范潔,等.火力優(yōu)化分配問(wèn)題的小生境遺傳螞蟻算法[J].計(jì)算機(jī)應(yīng)用,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.