基于高斯變異的引力搜索算法

隋永霞， 孫合明

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

萬有引力搜索算法(GSA)是2009 年由伊朗克曼大學(xué)教授Esmat Rashedi［1］等人提出的一種新的智能優(yōu)化算法，其起源于物理學(xué)中的萬有引力現(xiàn)象。牛頓萬有引力指出:在宇宙中，任意兩個粒子由于萬有引力的作用彼此相互吸引，引力的大小與粒子的質(zhì)量成正比，與它們之間的距離成反比。

目前有關(guān)GSA 的研究已經(jīng)逐漸展開。徐遙等［2］對質(zhì)量加以權(quán)值的基礎(chǔ)上對GSA 做了改進(jìn)，加大了質(zhì)量大的粒子對算法的影響。劉勇等［3］則將GSA 與混沌算法結(jié)合用于解決非線性的極大極小問題。李沛等［4］在標(biāo)準(zhǔn)的GSA 更新粒子位置的基礎(chǔ)上引入PSO 思想，將記憶速度引入GSA 中。GSA 同樣應(yīng)用到QoS 的Web 服務(wù)選擇問題［5］、解決多分類數(shù)據(jù)集中的分類問題［6］和多目標(biāo)的經(jīng)濟(jì)決策［7］等問題，但是GSA 還存在著易陷入早熟收斂和局部搜索能力不強(qiáng)［8］等問題。

文中通過提出Gaussian 變異因子的思想，較好地解決了GSA 易陷入局部最優(yōu)問題。最后通過幾個測試函數(shù)與其它算法進(jìn)行比較，有效地驗(yàn)證了文中算法的性能。

1 萬有引力搜索算法的基本思想

萬有引力是自然界中4 種基礎(chǔ)力之一，引力的作用無處不在。萬有引力搜索算法將所有的粒子都看成有質(zhì)量的物體，且其能夠做無阻尼運(yùn)動，每個粒子都會受到其它粒子萬有引力的影響，產(chǎn)生加速度使其朝向質(zhì)量大的粒子運(yùn)動。粒子的質(zhì)量與其適應(yīng)值有關(guān)，適應(yīng)值大的其慣性質(zhì)量也越大，質(zhì)量小的粒子在朝質(zhì)量大的粒子逐漸趨近的過程中逼近優(yōu)化問題的最優(yōu)解。

設(shè)在一個D 維搜索空間中［9］，有N 個粒子，第i個粒子的位置表示為

每個粒子的慣性質(zhì)量由其適應(yīng)值計算得出，慣性質(zhì)量越大的粒子越接近問題的最優(yōu)解。設(shè)Mi(t)代表第i 個粒子在t 時刻的慣性質(zhì)量，則質(zhì)量Mi(t)的計算公式表示為

其中，fiti(t)代表粒子i 在t 時刻的適應(yīng)值，best(t)表示t 時刻的最佳解，worst(t)表示t 時刻的最差解。求極小值問題時，best(t)和worst(t)的定義如下:

求極大值問題時，best(t)和worst(t)的定義如下:

在時刻t，物體j 在第d 維上受到物體i 的引力大小為

其中，Rij(t)為物體Xi與物體Xj之間的歐式距離，計算公式為

ε 是一個非常小的常量，Mpi(t)表示作用在物體i 上的慣性質(zhì)量，Maj(t)表示被作用物體j 的慣性質(zhì)量。G(t)是引力常數(shù)，其隨宇宙實(shí)際年齡的變化而變化，計算公式為

其中G(t)為t 時刻的引力常數(shù)值，α 取值為20，T 是最大迭代次數(shù)。故在t 時刻，物體i 在第d 維上所受到的合力為

其中randj為0 和1 之間的隨機(jī)數(shù)，kbest 線性地減小，使得算法在搜索空間中有最好的解的物體作用于其它物體。根據(jù)牛頓定律可知，在時刻t，物體i 在第d 維上獲得的加速度為

在每一次迭代過程中，物體根據(jù)得到的加速度更新物體i 的速度和位置，更新公式為

其中rand 是［0，1］之間的隨機(jī)數(shù)。

2 基于Gaussian 變異的引力搜索算法

2.1 基于Gaussian 變異的GSA 的思想

