采用反向變異機制的萬有引力搜索算法

陳　欣,劉　朔

(武漢輕工大學(xué) 數(shù)學(xué)與計算機學(xué)院,湖北 武漢 430023)

?

采用反向變異機制的萬有引力搜索算法

陳欣,劉朔

(武漢輕工大學(xué) 數(shù)學(xué)與計算機學(xué)院,湖北 武漢 430023)

和許多經(jīng)典的群智能算法一樣，萬有引力搜索算法在解決很多優(yōu)化問題的時候，容易陷入局部最優(yōu)解并且收斂精度不高。針對這樣的情況，提出一種基于變異策略和反向評估機制的改進萬有引力搜索算法。該算法通過引入反向評估機制和變異策略，顯著地提高了萬有引力搜索算法中粒子的局部尋優(yōu)能力和全局探索能力。通過對三個標(biāo)準(zhǔn)測試函數(shù)進行仿真實驗，表明其與基本的萬有引力搜索算法、傳統(tǒng)粒子群算法相比，提出的基于變異策略和反向評估機制的改進萬有引力搜索算法在函數(shù)優(yōu)化問題上具有更好的優(yōu)化性能。

反向評估機制;變異策略;萬有引力搜索算法

1　引言

萬有引力搜索算法(Gravitation search algorithm,簡稱GSA)是2009年由伊朗學(xué)者Esmat Rashedi等人[1]提出的一種新的啟發(fā)式算法，其源于對物理學(xué)中的萬有引力進行模擬產(chǎn)生的群體智能優(yōu)化算法。與粒子群算法(Particle swarm optimization，簡稱PSO)類似，GSA也是一種元啟發(fā)算法，算法原理是將搜索粒子看作宇宙空間運轉(zhuǎn)的一組物體，這組物體彼此之間通過萬有引力相互作用，導(dǎo)致物體的運動看作是嚴(yán)格遵循天體動力學(xué)的規(guī)律。將適應(yīng)度值看作是微粒的質(zhì)量，適應(yīng)度大的粒子所對應(yīng)的質(zhì)量就越大。因此，萬有引力定律會促使物體體現(xiàn)出向質(zhì)量較大的物體移動的趨勢，從而逐漸逼近求出優(yōu)化問題的最優(yōu)解。隨著GSA理論的不斷深入發(fā)展，以及其在各個領(lǐng)域廣泛的應(yīng)用，越來越多的國內(nèi)外學(xué)者開始關(guān)注GSA。文獻(xiàn)[2-5]就給出了對傳統(tǒng)的GSA算法的一些改進。但是，和其他全局搜索的群體智能算法一樣，GSA也容易陷入局部解和優(yōu)化精度不高等問題。

為了解決以上的不足，筆者對傳統(tǒng)萬有引力搜索算法做了以下兩個方面的改進：一是為了使初始種群中的微粒具有更均勻的分布，在種群初始化的時候引入反向評估機制；二是為了提高迭代搜索過程中的精度，采用類似于遺傳算法中交叉變異機制的策略。為了驗證本算法的優(yōu)化效果，通過仿真實驗，利用常見的三個標(biāo)準(zhǔn)測試函數(shù)進行測試和比較。

2　傳統(tǒng)的萬有引力搜索算法

GSA算法將所有粒子當(dāng)作具有質(zhì)量的物體，在尋優(yōu)過程中，所有粒子做著理想的無阻力運動。每個物體在其運動過程中都會受到解空間中來自其他物體的引力的影響，并且在牛頓第二運動定律的作用下，以一定的加速度向質(zhì)量更大的粒子靠近。由于GSA算法中，微粒的質(zhì)量是與微粒的適應(yīng)度的值相關(guān)，適應(yīng)度更優(yōu)的粒子其質(zhì)量也會更大，因此質(zhì)量相對較小的粒子在朝著質(zhì)量大的粒子趨近的過程中逐漸逼近所分析問題的最優(yōu)解。

假設(shè)在一個D維的搜索空間中包含N個物體，則第i個物體的位置為：

2.1慣性質(zhì)量計算

粒子Xi的慣性質(zhì)量直接和粒子所在位置所求的適應(yīng)度值有關(guān)，在時刻t時，粒子Xi的質(zhì)量用Mi(t)來表示。其計算公式如下：

