楊 青，張金格，吉孟然

(沈陽理工大學 自動化與電氣工程學院，遼寧 沈陽 110159)

萬有引力搜索算法改進及仿真驗證

楊 青，張金格，吉孟然

(沈陽理工大學 自動化與電氣工程學院，遼寧 沈陽 110159)

針對萬有引力搜索算法(GSA)求解函數優(yōu)化問題時易陷入局部最優(yōu)且優(yōu)化精度不高的問題，提出一種改進的萬有引力搜索算法(IGSA)。IGSA算法引入了時變權重和邊界變異策略，改善了全局搜索能力和局部優(yōu)化能力。通過求解無約束優(yōu)化問題進行仿真驗證，結果表明，改進的萬有引力搜索算法具有更好的優(yōu)化性能。

優(yōu)化算法；搜索算法；GSA；IGSA

針對特定的復雜計算，學者們提出很多啟發(fā)式優(yōu)化算法，但目前均未有一種算法能成功解決所有優(yōu)化問題，因此探索新的啟發(fā)式智能搜索算法十分必要。

萬有引力搜索算法(Gravitational Search Algorithm，GSA)由Esmat Rashedi教授等人在2009年提出[1]，是源于對物理學中的萬有引力進行模擬產生的啟發(fā)式智能群體優(yōu)化算法。目前關于萬有引力算法的研究已經成為熱點，理論研究方面，文獻[2-5]從不同角度對GSA算法進行改進以增強其優(yōu)化性能；在應用方面，文獻[6]將改進的GSA用于微網優(yōu)化問題的求解，文獻[7]采用GSA對電力系統(tǒng)控制變量進行優(yōu)化調整，文獻[8]中提出自適應量子的二進制引力搜索算法優(yōu)化電能質量檢測儀位置，文獻[9]將GSA與徑向基神經網絡相結合用于解決配電變電所輸電問題。GSA在解決問題的同時也存在局部優(yōu)化能力差和早熟收斂的問題[6，10]。因此，本文提出了改進的萬有引力搜索算法(ImprovedGravitationalSearchAlgorithm，IGSA)。為驗證IGSA的優(yōu)化效果，文中針對常用的優(yōu)化問題，通過仿真實驗，將IGSA與GSA、PSO算法的優(yōu)化算法結果進行比較。

1 標準萬有引力搜索算法

GSA來源于物理學中的萬有引力定律“宇宙中任意2個質點通過連心線方向上的力相互吸引，該引力的大小與它們質量的乘積成正比，與它們距離的平方成反比，與兩物體的化學組成和其間介質種類無關”。萬有引力會使物體朝著質量最大的物體移動如圖1所示，而最大質量的物體占據最優(yōu)位置，從而求得優(yōu)化問題的最優(yōu)解[1]。在GSA中，每個個體均包含5個特征參數：位置、速度、慣性質量、主動引力質量及被動引力質量，物體的位置即為問題的解。

圖1 各物體對m1的作用

假設在D維搜索空間中有N個個體，定義第i個個體的位置和速度分別為

(1)

i=1,2,…,N;k=1,2,…,D

(2)

式中：Mpi(t)指被作用個體i的慣性質量；Maj(t)指作用個體j的慣性質量；ε代表較小正常量；G(t)指t時刻的萬有引力常量，其值隨宇宙實際年齡的增大而變小，表達式為

G(t)=G0×e-αt/T

(3)

式中：G0指t0時刻的萬有引力常量，通常取值為100；α為衰減系數，通常取為20；T表示最大迭代次數。Rij(t)表示個體i和個體j間的歐氏距離：

Rij(t)=‖Xi(t),Xj(t)‖2

(4)

從而得到t時刻，個體i在k維空間上受到的總的作用力為

(5)

式中rand是[0，1]內的一個隨機數。根據牛頓第二定律，t時刻個體i在第k維上的加速度為

(6)

式中Mii(t)表示在t時刻個體i的慣性質量。

GSA在每次迭代過程中，個體的速度和位置根據以下公式進行更新，即

(7)

個體的慣性質量根據其適應值的大小來計算，慣性質量越大表明它越接近最優(yōu)值，同時也意味著該個體的吸引力越大，但其移動速度卻越慢。假設引力質量與慣性質量相等，個體的質量可以通過適當的運算規(guī)則去更新，更新算法如下所示：

(8)

式中，fiti(t)表示個體i在t時刻的適應值，best(t)和worst(t)根據具體情況而定。當求最小值問題時，定義如下：

(9)

當求最大值問題時，定義如下：

(10)

