基于差分進(jìn)化與模擬退火的人工魚(yú)群算法研究

周金治，孟　柳

(1.西南科技大學(xué)信息工程學(xué)院，四川 綿陽(yáng) 621010；2.特殊環(huán)境機(jī)器人技術(shù)四川省重點(diǎn)實(shí)驗(yàn)室，四川 綿陽(yáng) 621010)

0　引言

人工魚(yú)群算法(artificial fish swarm algorithm,AFSA)是一種仿效魚(yú)群覓食、群聚、追尾、隨機(jī)等行為的并行優(yōu)化算法[1]。該算法對(duì)搜索空間的自適應(yīng)能力及魯棒性較強(qiáng)，且易于實(shí)現(xiàn)。在眾多應(yīng)用中，AFSA已成為研究熱點(diǎn)。

同時(shí)，AFSA也存在一些不足[2]：①在搜索中，后期收斂慢，且后期搜索具有較大的無(wú)目的性；②尋優(yōu)結(jié)果精度低；③在尋優(yōu)中易陷入局部最優(yōu)值。針對(duì)這些缺點(diǎn)，諸多學(xué)者進(jìn)行了改進(jìn)研究：文獻(xiàn)[3]通過(guò)自適應(yīng)調(diào)整人工魚(yú)的步長(zhǎng)和改進(jìn)魚(yú)群算法中覓食行為，提出了一種變步長(zhǎng)自適應(yīng)的改進(jìn)人工魚(yú)群算法，提高了收斂速度和精度；文獻(xiàn)[4]充分運(yùn)用了粒子飛行速度和線性慣性權(quán)重的特點(diǎn)，提出了粒子群優(yōu)化人工魚(yú)群算法，提高了全局收斂能力和快速跳出局部極值的能力；文獻(xiàn)[5]為解決部分人工魚(yú)陷入局部最優(yōu)的問(wèn)題，引入了DNA交叉和變異的思想，提出了一種基于DNA的改進(jìn)人工魚(yú)群算法。

本文在搜索后期將模擬退火(simulated annealing,SA)算法的思想融入人工魚(yú)群算法中，以提高魚(yú)群算法跳出局部最優(yōu)解的能力。但當(dāng)模擬退火算法的問(wèn)題規(guī)模比較大時(shí)，通常只能得到近似值[6]。因此，引進(jìn)差分進(jìn)化(differential evolution,DE)的思想增加種群大小，以增強(qiáng)個(gè)體間的差異性，使得優(yōu)秀個(gè)體的優(yōu)勢(shì)更加明顯[7]。基于差分進(jìn)化與模擬退火的人工魚(yú)群算法(different evolution simulated annealing-artifical fish swarm algorithm,DESA-AFSA)。不僅具有魚(yú)群算法全局搜索的優(yōu)勢(shì)，還具有模擬退火算法良好的局部收斂能力，并能克服模擬退火算法自身的不足。

1　基本算法

1.1　人工魚(yú)群算法原理

人工魚(yú)群算法能模擬魚(yú)類快速感知食物濃度的能力；而魚(yú)類數(shù)目最多的位置就是食物濃度最高的位置。魚(yú)類通常有如下行為[8]。

①覓食行為。設(shè)某人工魚(yú)的狀態(tài)為Xi，隨機(jī)選擇一個(gè)在視線范圍內(nèi)的狀態(tài)為Xj。若Yi

(1)

式中：rand為(0,1)的隨機(jī)數(shù)，step為移動(dòng)步長(zhǎng)。

③隨機(jī)行為。一部分人工魚(yú)隨機(jī)選出一個(gè)在感知范圍內(nèi)的狀態(tài)，并朝著該方向進(jìn)行，即Xi的下一個(gè)位置Xi|next為：

Xi|next=Xi+R×Dvisual

(2)

式中：R為[-1,1]的隨機(jī)數(shù)；Dvisual為感知距離范圍。

④公告板。在公告板上記錄人工魚(yú)群當(dāng)前尋優(yōu)的最佳狀態(tài)和全局最優(yōu)解。每進(jìn)行一次迭代后，就對(duì)當(dāng)前狀態(tài)和歷史最優(yōu)記錄進(jìn)行比較，選擇最優(yōu)值。