在萬有引力搜索算法中，假設(shè)慣性質(zhì)量最大的粒子所在的位置是所需求解的最優(yōu)解，則其它粒子所處的位置均可根據(jù)其更新公式搜索空間中新的解。基本的萬有引力搜索算法同其它智能算法一樣存在易陷入局部最優(yōu)解及早熟收斂等缺點(diǎn)，為了避免算法陷入局部最優(yōu)解，文中將進(jìn)化計算過程中的高斯變異［10］融入到引力搜索算法的位置更新中。每個粒子在其搜索區(qū)域移動到另一位置時，并不是都像基本的萬有引力搜索算法進(jìn)行速度與位置的更新，而是通過高斯變異加入了一定的不確定性。變異的計算公式為

其中mut(x)為變異后粒子的位置，x 為原先粒子的位置，高斯分布函數(shù)

這里取σ 為搜索空間中每一維長度的0.1 倍，均值μ取為0。

基于高斯變異的引力搜索算法以預(yù)定的概率來選擇變異的個體，并通過高斯分布來確定粒子的新位置。這樣在算法初期可以進(jìn)行大范圍的搜索，在算法的中后期通過逐漸減小變異的概率來改進(jìn)搜索效率，文中將算法變異概率從1 線性減小到0.1。通過動態(tài)的改變其變異概率，加快了算法的收斂速度，增加種群的多樣性，使得算法容易跳出局部最優(yōu)。通過仿真實(shí)驗(yàn)表明，基于高斯變異的引力搜索算法通過借鑒遺傳算法中的變異因子有效地改善了引力搜索算法的全局搜索能力以及加快算法的收斂速度。

2.2 基于Gaussian 變異的GSA 的實(shí)現(xiàn)流程

1)隨機(jī)初始化粒子群中的所有粒子的位置xi和速度vi，并設(shè)置迭代次數(shù)以及算法中相應(yīng)的參數(shù);

2)計算每個粒子的相應(yīng)適應(yīng)值，利用公式(7)更新引力常數(shù);

3)根據(jù)計算得出粒子的適應(yīng)值利用公式(2)，(3)，(4)計算每個粒子的慣性質(zhì)量，并且利用公式(5)～(9)計算每個粒子的加速度;

4)產(chǎn)生隨機(jī)數(shù)，若隨機(jī)數(shù)小于變異概率，則根據(jù)變異更新粒子的位置，否則利用公式(10)計算粒子的速度，然后更新粒子的位置;

5)若算法未滿足終止條件，則返回步驟2);否則，輸出該算法的最優(yōu)解。

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

為了驗(yàn)證基于變異的GSA 算法性能，選取6 個經(jīng)典的測試函數(shù)。表1 給出這些測試函數(shù)的定義以及相應(yīng)的取值范圍，其中n 代表函數(shù)的維數(shù)，6 個測試函數(shù)的最優(yōu)解均為0。

對所列的測試函數(shù)分別采取標(biāo)準(zhǔn)萬有引力搜索算法(GSA)與基于權(quán)值的引力搜索算法［2］(GSAGJ)以及基于高斯變異的引力搜索算法(QGSA)進(jìn)行測試。在所有情況下，粒子的個數(shù)為50，維數(shù)為30，最大迭代次數(shù)為1 000，3 種算法對所列測試函數(shù)均進(jìn)行20 次單獨(dú)測試，結(jié)果如表2 所示。

表1 6 個經(jīng)典測試函數(shù)Tab.1 Six classical test functions

表2 3 種算法對測試函數(shù)的平均值與標(biāo)準(zhǔn)差Tab.2 Mean and standard deviation of three algorithms for test functions

從3 種算法對所列測試函數(shù)的收斂曲線圖1 ～6 可以看出，函數(shù)F1和函數(shù)F6運(yùn)用3 種算法所求結(jié)果很相近，但是顯然QGSA 算法的收斂速度快于GSA 算法以及GSAGJ 算法。從函數(shù)F3的收斂曲線圖可以看出，QGSA 算法的收斂速度明顯快于GSA 算法。從函數(shù)F2，F(xiàn)4以及函數(shù)F5的收斂曲線圖可以看出，GSA 算法以及GSAGJ 算法很快停止進(jìn)化，這說明算法已經(jīng)陷入局部最優(yōu)解中，而對于QGSA 算法，算法的收斂速度明顯比GSA 算法及GSAGJ 算法快，并且在GSA 算法及GSAGJ算法陷入局部解之后，QGSA 算法并沒有陷入局部解，而是繼續(xù)進(jìn)化，優(yōu)化結(jié)果明顯好于其它兩種算法。

