基于親和度的引力移動算法

趙蕊娟，楊連賀

天津工業大學計算機科學與軟件學院，天津300387

基于親和度的引力移動算法

趙蕊娟，楊連賀

天津工業大學計算機科學與軟件學院，天津300387

CNKI網絡出版：2017-03-13,http://kns.cnki.net/kcms/detail/11.2127.TP.20170313.1638.024.html

1 概述

近年來，許多相關研究人員通過觀察自然界中各種自然現象并從中受到了啟發，提出了很多啟發式優化算法來解決一些復雜的問題，例如：中心力算法[1]、模擬退火算法[2]、蟻群算法[3]、遺傳算法[4]、粒子群算法[5]等。這些啟發式優化算法只在某些特定問題上提供了有效解決問題的途徑，在解決一些高維空間優化問題時存在著搜索解的精度較低、搜索解過程中容易陷入局優導致算法收斂速度慢等問題。因此，探索新的算法仍然是必要的。

引力搜索算法（Gravitational Search Algorithm，GSA）是近年來伊朗克曼大學的教授EsmatRashedi等[6-7]提出的基于牛頓第二定律和萬有引力定律的一種新型啟發式優化算法。目前有關引力搜索算法的研究已經陸續展開，在應用方面，文獻[8]將GSA用于解決流水線調度問題時獲得了較好的效果，文獻[9-10]將模糊C-mean算法與GSA相結合用于求解模糊聚類問題，文獻[11]將GSA應用到船舶船艙的布置上得出的方案能較好地符合算例的要求，文獻[12]用GSA求解該電力系統電壓無功控制的數學模型；在理論研究方面，文獻[13-14]從不同的角度對算法進行了改進以增強其優化性能。在GSA算法的基礎上文獻[15]提出了一種新型的群體搜索優化算法引力移動算法（GMA）并在文中證明了GMA的搜索解的精度和穩定性明顯優于粒子群算法。但是引力移動算法在使用中仍然存在著過早陷入局部最優解導致收斂速度過早，搜索精度相對較低問題。本文針對這種群體搜索算法GMA的不足，引入親和度概念，對GMA算法中合力公式加以改進，使個體能夠更快地向最優方向移動，并通過試驗驗證改進方法的有效性。

2 引力移動算法（GMA）

2.1 算法思想

在引力移動算法中，個體在解空間中位置的優劣用個體質量大小來表示，初始狀態下種群中個體隨機分布在可行域中。種群中的每個個體均受萬有引力作用，在其作用下質量小的個體會逐漸向質量大的個體移動，種群整體呈現出收斂態勢，最終整個種群收斂到一點，該點即為種群最優解。

假定有一個種群的規模為N的D維目標搜索空間，則種群中第i個個體的位置向量定義為：

其中Xi和Xj分別表示個體i與個體j的位置。一個種群中個體i受到合力是其引力和，定義為：

個體i的加速度為：

將式（4）中ai替換為位移對時間的二階導數并展開：

將公式（5）作為一個微分方程，對其求解得：

其中C1和C2為任意實數，變量t取1。random是一個范圍為[0，1]隨機數。引力常量G表示為：

其中G0為100，a為20，算法計算過程中當前迭代次數是iteration，最大迭代次數是MAXITER。

2.2 質量函數

在GMA算法中個體i的質量函數定義為：

其中f(Xi)表示個體i的適應值。對于求解最小值問題，f(Xbest)和f(Xworst)定義如下：

對求解最大值問題，f(Xbest)和f(Xworst)定義如下：

3 基于親和度的引力移動算法

種群中各粒子質量的計算是引力移動算法中的最關鍵部分，在引力移動算法中粒子質量的大小是通過質量相關的函數適應值的大小來衡量的，作用粒子在質量大，適應值好，對作用力子吸引力大的粒子作用下逐步偏向質量較大的粒子。對于種群整體，作用粒子將受到群體粒子質量的影響，從而使作用粒子在群體粒子質量的影響作用下向粒子的最優方向移動。

根據以上算法思想的敘述可知粒子質量的大小與粒子受到合力的大小具有緊密關系。因此，改進算法通過改進粒子質量關系來改進粒子受到種群中其他粒子對該粒子的引力合力計算公式從而實現對粒子位置更新的引導。

3.1 基于親和度的引力移動算法簡述

根據上文對引力移動算法的分析，在改進的引力移動算法中通過在式（3）中添加系數λ來改進GMA中的粒子受到的合力計算公式。系數λ的計算公式為：