1.2　人工魚(yú)群算法缺陷分析

目前對(duì)人工魚(yú)群算法的描述與應(yīng)用中，存在以下不足。

①收斂精度不高。

從式(1)中可以看出，移動(dòng)步長(zhǎng)step是固定的。這就意味著在收斂后期，人工魚(yú)每前進(jìn)一步都會(huì)在一個(gè)較大的區(qū)域里變化，從而將出現(xiàn)人工魚(yú)在最優(yōu)解附近反復(fù)振蕩的情況。特別是當(dāng)step較大時(shí)，振蕩幅度更大，從而難以達(dá)到較高的收斂精度。

②尋優(yōu)結(jié)果易于陷入局部最優(yōu)的陷阱。

當(dāng)式(1)中的step較小時(shí)，收斂精度會(huì)稍微提高，但收斂速度會(huì)變慢。當(dāng)局部最優(yōu)值突出時(shí)，很容易陷入局部最優(yōu)值。從人工魚(yú)的行為描述上看，每條人工魚(yú)都會(huì)選擇一個(gè)適當(dāng)?shù)男袨樘剿髌渌诃h(huán)境，使其向著最佳位置移動(dòng)，最終導(dǎo)致了人工魚(yú)聚集在幾個(gè)局部極值附近。此時(shí)，魚(yú)群在搜索過(guò)程的個(gè)體差異性變差，導(dǎo)致了尋優(yōu)過(guò)程的停滯不前，最終陷入局部最優(yōu)解而無(wú)法跳出。

2　基于差分進(jìn)化與模擬退火的人工魚(yú)群算法

2.1　算法改進(jìn)策略

考慮到魚(yú)群算法收斂精度不高以及尋優(yōu)結(jié)果容易陷入局部最優(yōu)解的缺陷，提出將模擬退火算法的思想融入魚(yú)群算法。該算法整體分成前期全局搜索和后期局部搜索的兩個(gè)過(guò)程。

(1)前期全局搜索。在每一代人工魚(yú)的尋優(yōu)過(guò)程中，擇優(yōu)執(zhí)行模擬的聚群、追尾等行為，在公告板中求得全局極值滿意解域。具體步驟同上述人工魚(yú)群算法原理。

(2)后期局部搜索。采用模擬退火操作，對(duì)當(dāng)代食物濃度最高的狀態(tài)進(jìn)行細(xì)化搜索。由于模擬退火算法以一定的概率接收較差值，所以能夠跳出局部最優(yōu)解，從而獲得全局最優(yōu)解。模擬退火操作的具體步驟如下[9]。

①選取當(dāng)代食物濃度最高狀態(tài)為初始狀態(tài)S0，令S(0)=S0，初始溫度為T(mén)。

②令T=Ti，若i大于個(gè)體X的變量維數(shù)D，則通過(guò)Metropolis抽樣過(guò)程[10]調(diào)整子變量xi。

具體做法為：在(0,1)之間隨機(jī)產(chǎn)生一個(gè)數(shù)r。若r>0.5，則可得到式(3)，即朝著增大的方向調(diào)整子變量。

(3)

若r<0.5，則可得到式(4)，即朝著減小的方向調(diào)整子變量。

(4)

然后，計(jì)算子變量xi←xi+Δxi。

③計(jì)算調(diào)整后的新個(gè)體X′的目標(biāo)函數(shù)f(X′)和目標(biāo)函數(shù)f(X)的差值Δy。若Δy≤0，則接受新?tīng)顟B(tài)X←X′，執(zhí)行步驟④；否則，不接受新?tīng)顟B(tài)，i=i+1，返回執(zhí)行步驟②。

④退火降溫處理。若Ti小于終止溫度Tend，則Ti+1=kTi(Ti

⑤輸出最優(yōu)解，算法結(jié)束。

當(dāng)面對(duì)大規(guī)模欺騙問(wèn)題時(shí)，利用模擬退火算子實(shí)施局部細(xì)化的求解能力將會(huì)減弱。這是因?yàn)殡S著迭代次數(shù)的增加，個(gè)體間的差異性和多樣性將會(huì)逐漸降低，使得尋優(yōu)結(jié)果只是近似解，而非最優(yōu)解[11]。這時(shí)就可以通過(guò)擴(kuò)大種群規(guī)模和增加代數(shù)的方法接近最優(yōu)解。

