楊 青，張金格，吉孟然

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

萬有引力搜索算法改進(jìn)及仿真驗(yàn)證

楊 青，張金格，吉孟然

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

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

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

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

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

1 標(biāo)準(zhǔn)萬有引力搜索算法

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

圖1 各物體對(duì)m1的作用

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

(1)

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

(2)

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

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

(3)

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

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

(4)

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

(5)

式中rand是[0，1]內(nèi)的一個(gè)隨機(jī)數(shù)。根據(jù)牛頓第二定律，t時(shí)刻個(gè)體i在第k維上的加速度為

(6)

式中Mii(t)表示在t時(shí)刻個(gè)體i的慣性質(zhì)量。

GSA在每次迭代過程中，個(gè)體的速度和位置根據(jù)以下公式進(jìn)行更新，即

(7)

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

(8)

式中，fiti(t)表示個(gè)體i在t時(shí)刻的適應(yīng)值，best(t)和worst(t)根據(jù)具體情況而定。當(dāng)求最小值問題時(shí)，定義如下：

(9)

當(dāng)求最大值問題時(shí)，定義如下：

(10)

2 改進(jìn)的萬有引力搜索算法

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

2.1 基于時(shí)變權(quán)重的GSA優(yōu)化算法

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

(11)

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

(12)

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

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

若xi≥xmax或xi≤xmin

xi=rand×(xmax-xmin)+xmin

(13)

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

2.3 IGSA流程圖

IGSA工作過程如下：

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

(2)計(jì)算每個(gè)個(gè)體的適應(yīng)值fiti(t)；

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

(6)根據(jù)式(13)進(jìn)行邊界變異；

(7)判斷是否達(dá)到終止條件，若是則停止，否則轉(zhuǎn)至(2)，一般終止條件設(shè)置為一個(gè)足夠好的適應(yīng)值或達(dá)到預(yù)設(shè)的最大迭代次數(shù)。

IGSA流程圖如下：

圖2 IGSA流程圖

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

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

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

圖3 目標(biāo)函數(shù)的三維曲面圖

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

3.2 IGSA參數(shù)設(shè)計(jì)

編碼：顯然問題的維數(shù)為2，即每個(gè)個(gè)體為2維的實(shí)數(shù)向量；

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

初始化參數(shù)：G0=100，α=20，λ=1；

種群大小：為了方便說明，采用一個(gè)較小的種群規(guī)模，N=5；

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

3.3 仿真驗(yàn)證及分析

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

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

IGSA與GSA、PSO算法進(jìn)行比較分析如下：

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

提出了改進(jìn)萬有引力搜索算法，即IGSA。通過引入時(shí)變權(quán)重及邊界變異策略對(duì)GSA算法進(jìn)行了改進(jìn)。通過仿真實(shí)例對(duì)IGSA算法進(jìn)行測(cè)試。與GSA、PSO算法相比，IGSA均表現(xiàn)出更好的優(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].兵工學(xué)報(bào)，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]李鵬，徐偉娜，周澤遠(yuǎn),等.基于改進(jìn)萬有引力搜索算法的微網(wǎng)優(yōu)化運(yùn)行[J].中國電機(jī)工程學(xué)報(bào)，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.

(責(zé)任編輯：馬金發(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

遼寧省教育廳科學(xué)研究項(xiàng)目(L2014083)；遼寧省教育廳科學(xué)研究項(xiàng)目(L2015467)

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

1003-1251(2015)06-0066-06

文獻(xiàn)標(biāo)志碼：A