其中，λ為式（3）需要添加的系數；k1,k為可調整參數，在不同函數中設置不同的值；C為與k有關的參數，可通過C=πk-1/2計算。x的計算由式（13）得到，其中，M(i)和M(j)分別為粒子i和粒子j的質量；f(x)為一它由x得來的分段函數，通過式（15）可以使f(x)在[0,內變化。改進算法中設置x實現了函數值的親和度檢測。x值越小即兩個粒子的之間的質量差越小，表示兩個粒子之間親和度越大，且兩者之間引力越大；反之，兩者之間的引力就越小。因此，將上式中設置的系數λ計算公式代入式（3）得到改進的引力移動算法的合力計算公式，表示為：

從式（16）可以看出，通過在引力移動算法中合力計算公式中添加λ，加快了算法的尋優速度。由于粒子的質量是由計算所得的目標函數的適應度值表示的，種群中粒子間目標函數適應度值大小越接近，粒子質量大小也就越相近，進而式（13）中x的值越小，且由式（15）可以得知，兩個粒子之間的質量差的值越小，λ就越大，故將x代入式（15）計算得到一個系數λ的值就越大，相應的兩個粒子間親和度越大，進而粒子間的相互作用力也就越大，加快粒子向最優解偏移。

故由上文敘述分析知，改進的引力移動算法計算過程在基本算法每次迭代過程中首先計算粒子適應值，在計算得到新的適應度值的基礎上，添加了一個修正適應值系數，削弱適應值差別大的粒子對作用粒子的影響，使得在粒子在尋優的過程中不容易陷入局部最優解，從而加速了尋優過程的進行。當種群兩個粒子間適應度大小（即質量差）越相近時，粒子間的相互作用力也就越大，對作用粒子產生的加速度越大，作用粒子就會向對應粒子方向加速偏移，而當兩個粒子間質量差很大時，粒子對作用粒子的作用力也就越小，對作用粒子產生相應方向的加速度就越小，粒子向著劣勢方向的偏移就越小，在這種趨勢下，整個種群就能更好地向最優解移動，理論說明改進的引力移動算法可以加速種群的收斂。

3.2 算法流程

步驟1初始化一個種群規模的大小為N，最大迭代次數設置為T，個體在可行域內中隨機分布。

步驟2計算種群中每個個體在本次迭代后的適應值，確定種群中本次迭代后最優個體，更新最優個體及其適應值。

步驟3計算個體慣性質量及個體間的引力。

步驟4根據公式（13）計算種群中每個個體與種群中其他個體間質量差的大小。

步驟5根據公式（15）映射到區間，計算得到系數，得到粒子受到的合力。

步驟6根據公式（6）更新個體位置。

步驟7如滿足終止條件則結束算法，否則返回步驟2。

4 實驗結果分析

4.1 基準函數

為了測試該算法的優化效果，本文選取13個標準基準函數[17]來測試比較改進算法與基本算法的性能。基準函數如表1、表2所示。在表1包含的函數為高維單峰函數，在表2包含的函數為高維多峰函數。其中函數的維數用變量n代表，S是Rn的子集，表1、表2中的函數除了F8最小值為-418.982 9×n外其他函數的最小值均為0。

表1 高維單峰測試函數

表2 高維多峰測試函數

4.2 實驗仿真

算法的實驗仿真平臺為Windows 10，MatlabR14a版本。本實驗把改進后的算法與基本的引力移動算法進行結果對比。在以上情況下，假定兩種算法種群的維度為30，種群規模設為50，最大迭代次數為1 000。對每個測試函數運行30次，統計測試30次后測試運行結果的中值、平均值和方差。

表3是式（14）、式（15）中的可調參數，可調參數是在仿真過程中多次測試后在穩定性和搜索精度結果相對最好的情況下確定的。對于表1、表2中的測試函數，運行結果分別如表4、表5所示。圖1是F1優化結果曲線圖，圖2是F5優化結果曲線圖，圖3是F7優化結果曲線圖，圖4是F12優化結果曲線圖，其中橫坐標表示當前迭代次數，縱坐標表示每次迭代中取得的最好適應值的對數值。

表3 可調參數值

表4 高位單峰函數最小值搜索結果

圖1 F1優化結果曲線圖

表5 高位多峰函數最小值搜索結果

圖2 F5優化結果曲線圖

圖3 F7優化結果曲線圖

圖4 F12優化結果曲線圖

通過表4、表5數據以及改進前后GMA優化曲線對比可知，PGMA的收斂速度和最優值的精度均優于基本GMA算法。通過上文中算法的理論推理和仿真實驗的結果可知，在可行域中搜索解的過程中粒子是不斷尋找最優的，種群中每個粒子在其受到的來自種群其他所有粒子作用力疊加形成的合力作用下不斷的移動。PGMA通過引進由粒子質量差的來表示親和度，對基本GMA算法進行改進。在PGMA算法中采用減小質量大（即優解）的粒子對最優解的偏差，削弱質量小的粒子對質量大的粒子的作用力的方法，從而使得粒子更好更快地向著最優解的方向運動，進而提高了算法的搜索精度和穩定性。

5 結束語

本文對基本的GMA算法進行改進：在GMA算法基礎上，針對其很難對問題求極小值進行了改進。在一個種群中，每個個體都在其他個體的引力作用而移動，在這種運動趨勢下，整個種群中粒子最終達到一個平衡狀態。個體在更新位置信息時，嘗試改進了粒子受到種群中其他個體對其的合力的計算公式，優化了搜索精度，加快了算法的收斂速度。

本文使用13個基準函數對改進后的算法與GMA算法進行測試對比來驗證改進算法性能PGMA提高。從實驗結果可以看出，改進后的算法在穩定性和求解精度上均有更好的表現，驗證了改進方法的可行性和有效性。

[1] Formato R A.Central force optimization：A new natureinspired computational framework for multidimensional search and optimization[C]//Proceedings of Nature Inspired Cooperative Strategies for Optimization（NICSO 2007）.Berlin，Germany：Springer，2008：221-238.

[2] Lin Y L，Chang W D，Hsieh J G.A particle swarm optimization approach to nonlinear rational filter modeling[J].Expert Systems with Applications，2008，34（2）：1194-1199.

[3] Dorigo M，Maniezzo V，Colorni A.Ant system：Optimization by a colony of cooperating agents[J].IEEE Transactions on Systems，Man，and Cybernetics，PartB：Cybernetics，1996，26（1）：29-41.

[4] Goldberg D E，Holland J H.Genetic algorithms and machine Learning[J].Machine Learning，1988，3（2）：95-99.

[5] Karakuzu J，Eberhart R C.Particle swarm optimization[C]//Proceedings of IEEE International Conference on Neural Networks.Washington D C，USA：IEEE Press，1995：1942-1948.

[6] Rashedi E，Nezamabadi-Pour H，Saryazdi S.GSA：A gravitational search algorithm[J].Information Sciences，2009，179（13）：232-2248.

[7] Rashedi E，Nezamabadi-Pour H，Saryazdi S.BGSA：Binary gravitational search algorithm[J].Natural Computing，2010，9（3）：727-745.

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

[9] Yin M H，Hu Y M，Li X T，et al.A novel hybrid K-harmonic means and gravitational search algorithm approach for clustering[J].Expert Systems with Applications，2011，38（8）：9319-9324.

[10] 谷文祥，郭麗萍，殷明浩.模糊c-均值算法和萬有引力算法求解模糊聚類問題[J].智能系統學報，2011，6（6）：520-525.

[11] 王宇，黃勝，廖全蜜，等.基于引力搜索算法的船舶艙室布置方法[J].上海交通大學學報，2016，50（1）：131-139.

[12] 陳梓銘.基于萬有引力搜索算法的電力系統電壓無功控制策略研究[J].華北電力技術，2016，35（5）：16-21.

[13] 蔣悅，沈冬梅，趙彥，等.基于引力搜索和分布估計的混合離散優化算法[J].計算機應用，2014，34（7）：2074-2079.

[14] 徐遙，王士同.引力搜索算法的改進[J].計算機工程與應用，2011，47（35）：188-192.

[15] 鄭連斌，楊連賀.一種實現全局優化的引力移動算法[J].計算機工程，2015，41（7）：230-233.

[16] Spears W M，Spears D F，Heil R，et al.An over view of physicomimetics[M].Berlin，Germany：Springer，2005.

[17] Sarafrazi S，Nezamabadi-Pour H，Saryazdi S.Disruption：A new operator in gravitational search algorithm[J].Scientia Iranica，2011，18（3）：539-548.

ZHAO Ruijuan,YANG Lianhe.Improved gravitation move algorithm based on affinity.Computer Engineering andApplications,2018,54（6）：44-48.

ZHAO Ruijuan,YANG Lianhe

School of Computer Science and Software Engineering,Tianjin Polytechnic University,Tianjin 300387,China

To improve the searching performance of gravitation move algorithm,in accordance with problems of bad performance in search accuracy and slow convergence speed in the high dimensional space optimization,PGMA is proposed by introducing affinity to improve the algorithm convergence and search precision,and this improved Gravitational Move Algorithm（GMA）changes the particle’s gravitational force calculation formula.It includes the principles of gravitational move algorithm and the structure of the affinity,and the affinity for the appropriate transformation is added to the formula resultant force.Then the formula resultant force is modified.Thirteen benchmarks function are tested and show that new algorithm is better than GMAwith both a steady convergence and a better accuracy of solution.

Gravitation MoveAlgorithm（GMA）;resultant force;affinity;benchmark function;adjustable parameter

為提高引力移動算法搜索性能，針對引力移動算法解決一些高維空間優化問題時存在的收斂速度慢、搜索精度不高的問題，提出一種基于親和度的改進引力移動算法PGMA。基于引力移動算法原理，通過構造一個基于親和度概念的系數對種群個體受到的引力合力公式作適當的變換改造基本引力移動算法。改進后的算法對種群中個體的位置更新方向加以引導，來提高算法的搜索精度和算法搜索能力。用13個基準函數對改進算法進行試驗驗證改進算法在求解精度和穩定性上優于基本引力移動算法。

引力移動算法；合力；親和度；基準函數；可調參數

2016-11-09

2017-01-02

1002-8331（2018）06-0044-05

A

TP301

10.3778/j.issn.1002-8331.1611-0158

天津市科技計劃項目（No.16JCTPJC47400）。

趙蕊娟（1990—），女，碩士研究生，研究方向：數據挖掘、智能優化，E-mail：zhaorj_tjpu@163.com；楊連賀，博士，教授，博導，研究方向：數據挖掘。