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

周金治，孟　柳

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

0　引言

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

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

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

1　基本算法

1.1　人工魚群算法原理

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

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

(1)

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

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

Xi|next=Xi+R×Dvisual

(2)

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

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

1.2　人工魚群算法缺陷分析

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

①收斂精度不高。

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

②尋優結果易于陷入局部最優的陷阱。

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

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

2.1　算法改進策略

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

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

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

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

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

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

(3)

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

(4)

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

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

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

⑤輸出最優解，算法結束。

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

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

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

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

①變異操作。隨機選擇本體以外的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)之間的隨機數；CR為交叉概率。

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

(7)

若新個體比當前個體更優，則替換掉當前個體；否則，保留當前個體。

2.2　算法實現過程

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

DESA-AFSA的實現過程如下。

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

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

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

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

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

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

圖2　DESA-AFSA流程圖

3　函數尋優仿真

為了驗證DESA-AFSA的有效性，對AFSA、SA-AFSA以及DESA-AFSA進行比較，并通過兩個經典函數進行優化仿真試驗。

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

①測試函數F1。

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

圖3　F1函數的三維圖像

采用3種算法，分別對F1函數進行50次迭代的尋優，F1函數平均優化結果如圖4所示。

圖4　F1函數平均優化結果

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

表1為F1函數的平均尋優結果分析。

表1　F1函數的平均尋優結果分析

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

②測試函數F2。

|x|≤5,|y|≤5

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

圖5　F2函數的三維圖像

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

圖6　F2函數平均優化結果

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

表2為F2函數的平均尋優結果分析。

表2　F2函數的平均尋優結果分析

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

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

4　結束語

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

參考文獻:

[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] 梁毓明,裴興環.粒子群優化人工魚群算法[J].計算機仿真,2016(6):213-217.

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

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

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

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

[9] 劉愛軍,楊育,李斐,等.混沌模擬退火粒子群優化算法研究及應用[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多目標優化配置[J].中國電機工程學報,2014,34(13):2178-2187.

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

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

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

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