2 改進的萬有引力搜索算法

本文提出改進GSA(Improved Gravitational Search Algorithm，IGSA)優(yōu)化算法，分別從時變權重和邊界變異兩方面對GSA優(yōu)化算法進行改進，詳細分析如下。

2.1 基于時變權重的GSA優(yōu)化算法

GSA優(yōu)化算法探索能力和開發(fā)能力的平衡是靠慣性權重來實現的。較大的慣性權重使個體在原來的方向上具有更大的速度，具有更好的探索能力；較小的慣性權重使個體繼承了較少的原方向的速度，具有更好的開發(fā)能力。通常希望種群在開始時具有較好的探索能力，隨著迭代次數的增加，特別是臨近結束時希望具有較好的開發(fā)能力。針對此情況本文提出動態(tài)調節(jié)慣性權重的GSA優(yōu)化算法。設置慣性權重的取值范圍為[wmin,wmax]，最大迭代次數為T，則在t時刻慣性權重為

(11)

這是一種線性減小的變化方式。根據實際問題來確定最大權重wmax和最小權重wmin。則公式(7)轉化為

(12)

2.2 基于邊界變異的GSA優(yōu)化算法

在GSA工作過程中，個體在牛頓第二定律作用下若其位置超出可行域[xmin,xmax]的范圍，標準GSA會強制將個體位置拉回其邊界上，即xi=xmax或xi=xmin。實際應用中，若個體位置過多地聚集到可行域邊界上，不利于GSA的收斂。為提高算法收斂性，本文引入邊界變異策略，詳細描述為

若xi≥xmax或xi≤xmin

xi=rand×(xmax-xmin)+xmin

(13)

經邊界變異后，超過邊界的個體將不會全部聚集到邊界上，而是重新分布在[xmin,xmax]可行域范圍內，增加了個體的多樣性，利于算法更快地發(fā)現最優(yōu)解。

2.3 IGSA流程圖

IGSA工作過程如下：

(1)初始化：確定搜索空間維數D，種群規(guī)模N，迭代次數T，初始時刻萬有引力常數G0，衰減系數α，隨機初始化種群位置和速度；

(2)計算每個個體的適應值fiti(t)；

(3)分別根據式(3、8、10)更新G(t)、Mi(t)、best(t)和worst(t)；

(6)根據式(13)進行邊界變異；

(7)判斷是否達到終止條件，若是則停止，否則轉至(2)，一般終止條件設置為一個足夠好的適應值或達到預設的最大迭代次數。

IGSA流程圖如下：

圖2 IGSA流程圖

3 仿真實驗與結果分析

3.1 典型優(yōu)化問題

本文通過求解無約束優(yōu)化問題

圖3 目標函數的三維曲面圖

選用上述目標函數作為測試函數，其特點是該函數是多峰函數，即在[-2π,2π]上具有多個極大點和極小點，但只有一個全局極大值，且在全局極大值臨近的狹小區(qū)域內取值變化緩慢，部分優(yōu)化算法在優(yōu)化該函數時，易陷入局部最優(yōu)，即該函數可以評價優(yōu)化算法的搜索性能。

3.2 IGSA參數設計

編碼：顯然問題的維數為2，即每個個體為2維的實數向量；

初始化范圍：根據問題要求，設定為[-2π,2π]，初始速度設為0；

初始化參數：G0=100，α=20，λ=1；

種群大?。簽榱朔奖阏f明，采用一個較小的種群規(guī)模，N=5；

停止準則：設定為最大迭代次數100次，顯然該問題的最優(yōu)值為1，因此設定閾值為1。

3.3 仿真驗證及分析

圖4給出采用IGSA算法種群全局最優(yōu)適應度值隨著迭代次數增加的變化曲線。結果表明，經過51次迭代后，種群收斂，最優(yōu)位置為(0，0)，最大值為1，這與理論分析相同，驗證了IGSA算法的可行性。

圖4 IGSA全局最優(yōu)適應度值曲線

IGSA與GSA、PSO算法進行比較分析如下：

1)全局最優(yōu)適應度值比較如圖5所示。

定性分析：IGSA優(yōu)化算法在51次迭代時停止循環(huán)，而GSA、PSO算法在達到預定的最大迭代次數100時停止，表明IGSA較GSA、PSO算法有較快的收斂速度；

定量分析：IGSA優(yōu)化算法最終達到最優(yōu)值1，而PSO算法在運行100次之后全局最優(yōu)值為0.9999，盡管相差0.0001，但也表明了IGSA較PSO算法更精確，GSA算法顯然沒有找到最優(yōu)解。