由于模擬退火算法和差分進(jìn)化算法可以取長(zhǎng)補(bǔ)短，故引入差分進(jìn)化算法的差分策略。通過(guò)差分策略的變異、交叉和選擇操作擴(kuò)大種群規(guī)模，并放大個(gè)體適應(yīng)度的差異，逼近最優(yōu)解[12-14]。DESA算法流程如圖1所示。圖中:gen為循環(huán)計(jì)數(shù)變量；MAXGEN為最大進(jìn)化次數(shù)；Ti為某次退火溫度；k為冷卻系數(shù)；Tend為終止溫度。

由圖1可知，將當(dāng)代食物濃度最高的狀態(tài)作為初始狀態(tài)，在溫度Ti下進(jìn)行差分進(jìn)化的變異、交叉和選擇操作，再對(duì)得到的新種群進(jìn)行模擬退火算法計(jì)算，直至得到局部最優(yōu)解。

差分策略的變異、交叉和選擇操作如下。

①變異操作。隨機(jī)選擇本體以外的3個(gè)個(gè)體r1、r2、r3，將兩個(gè)個(gè)體的向量差加到第1個(gè)個(gè)體上，得到第i個(gè)個(gè)體第j個(gè)分量變異后的新個(gè)體uij(t+1)。

uij(t+1)=xr1j(t)+η[xr2j(t)-xr3j(t)]

(5)

式中：η為差分進(jìn)化中的放縮因子。

圖1　DESA算法流程圖

②交叉操作。將變異后的新個(gè)體uij(t+1)與當(dāng)前個(gè)體xij(t)進(jìn)行離散交叉操作，可得到中間個(gè)體cij(t+1)。

(6)

式中：r為(0,1)之間的隨機(jī)數(shù)；CR為交叉概率。

③選擇操作。將得到的中間個(gè)體ci(t+1)與當(dāng)前個(gè)體xi(t)進(jìn)行貪婪算法計(jì)算[15]，選擇下一代的新種群個(gè)體xi(t+1)：

(7)

若新個(gè)體比當(dāng)前個(gè)體更優(yōu)，則替換掉當(dāng)前個(gè)體；否則，保留當(dāng)前個(gè)體。

2.2　算法實(shí)現(xiàn)過(guò)程

結(jié)合以上具體步驟，可得出DESA-AFSA算法實(shí)現(xiàn)的整體流程。DESA-AFSA流程如圖2所示。

DESA-AFSA的實(shí)現(xiàn)過(guò)程如下。

①初始化魚(yú)群算法中的魚(yú)群規(guī)模M、每條魚(yú)的初始位置、擁擠度δ、步長(zhǎng)step、視野范圍Dvisual、最大迭代次數(shù)Lmax；模擬退火算法中的初始溫度T、冷卻系數(shù)k、終止溫度Tend、每個(gè)溫度的迭代次數(shù)L；差分進(jìn)化算法中縮放因子η、交叉概率CR等。

②每條人工魚(yú)進(jìn)行覓食、聚群、追尾和隨機(jī)行為，更新自己的位置Xi|next。

③對(duì)每條人工魚(yú)的食物濃度進(jìn)行計(jì)算比較，將當(dāng)代食物濃度最高的狀態(tài)賦值給公告板。

④對(duì)當(dāng)代食物濃度最高的人工魚(yú)群進(jìn)行差分進(jìn)化操作，并將新種群結(jié)果與公告板比較。若較好，則作為步驟⑤的初始狀態(tài)。

⑤將步驟④中的較優(yōu)種群進(jìn)行模擬退火，并將該算法的最優(yōu)解與公告板比較。若更優(yōu)，則將其賦值給公告板。

⑥檢查是否達(dá)到設(shè)定的迭代次數(shù)。若達(dá)到，則輸出最優(yōu)解，算法結(jié)束；若沒(méi)達(dá)到，則跳到步驟②。

圖2　DESA-AFSA流程圖

3　函數(shù)尋優(yōu)仿真

為了驗(yàn)證DESA-AFSA的有效性，對(duì)AFSA、SA-AFSA以及DESA-AFSA進(jìn)行比較，并通過(guò)兩個(gè)經(jīng)典函數(shù)進(jìn)行優(yōu)化仿真試驗(yàn)。

