陳　欣,劉　朔

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

?

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

陳欣,劉朔

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

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

反向評(píng)估機(jī)制;變異策略;萬有引力搜索算法

1　引言

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

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

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

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

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

2.1慣性質(zhì)量計(jì)算

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

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

2.2引力計(jì)算

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

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

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

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

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

2.3位置更新

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

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

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

3.1采用反向評(píng)估機(jī)制的種群初始化和更新

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

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

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

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

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

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

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

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

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

3.3算法具體步驟

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

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

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

Step 4:計(jì)算各個(gè)維度上微粒所受的合力；

Step 5:計(jì)算各個(gè)微粒的加速度；

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

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

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

4　仿真實(shí)驗(yàn)

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

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

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

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

表2仿真實(shí)驗(yàn)結(jié)果

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

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

圖1　Ackley函數(shù)圖

圖2　Rastrigrin函數(shù)圖

圖3　Schaffer函數(shù)圖

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

5　結(jié)束語

針對(duì)傳統(tǒng)引力搜索算法GSA在函數(shù)優(yōu)化過程中容易出現(xiàn)早熟的問題，筆者提出一種基于變異策略和雙向評(píng)估機(jī)制的改進(jìn)萬有引力搜索算法。該算法在演化過程中以一定的概率生成反向種群，在雙向評(píng)估機(jī)制下對(duì)適應(yīng)度較低的個(gè)體進(jìn)行位置變異，并且通過與當(dāng)前種群進(jìn)行比較，保證最優(yōu)個(gè)體進(jìn)入下一代種群。并且通過選取若干個(gè)標(biāo)準(zhǔn)測試函數(shù)，將本文算法與傳統(tǒng)粒子群算法和傳統(tǒng)引力搜索算法相比較。實(shí)驗(yàn)結(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]王彩霞.基于改進(jìn)引力搜索的混合K-調(diào)和均值聚類算法研究[J].計(jì)算機(jī)應(yīng)用研究,2016,33(1):118-121.

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

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

[5]董新燕,丁學(xué)明,王健.基于改進(jìn)的引力搜索算法的T-S模型辨識(shí)[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]張維平,任雪飛,李國強(qiáng),等.改進(jìn)的萬有引力搜索算法在函數(shù)優(yōu)化中的作用[J].計(jì)算機(jī)應(yīng)用,2013,33(5):1317-1320.

[8]馬力，劉麗濤.萬有引力搜索算法的分析與改進(jìn)[J].微電子學(xué)與計(jì)算機(jī),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