其中fiti(t)表示時刻t粒子Xi的適應(yīng)度值。best(t)表示時刻t中的最佳解，worst(t)表示時刻t中的最差解。

2.2引力計算

時刻t，物體j在第k維上受到物體i的引力為：

其中，ε表示一個很微小的常數(shù)； Mi(t),Mj(t)分別表示物體i，物體j的質(zhì)量。G(t)表示引力隨宇宙時間變換的萬有引力常數(shù)，它的值通常是由宇宙的真實年齡所決定的，隨著宇宙年齡的增大，它的值反而會變小，具體如下式：

通常G0=100,a=20。而Rij(t)表示物體i和物體j的歐氏距離，具體如下式：

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

因此在時刻t，第k維上作用于微粒Xi的作用力總和等于其他所有物體對其作用之和。其計算公式如下所示：

2.3位置更新

根據(jù)牛頓第二運動定律，物體受到外力的作用就會產(chǎn)生加速度，因此當(dāng)粒子受到其他粒子的引力作用后也會產(chǎn)生加速度。根據(jù)以上的分析，物體i在第k維上獲得的加速度為其作用力與慣性質(zhì)量的比值。具體如下式表示：

在每一次迭代過程中，根據(jù)得到的加速度來更新物體i的速度和位置，其更新公式如下：

3　基于反向變異機制的萬有引力搜索算法

3.1采用反向評估機制的種群初始化和更新

與許多群體智能算法一樣，種群中微粒的初始位置對算法整體的運行起到非常重要的作用。為了使初始種群的微粒位置具有更好的分布性,在初始種群的分布上采用Tizhoosh提出的反向?qū)W習(xí)雙向評估機制[6]。假設(shè)x∈[a,b],則它相對應(yīng)的反向粒子x′=a+b-x。采用雙向評估機制的種群初始化和更新的具體步驟如下：

1)隨機產(chǎn)生N個位于D維搜索空間內(nèi)的粒子的初始位置，從而構(gòu)成初始種群記為IP,其中每個微粒的位置表示為：

2)遵循反向?qū)W習(xí)機制。根據(jù)初始種群IP產(chǎn)生相對應(yīng)的反向種群EP，即X′∈EP，其中：

3)將初始種群IP與反向種群EP合并成一個容量為2N的擴展種群，將這2N的微粒所對應(yīng)的適應(yīng)度值按照大小進行排序，再結(jié)合下文所描述的基于變異的精英機制相結(jié)合來更新種群。反向?qū)W習(xí)機制不僅考慮初始種群而且考慮其反向種群的適應(yīng)度值，這種機制實際上是一種雙向評估機制，這種機制使得微粒的搜索范圍更加均勻，搜尋到全局最優(yōu)解的幾率變得更大。

3.2基于變異策略的優(yōu)化

為了避免算法陷入局部最優(yōu)解，張維平等人[7]曾經(jīng)提出一種基于傳統(tǒng)精英策略的優(yōu)化方法，但是其方法仍然具有一定的局限性。筆者提出一種類似遺傳算法的變異機制的精英策略。首先根據(jù)傳統(tǒng)的引力搜索算法計算出各個微粒的適應(yīng)度值，并且完成微粒位置的更新。此時在該輪迭代結(jié)束后，將2N個粒子的適應(yīng)度值進行排序，記錄下此時刻最好的適應(yīng)度值和對應(yīng)的微粒位置Xbest(t)，并且選取適應(yīng)度最差的10%的微粒進行進化變異操作。之所以選取適應(yīng)度排在最后10%的微粒進行進化變異操作，是因為在傳統(tǒng)的引力搜索算法中，隨著物體之間的引力作用，一方面對于所有的微粒而言已經(jīng)體現(xiàn)出向當(dāng)前最優(yōu)解靠近的趨勢，另一方面對于那些適應(yīng)度比較差的微粒而言，應(yīng)該只是在一部分的維度上體現(xiàn)出與當(dāng)前最優(yōu)解有較大的差距，在另一些維度上則相差無幾。在其他的一些群體智能算法中，也經(jīng)常出現(xiàn)這種情況，為了克服這種情況，借鑒遺傳算法中的對若干個基因片段進行突變的變異操作。傳統(tǒng)的遺傳算法，是在保留了父代優(yōu)良基因的情況下，對個別基因片段產(chǎn)生變異，在變異基因片段的選擇上仍然具有一定的盲目性。而筆者提出的基于靠近全局最優(yōu)解的位置變異可以保證當(dāng)前粒子以一定概率在所有維度上向當(dāng)前最優(yōu)解靠近，可以使得原來適應(yīng)度較差的微粒經(jīng)過基因突變之后向當(dāng)前最優(yōu)解靠攏的幾率大大增加。具體的變異操作思想如下：

