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

隋永霞， 孫合明

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

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

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

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

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

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

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

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

其中，fiti(t)代表粒子i 在t 時刻的適應值，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 上的慣性質量，Maj(t)表示被作用物體j 的慣性質量。G(t)是引力常數，其隨宇宙實際年齡的變化而變化，計算公式為

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

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

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

其中rand 是［0，1］之間的隨機數。

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

2.1 基于Gaussian 變異的GSA 的思想

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

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

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

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

2.2 基于Gaussian 變異的GSA 的實現流程

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

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

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

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

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

3 實驗結果與分析

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

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

表1 6 個經典測試函數Tab.1 Six classical test functions

表2 3 種算法對測試函數的平均值與標準差Tab.2 Mean and standard deviation of three algorithms for test functions

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

圖1 函數F1 中3 種算法優化結果比較Fig.1 Optimization results of three algorithms in function F1

圖2 函數F2 中3 種算法優化結果比較Fig.2 Optimization results of three algorithms in function F2

圖3 函數F3 中3 種算法優化結果比較Fig.3 Optimization results of three algorithms in function F3

圖4 函數F4 中3 種算法優化結果比較Fig.4 Optimization results of three algorithms in function F4

圖5 函數F5 中3 種算法優化結果比較Fig.5 Optimization results of three algorithms in function F5

圖6 函數F6 中3 種算法算法優化結果比較Fig.6 Optimization results of three algorithms in function F6

4 結 語

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

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

［2］徐遙，王士同.引力搜索算法的改進［J］.計算機工程與應用，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］.計算機應用研究，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］.中國科學:技術科學，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］徐耀群，王長舉.一種萬有引力優化算法及其收斂性分析［J］.哈爾濱商業大學學報，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］張維平，任雪飛，李國強，等.改進的萬有引力搜索算法在函數優化中的應用［J］.計算機應用，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］汪定偉，王俊偉，王洪峰，等.智能優化算法［M］.北京:高等教育出版社，2007.