圖1 函數(shù)F1 中3 種算法優(yōu)化結(jié)果比較Fig.1 Optimization results of three algorithms in function F1

圖2 函數(shù)F2 中3 種算法優(yōu)化結(jié)果比較Fig.2 Optimization results of three algorithms in function F2

圖3 函數(shù)F3 中3 種算法優(yōu)化結(jié)果比較Fig.3 Optimization results of three algorithms in function F3

圖4 函數(shù)F4 中3 種算法優(yōu)化結(jié)果比較Fig.4 Optimization results of three algorithms in function F4

圖5 函數(shù)F5 中3 種算法優(yōu)化結(jié)果比較Fig.5 Optimization results of three algorithms in function F5

圖6 函數(shù)F6 中3 種算法算法優(yōu)化結(jié)果比較Fig.6 Optimization results of three algorithms in function F6

4 結(jié) 語

在萬有引力搜索算法的基礎(chǔ)上通過引入遺傳算法中的變異因子，提出基于高斯變異的引力搜索算法。通過3 種算法之間的數(shù)值實(shí)驗(yàn)比較看出，基于高斯變異的引力搜索算法具有較強(qiáng)的優(yōu)化能力，其收斂速度及其穩(wěn)定性都要高于基本的引力搜索算法，有效地提高了引力搜索算法的全局搜索能力，并提高了原有算法的求解精度。仿真實(shí)驗(yàn)表明，基于高斯變異的引力搜索算法在求解函數(shù)優(yōu)化問題中具有更好的優(yōu)化性能，但對某些函數(shù)優(yōu)化效果并不明顯，尚需要對其進(jìn)一步探索。

［1］Rashedi E，Nezamabadi-Pour H，Saryazdi S. GSA:a gravitational search algorithm［J］. Information Sciences，2009，179(13):2232-2248.

［2］徐遙，王士同.引力搜索算法的改進(jìn)［J］.計算機(jī)工程與應(yīng)用，2011，47(35):188-192.

XU Yao，WANG Shitong.The improvement of gravitational search algorithm［J］.Computer Engineering and Application，2011，47(35):188-192.(in Chinese)

［3］劉勇，馬良.非線性極大極小問題的混沌萬有引力搜索算法求解［J］.計算機(jī)應(yīng)用研究，2012，29(1):47-48，56.LIU Yong，MA Liang.Non-linear minimax problem of chaos gravitational search algorithm［J］.Computer Application Research，2012，29(1):47-48，56.(in Chinese)

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

LI Pei，DUAN Haibin. Unmanned aerial vehicle route planning based on improved gravitational search algorithm［J］. China Sciences:Technology Science，2012，42(10):1130-1136.(in Chinese)

［5］Zibanezhad B，Zamanifar K，Sadjady R S，et al.Applying gravitational search algorithm in the QoS-based Web service selection problem［J］.Journal of Zhejiang University Science C，2011，12(9):730-742.

［6］Bahrololoum A，Nezamabadi-Pour H，Bahrololoum H，et al. A prototype classifier based on gravitational search algorithmfJ］.Applied Soft Computing，2012，12(2):819-825.

［7］Mondal S，Bhattacharya A. Multi-objective economic emission load dispatch solution using gravitational search algorithm and considering wind power penetration［J］.International Journal of Electrical Power and Energy Systems，2013，44(1):282-292.

［8］徐耀群，王長舉.一種萬有引力優(yōu)化算法及其收斂性分析［J］.哈爾濱商業(yè)大學(xué)學(xué)報，2013，29(1):63-69.

XU Yaoqun，WANG Changju.A gravity optimization algorithm and its convergence analysis［J］.Journal of Harbin University of Commerce，2013，29(1):63-69.(in Chinese)

［9］張維平，任雪飛，李國強(qiáng)，等.改進(jìn)的萬有引力搜索算法在函數(shù)優(yōu)化中的應(yīng)用［J］.計算機(jī)應(yīng)用，2013，33(5):1317-1320.

ZHANG Weiping，REN Xuefei，LI Guoqiang，et al. Improved gravitational search algorithm application in function optimization［J］.Computer Applications，2013，33(5):1317-1320.

［10］汪定偉，王俊偉，王洪峰，等.智能優(yōu)化算法［M］.北京:高等教育出版社，2007.