我們求出所有微粒和當(dāng)前處于最佳位置的微粒的平均距離DT(t)，如果當(dāng)前粒子Xp(t)與此時最佳的微粒位置Xbest(t)的距離小于DT,則進行局部靠近的探索階段,，位置更新公式如下：

Xp(t+1)=(1+α*U(-0.5,0.5))Xp(t)

其中α是(0,1)之間均勻分布的隨機數(shù)。如果當(dāng)前粒子Xp(t)與此時最佳的微粒位置Xbest(t)的距離大于DT，則進行相對大范圍的開發(fā)階段，此時采取對當(dāng)前粒子施加一定的擾動的方式來進行微粒的更新，擾動的結(jié)果是一定概率保證微粒在所有維度上靠近全局最優(yōu)解。位置更新公式如下：

其中r1,r2為服從U(0,1)分布的隨機數(shù)，k表示位置的第k維度，t表示當(dāng)前迭代輪數(shù)，T表示最大迭代次數(shù)。變異后得到的新微粒與原個微粒進行比較，并保留適應(yīng)度較好的個體。隨著迭代次數(shù)的增加，擾動逐漸轉(zhuǎn)移到最優(yōu)個體，再通過對最優(yōu)個體的擾動來與原來適應(yīng)度較差而距離相對較遠(yuǎn)的微粒進行交叉變異，如此不斷的擾動，可以避免種群陷入早熟而導(dǎo)致搜索停滯不前。

3.3算法具體步驟

Step 1:通過反向?qū)W習(xí)機制，將初始種群IP擴展成種群{IP∪EP}，并且由變異策略替換擴展種群中最后10%的微粒；

Step 2:計算各個微粒的適應(yīng)度的值；

Step 3:更新G(t),Mi(t),best(t),worst(t)變量；

Step 4:計算各個維度上微粒所受的合力；

Step 5:計算各個微粒的加速度；

Step 6:更新種群內(nèi)所有微粒的位置；

Step 7:通過反向?qū)W習(xí)機制，以一定的概率將初始種群IP擴展成種群{IP∪EP}，并且由變異策略替換擴展種群中最后10%的微粒；

Step 8:返回至步驟2，直到滿足判斷條件后停止。

4　仿真實驗

為了驗證本文算法的有效性，選取了三個標(biāo)準(zhǔn)測試函數(shù)[8]與傳統(tǒng)粒子群算法(PSO)和傳統(tǒng)引力搜索算法(GSA)來進行仿真實驗的對比。實驗函數(shù)選取如表1所示。

表1三個標(biāo)準(zhǔn)測試函數(shù)

函數(shù)搜索空間最優(yōu)值A(chǔ)ckley[-32,32]0Rastrigrin[-5.12,5.12]0Schaffer[-10,10]0

在仿真實驗中，為了消除偶然性的影響，每個算法均獨立運行30次，維度選擇為30維，記Ackley函數(shù)為f1，Rastrigrin函數(shù)為f2，Schaffer函數(shù)為f3，其平均最佳適應(yīng)度的結(jié)果如表2所示：

表2仿真實驗結(jié)果

函數(shù)傳統(tǒng)PSO算法傳統(tǒng)GSA算法本文算法f10.00353127-0.00539183-0.00043771f20.000440800.335271360.00034647f30.030340230.073463300.00013073

為了分析幾種算法的動態(tài)收斂情況，圖1，圖2，圖3給出了傳統(tǒng)PSO算法、傳統(tǒng)GSA算法和本文算法在幾個典型測試函數(shù)上的收斂曲線。

圖1　Ackley函數(shù)圖

圖2　Rastrigrin函數(shù)圖

