趙蕊娟，楊連賀

天津工業(yè)大學(xué)計算機科學(xué)與軟件學(xué)院，天津300387

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

趙蕊娟，楊連賀

天津工業(yè)大學(xué)計算機科學(xué)與軟件學(xué)院，天津300387

CNKI網(wǎng)絡(luò)出版：2017-03-13,http://kns.cnki.net/kcms/detail/11.2127.TP.20170313.1638.024.html

1 概述

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

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

2 引力移動算法（GMA）

2.1 算法思想

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

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

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

個體i的加速度為：

將式（4）中ai替換為位移對時間的二階導(dǎo)數(shù)并展開：

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

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

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

2.2 質(zhì)量函數(shù)

在GMA算法中個體i的質(zhì)量函數(shù)定義為：

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

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

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

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

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

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

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

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

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

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

3.2 算法流程

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

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

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

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

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

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

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

4 實驗結(jié)果分析

4.1 基準函數(shù)

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

表1 高維單峰測試函數(shù)

表2 高維多峰測試函數(shù)

4.2 實驗仿真

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

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

表3 可調(diào)參數(shù)值

表4 高位單峰函數(shù)最小值搜索結(jié)果

圖1 F1優(yōu)化結(jié)果曲線圖

表5 高位多峰函數(shù)最小值搜索結(jié)果

圖2 F5優(yōu)化結(jié)果曲線圖

圖3 F7優(yōu)化結(jié)果曲線圖

圖4 F12優(yōu)化結(jié)果曲線圖

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

5 結(jié)束語

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

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

[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] 谷文祥，李向濤，朱磊，等.求解流水線調(diào)度問題的萬有引力搜索算法[J].智能系統(tǒng)學(xué)報，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].智能系統(tǒng)學(xué)報，2011，6（6）：520-525.

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

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

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

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

[15] 鄭連斌，楊連賀.一種實現(xiàn)全局優(yōu)化的引力移動算法[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

為提高引力移動算法搜索性能，針對引力移動算法解決一些高維空間優(yōu)化問題時存在的收斂速度慢、搜索精度不高的問題，提出一種基于親和度的改進引力移動算法PGMA?；谝σ苿铀惴ㄔ恚ㄟ^構(gòu)造一個基于親和度概念的系數(shù)對種群個體受到的引力合力公式作適當?shù)淖儞Q改造基本引力移動算法。改進后的算法對種群中個體的位置更新方向加以引導(dǎo)，來提高算法的搜索精度和算法搜索能力。用13個基準函數(shù)對改進算法進行試驗驗證改進算法在求解精度和穩(wěn)定性上優(yōu)于基本引力移動算法。

引力移動算法；合力；親和度；基準函數(shù)；可調(diào)參數(shù)

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—），女，碩士研究生，研究方向：數(shù)據(jù)挖掘、智能優(yōu)化，E-mail：zhaorj_tjpu@163.com；楊連賀，博士，教授，博導(dǎo)，研究方向：數(shù)據(jù)挖掘。