周金治，孟　柳

(1.西南科技大學信息工程學院，四川 綿陽 621010；2.特殊環(huán)境機器人技術四川省重點實驗室，四川 綿陽 621010)

0　引言

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

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

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

1　基本算法

1.1　人工魚群算法原理

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

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

(1)

式中：rand為(0,1)的隨機數(shù)，step為移動步長。

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

Xi|next=Xi+R×Dvisual

(2)

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

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

1.2　人工魚群算法缺陷分析

目前對人工魚群算法的描述與應用中，存在以下不足。

①收斂精度不高。

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

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

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

2　基于差分進化與模擬退火的人工魚群算法

2.1　算法改進策略

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

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

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

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

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

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

(3)

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

(4)

然后，計算子變量xi←xi+Δxi。

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

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

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

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

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

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

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

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

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

(5)

式中：η為差分進化中的放縮因子。

圖1　DESA算法流程圖

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

(6)

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

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

(7)

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

2.2　算法實現(xiàn)過程

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

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

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

②每條人工魚進行覓食、聚群、追尾和隨機行為，更新自己的位置Xi|next。

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

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

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

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

圖2　DESA-AFSA流程圖

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

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

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

①測試函數(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種算法，分別對F1函數(shù)進行50次迭代的尋優(yōu)，F(xiàn)1函數(shù)平均優(yōu)化結果如圖4所示。

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

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

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

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

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

②測試函數(shù)F2。

|x|≤5,|y|≤5

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

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

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

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

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

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

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

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

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

4　結束語

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

參考文獻:

[1] 王闖.人工魚群算法的分析及改進[D].大連:大連海事大學,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] 朱旭輝,倪志偉,程美英.變步長自適應的改進人工魚群算法[J].計算機科學,2015(2):210-216.

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

[5] 費騰,張立毅,白煜,等.基于DNA的改進人工魚群算法[J].天津大學學報(自然科學與工程技術版),2016(6):581-588.

[6] 傅文淵,凌朝東.布朗運動模擬退火算法[J].計算機學報,2014,37(6):1301-1308.

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

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

[9] 劉愛軍,楊育,李斐,等.混沌模擬退火粒子群優(yōu)化算法研究及應用[J].浙江大學學報(工學版),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]袁澎,艾芊,趙媛媛.基于改進的遺傳-模擬退火算法和誤差度分析原理的PMU多目標優(yōu)化配置[J].中國電機工程學報,2014,34(13):2178-2187.

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

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

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

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