為減少不確定因素對(duì)仿真結(jié)果的影響，對(duì)每次試驗(yàn)中的每種算法獨(dú)立進(jìn)行20次尋優(yōu)仿真。為減少2次試驗(yàn)的差異性，仿真函數(shù)F1與F2采用相同的參數(shù)：人工魚(yú)群規(guī)模M=100，感知距離Dvisual=2.5，步長(zhǎng)step=0.1，最多探測(cè)次數(shù)try_number=100，擁擠度因子δ=0.618，最大迭代次數(shù)Lmax=50，模擬退火算法中每個(gè)溫度的迭代次數(shù)L=40，初始溫度T=30，終止溫度Tend=0.001，冷卻系數(shù)k=0.95，差分進(jìn)化算法中變異率F0=0.5，交叉概率CR=0.9，最大迭代次數(shù)MAXGEN=100，放縮因子η=1。

①測(cè)試函數(shù)F1。

F1函數(shù)的三維圖像如圖3所示。由圖3可知，F(xiàn)1函數(shù)在(0,0)的全局最優(yōu)解為1，在全局最優(yōu)解周圍有很多局部最優(yōu)解，但是全局最優(yōu)解與局部最優(yōu)解差異明顯。

圖3　F1函數(shù)的三維圖像

采用3種算法，分別對(duì)F1函數(shù)進(jìn)行50次迭代的尋優(yōu)，F(xiàn)1函數(shù)平均優(yōu)化結(jié)果如圖4所示。

圖4　F1函數(shù)平均優(yōu)化結(jié)果

從圖4中可以看出，DESA-AFSA的平均優(yōu)化效果最好，收斂速度更快，只需6次迭代就找到了全局最優(yōu)解。其次是SA-AFSA，需要15次迭代才能找到全局最優(yōu)解，而AFSA需要23次左右的迭代才能找到全局最優(yōu)解。

表1為F1函數(shù)的平均尋優(yōu)結(jié)果分析。

表1　F1函數(shù)的平均尋優(yōu)結(jié)果分析

由表1可知，在20次尋優(yōu)試驗(yàn)中，AFSA尋優(yōu)結(jié)果的最優(yōu)值在0.99以上，最差值在0.95以上。SA-AFSA尋優(yōu)的最優(yōu)值為1，最差值在0.99以上。由此表明，雖然SA-AFSA優(yōu)于AFSA，但尋優(yōu)精度有待提高，且穩(wěn)定性不強(qiáng)。DESA-AFSA每次都能準(zhǔn)確地找到全局最優(yōu)解，且收斂速度快，顯然優(yōu)于前兩種算法。

②測(cè)試函數(shù)F2。

|x|≤5,|y|≤5

圖5為F2函數(shù)的三維圖像。由圖5可知，該函數(shù)有很多局部極大值，在尋優(yōu)過(guò)程中容易陷入局部最優(yōu)解而難以跳出；而F2在(0,0)處為全局最優(yōu)解1。

圖5　F2函數(shù)的三維圖像

采用3種算法，分別對(duì)F2函數(shù)進(jìn)行50次迭代的尋優(yōu)。F2函數(shù)平均優(yōu)化結(jié)果如圖6所示。

圖6　F2函數(shù)平均優(yōu)化結(jié)果

從圖6可知，DESA-AFSA的尋優(yōu)效果最好，在大約15次迭代后就能得到全局最優(yōu)解。SA-AFSA在尋優(yōu)過(guò)程中求得的最優(yōu)解逐漸接近全局最優(yōu)解，但最終還是存在誤差。AFSA尋得的最優(yōu)解并不是全局最優(yōu)解。這是因?yàn)樵撍惴ㄔ趯?yōu)過(guò)程中陷入了局部最優(yōu)解而找不到全局最優(yōu)解。

表2為F2函數(shù)的平均尋優(yōu)結(jié)果分析。

表2　F2函數(shù)的平均尋優(yōu)結(jié)果分析