2)個體歷史最優(yōu)適應度值比較曲線如圖6～10所示。

圖6 第1個個體歷史最優(yōu)值曲線

從圖6～10中可以看出，IGSA優(yōu)化算法在可行域范圍內進行全局搜索，最終使得每個個體均取得最優(yōu)值，即種群收斂，而PSO算法在循環(huán)過程中，總在個體歷史最優(yōu)值附近徘徊，這樣就降低了種群的全局搜索能力，以個體1為例，在進行100次迭代時還未達到最優(yōu)值，即種群還未收斂；GSA算法盡管在100次迭代后收斂，但是未達到最優(yōu)值。另外IGSA優(yōu)化過程中每個個體適應度值的波動體現出IGSA算法的全局搜索能力，避免了陷入局部最優(yōu)問題。

圖7 第2個個體歷史最優(yōu)值曲線

圖8 第3個個體歷史最優(yōu)值曲線

圖9 第4個個體歷史最優(yōu)值曲線

圖10 第5個個體歷史最優(yōu)值曲線

4 結束語

提出了改進萬有引力搜索算法，即IGSA。通過引入時變權重及邊界變異策略對GSA算法進行了改進。通過仿真實例對IGSA算法進行測試。與GSA、PSO算法相比，IGSA均表現出更好的優(yōu)化精度與穩(wěn)定性，這表明IGSA具有良好的全局搜索能力且不易陷入局部最優(yōu)值。

[1]Esmat Rashedi，Hossein Nezamabadi-pour，Saeid Saryazdi.GSA：A Gravitation Search Algorithm[J].Informaton Science，2009，(179)：2232-2248.

[2]楊晶，黎放，狄鵬.免疫萬有引力搜索算法的研究與仿真[J].兵工學報，2012，33(12)：1533-1538.

[3]Anupam Yadav，Kusum Deep.Constrained Optimization Using Gravitational Search Algorithm[J].National Academy Science Letters，2013，36(5)：527-534.

[4]Yong Liu，Liang Ma.Improved gravitation search algorithm based on free search differential evolution[J].Journal of systems Engineering and Electronics，2013，24(4)：690-698.

[5]Mohammad Bagher Dowlatshahi，Hossein Nezamabadi-pour，Mashaallah Mashinchi.A discrete gravitational search algorithm for solving combinatorial optimization problems[J].Information Sciences，2014，(258)：94-107.

[6]李鵬，徐偉娜，周澤遠,等.基于改進萬有引力搜索算法的微網優(yōu)化運行[J].中國電機工程學報，2014，34(19)：3073-3079.

[7]Arup Ratan Bhowmik，A.K.Chakraborty.Solution of optimal power flowusing nondominated sorting multiobjective Gravitation Search Algorithm[J].International Journal of Electrical Power & Energy System，2014，(62)：323-334.

[8]Ahmad Asrul Lbrahim，Azah Mohamed，Hussain Shareef.Optimal power quality monitor placement in power system using an adaptive quantum-inspired binary gravitional search algorithm[J].International Journal of Electrical Power & Energy System，2014，(57)：404-413.

[9]Y.Mohamed Shuaib，M.Surya Kalavathi，C.Christober Asir Rajan.Optimal capacitor placement in radial distribution system using Gravitation Search Algorithm[J].International Journal of Electrical Power & Energy System，2015，(64)：384-397.

[10]Tapabrata Chakraborti，Kaushik Das Sharma，Amitava Chatterjee.A novel local extrema based gravitational search algorithm and its applicati on in face recognition using one image per class[J].Engineering Applications of Artificial Intelligence，2014，(34)：13-22.

(責任編輯：馬金發(fā))

Improvement and Simulation of Gravitation Search Algorithm

YANG Qing，ZHANG Jinge，JI Mengran

(Shenyang Ligong University，Shenyang 110159，China)

To solve the problem of falling into local optimal value and the low accuracy in the function optimization by using the Gravitation Search Algorithm (GSA),an improved Gravitation Search Algorithm (IGSA) is proposed.Variable weight and boundary mutation strategy are introduced in the proposed method,which improves the global search ability and local optimization capability.Simulation result of solving the unconstrained optimization problem demonstrates that the proposed algorithm has much better optimization performances.

optimization algorithm;search algorithm;GSA;IGSA

2014-09-30

遼寧省教育廳科學研究項目(L2014083)；遼寧省教育廳科學研究項目(L2015467)

楊青(1963—)，男，教授，研究方向：故障檢測與診斷等.

1003-1251(2015)06-0066-06

文獻標志碼：A