圖3　Schaffer函數(shù)圖

從圖1可以看出，對于多峰值A(chǔ)ckley函數(shù)，本文算法與傳統(tǒng)PSO算法和傳統(tǒng)GSA算法相比，優(yōu)勢是比較明顯，具有更快的收斂速度和收斂精度；從圖2可以看出，對于多峰值Rastrigrin函數(shù)，本文算法比傳統(tǒng)PSO算法具有明顯優(yōu)勢，在算法初期具有更好的收斂速度，在算法后期具有更好的收斂精度。與傳統(tǒng)GSA算法相比，具有更好的穩(wěn)定性；從圖3可以看出，傳統(tǒng)PSO算法掉入了局部收斂的陷阱，而本文則具有明顯的更準(zhǔn)確的收斂精度。與傳統(tǒng)的GSA算法相比，本文算法的收斂速度也有了明顯的提高。

5　結(jié)束語

針對傳統(tǒng)引力搜索算法GSA在函數(shù)優(yōu)化過程中容易出現(xiàn)早熟的問題，筆者提出一種基于變異策略和雙向評估機制的改進萬有引力搜索算法。該算法在演化過程中以一定的概率生成反向種群，在雙向評估機制下對適應(yīng)度較低的個體進行位置變異，并且通過與當(dāng)前種群進行比較，保證最優(yōu)個體進入下一代種群。并且通過選取若干個標(biāo)準(zhǔn)測試函數(shù)，將本文算法與傳統(tǒng)粒子群算法和傳統(tǒng)引力搜索算法相比較。實驗結(jié)果表明，本文算法在收斂速度和尋優(yōu)精度上具有更大的優(yōu)勢。

[1]Rashedi E, Nezamabadi-pour H, Saryazdi S.GSA:A Gravitational search algorithm[J].Information Sciences,2009,179(13):2232-2248.

[2]王彩霞.基于改進引力搜索的混合K-調(diào)和均值聚類算法研究[J].計算機應(yīng)用研究,2016,33(1):118-121.

[3]覃飛.一類求解箱式約束優(yōu)化問題的自適應(yīng)引力搜索算法[J].計算機測量與控制,2016,24(1):273-276.

[4]楊青,張金格,吉孟然.萬有引力搜索算法改進及仿真驗證[J].沈陽理工大學(xué)學(xué)報,2015,34(6):66-71.

[5]董新燕,丁學(xué)明,王健.基于改進的引力搜索算法的T-S模型辨識[J].電子科技,2015,28(11):16-20.

[6]Tizhoosh H R.Opposition-based learning：a new scheme for machine intelligence[C].Int.Conf.on Computational Intelligence for Modeling Control and Automation-CIMCA 2005.Vienna，Austria,2005,(1):695-701.

[7]張維平,任雪飛,李國強,等.改進的萬有引力搜索算法在函數(shù)優(yōu)化中的作用[J].計算機應(yīng)用,2013,33(5):1317-1320.

[8]馬力，劉麗濤.萬有引力搜索算法的分析與改進[J].微電子學(xué)與計算機,2015,32(9):76-80.

Improvement of universal gravitation search algorithm based on reverse evaluation mechanism

CHENXin1,LIUShuo2

(School of Mathematics and Computer Science, Wuhan Polytechnic University,Wuhan 430023,China)

Like many of the classic swarm intelligence algorithm, gravitational search algorithm is easy to fall into local optimal solution and convergence precision that is not high in solving many optimization problems.In this situation, this paper proposes an improved universal gravitation search algorithm based on reverse evaluation mechanism. The local optimization ability and the global exploration ability of the particle in the gravitational search algorithm are significantly improved by introducing the reverse evaluation mechanism and variation strategy.Simulation experiment of three standard test functions,show that improvement of universal gravitation search algorithm based on reverse evaluation mechanism on this paper has better functions in function optimization problem，compared with basic gravity search algorithm and the traditional particle swarm algorithm.

reverse evaluation mechanism; mutation strategy;gravitation search algorithm

2016-03-24.

2016-04-25.

陳欣(1978-),男,講師,E-mail:2924892402@qq.com.

2095-7386(2016)03-0060-04

10.3969/j.issn.2095-7386.2016.03.011

TP 391

A