由表2可知，在20次尋優(yōu)試驗(yàn)中，DESA-AFSA每次都能夠跳出局部最優(yōu)值，并能準(zhǔn)確得到全局最優(yōu)值。而AFSA有50%的幾率會(huì)陷入局部最優(yōu)而無(wú)法跳出。SA-AFSA雖然使跳出局部最優(yōu)的能力得到增強(qiáng)，但依然存在陷入局部最優(yōu)解的情況，且得到的全局最優(yōu)解精度不高。

由此得知，為防止陷入局部最優(yōu)，在人工魚(yú)群算法中加入模擬退火算法是可行的，并且可以通過(guò)差分進(jìn)化算法提高模擬退火算法的精度。

4　結(jié)束語(yǔ)

對(duì)于人工魚(yú)群算法的改進(jìn)，提出一種基于差分進(jìn)化與模擬退火的人工魚(yú)群算法，即DESA-AFSA。該算法通過(guò)在人工魚(yú)群算法尋優(yōu)后期引入模擬退火算法，解決尋優(yōu)過(guò)程中陷入局部最優(yōu)解的情況；在模擬退火算法中引入差分進(jìn)化算法，來(lái)提高尋優(yōu)精度。函數(shù)仿真試驗(yàn)證明，DESA-AFSA能夠較好地兼顧全局收斂和局部收斂，并且穩(wěn)定性好、精度高。

參考文獻(xiàn):

[1] 王闖.人工魚(yú)群算法的分析及改進(jìn)[D].大連:大連海事大學(xué),2008.

[2] XIN G,YI X Y.An improved artificial fish swarm algorithm and its application[J].Advanced Materials Research,2012,1566(433):4434-4438.

[3] 朱旭輝,倪志偉,程美英.變步長(zhǎng)自適應(yīng)的改進(jìn)人工魚(yú)群算法[J].計(jì)算機(jī)科學(xué),2015(2):210-216.

[4] 梁毓明,裴興環(huán).粒子群優(yōu)化人工魚(yú)群算法[J].計(jì)算機(jī)仿真,2016(6):213-217.

[5] 費(fèi)騰,張立毅,白煜,等.基于DNA的改進(jìn)人工魚(yú)群算法[J].天津大學(xué)學(xué)報(bào)(自然科學(xué)與工程技術(shù)版),2016(6):581-588.

[6] 傅文淵,凌朝東.布朗運(yùn)動(dòng)模擬退火算法[J].計(jì)算機(jī)學(xué)報(bào),2014,37(6):1301-1308.

[7] 姚峰,楊衛(wèi)東,張明,等.改進(jìn)自適應(yīng)變空間差分進(jìn)化算法[J].控制理論與應(yīng)用,2010,27(1):32-38.

[8] 王培崇.人工魚(yú)群算法研究綜述[J].中國(guó)民航飛行學(xué)院學(xué)報(bào),2013(4):22-26.

[9] 劉愛(ài)軍,楊育,李斐,等.混沌模擬退火粒子群優(yōu)化算法研究及應(yīng)用[J].浙江大學(xué)學(xué)報(bào)(工學(xué)版),2013,47(10):1722-1730.

[10]ZHANG H Y,WU Y F,CHENG L L,et al.Hit and run ARMS:adaptive rejection Metropolis sampling with hit and run random direction[J].Journal of Statistical Computation and Simulation,2016,86(5):973-985.

[11]袁澎,艾芊,趙媛媛.基于改進(jìn)的遺傳-模擬退火算法和誤差度分析原理的PMU多目標(biāo)優(yōu)化配置[J].中國(guó)電機(jī)工程學(xué)報(bào),2014,34(13):2178-2187.

[12]熊聰聰,郝璐萌,王丹,等.一種基于差分策略的群搜索優(yōu)化算法[J].計(jì)算機(jī)科學(xué),2017(2):250-256.

[13]張大斌,楊添柔,溫梅,等.基于差分進(jìn)化的魚(yú)群算法及其函數(shù)優(yōu)化應(yīng)用[J].計(jì)算機(jī)工程,2013(5):18-22.

[14]李榮雨,陳菲爾.改進(jìn)的差分進(jìn)化算法在電力經(jīng)濟(jì)調(diào)度中的應(yīng)用[J].自動(dòng)化儀表,2016,37(11):43-47.

[15]方紅,楊海蓉.貪婪算法與壓縮感知理論[J].自動(dòng)化學(xué)報(bào),2011,37(12):1413-1421.