一種人工魚群蛙跳混合優(yōu)化算法

姜慧楠， 張向鋒

(上海電機學院 電氣學院, 上海 201306)

人工魚群算法(Artificial Fish Swarm Algori-thm, AFSA)，是一種根據(jù)魚群覓食行為的優(yōu)化算法[1]。算法以模仿自然界的魚群尋食過程來求得問題的最優(yōu)解，它最初的收斂速度較快，但是后期收斂速度慢，因此，適用于精度要求不高的尋優(yōu)問題[2-3]。蛙跳算法(Shuffled Frog Leaping Algori-thm, SFLA)是一種新的結(jié)合了全局搜索和局部更新的元啟發(fā)式協(xié)同搜索算法[4]。SFLA求解速度快且全局尋優(yōu)能力強，但存在前期收斂速度慢的問題。

AFSA因具有收斂速度快、計算原理簡單等優(yōu)勢，得到了國內(nèi)外學者的廣泛關(guān)注。文獻[5]對適應(yīng)度值最好的人工魚利用最速下降法進行更新，提高魚群的整體水平；文獻[6]采用引入對稱正態(tài)隨機行為及自適應(yīng)調(diào)整行為參數(shù)，使得系統(tǒng)的收斂速度更佳；文獻[7]驗證了一種基于DNA改進的AFSA；文獻[8]將禁忌搜索策略融入到AFSA尋優(yōu)過程中，并在求解車間調(diào)度問題中取得了比較好的結(jié)果；文獻[9-10]采用對魚群行為的改變，提高了AFSA的搜索速度。文獻[11-12]為克服SFLA存在的問題，對全局及局部做出改進，提出一種改進的SFLA；文獻[13-14]通過對步長公式的改變及引入影響因子的方法，提升了SFLA的搜索能力；文獻[15-16]通過借鑒優(yōu)化及搜索策略的思想，使得最差青蛙的位置趨向最佳，提高了SFLA搜索的速度。

針對SFLA在后期收斂速度慢、易陷入局部最優(yōu)和精度低等問題，本文將結(jié)合AFSA前期收斂速度快和SFLA局部搜索能力強的優(yōu)勢，通過將兩種仿生算法聯(lián)合運用，提出一種人工魚群-蛙跳混合優(yōu)化算法(Artificial Fish Swarm Algori-thm-Shuffled Frog Leaping Algorithm, AFSA-SFLA)。

1 人工魚群算法及蛙跳算法

1.1 AFSA基本原理

魚群的主要行為包括魚群初始化、覓食行為、聚群行為、追尾行為、隨機行為[17]。其主要行為如下：

(1) 魚群初始化。魚群中的每一條人工魚是在給定范圍內(nèi)產(chǎn)生的隨機數(shù)組。

(2) 覓食行為。假設(shè)當前人工魚的狀況為Xi，在其感知的范圍內(nèi)隨機選擇一個狀況Xj，如果求極大值問題，Yi為第i條人工魚當前所在食物濃度(Yi

(3) 聚群行為。設(shè)當前人工魚的狀況為Xi，探究當前領(lǐng)域內(nèi)(即di，jδYi(δ為擁擠度)，說明同伴中央有較多的食物且不太擁擠，則朝同伴中央的位置行進一步，否則實施覓食行為。

(4) 追尾行為。設(shè)當前人工魚的狀況為Xi，試探當前領(lǐng)域內(nèi)(即di，jδYi，說明同伴Xj的狀態(tài)有較多的食物且不太擁擠，則朝同伴的Xj的位置行進一步，否則實施覓食行為。

(5) 隨機行為。隨機行為的實現(xiàn)比較簡單，就是在視線中隨機抉擇一個情況，然后向該方向行進，即Xi的下一個動作為

X′i=Xi+r·V

(1)

式中：r是[-1，1]區(qū)間的隨機數(shù)。

1.2 SFLA基本原理

SFLA是模擬青蛙在尋食的過程當中，青蛙群體通過按子群分類進行信息交換的進展，將全局搜索與子群局部搜索相結(jié)合，使算法朝著全局最優(yōu)解的方向進化[18]。

(1) 全局搜索。全局搜索的布置如下：① 設(shè)置SFLA參數(shù)種群分組數(shù)m，每組青蛙包含的青蛙個數(shù)n，組內(nèi)迭代次數(shù)Ne，最大、最小步長分別為swmax、swmin，種群總的進化代數(shù)N′max，青蛙位置的最大、最小值分別為Pmax、Pmin；② 隨機初始化青蛙的種群，共生成F只青蛙，簡記為P={P1，P2，…，PF}，其中Pi代表第i個解(0≤i≤F)，Pi={Pi1，Pi2，…，Pid}，d為解的維數(shù)，每一只青蛙代表著一種可行的解；③ 設(shè)Ff(Pi)為適應(yīng)度函數(shù)，計算P中的每一只青蛙的適應(yīng)度值，并將其進行降序處理，同時將第一個適應(yīng)度值所對應(yīng)的Pi記錄為全局最優(yōu)青蛙gx，并將排序后的青蛙放置P中；④ 將P中的F只青蛙，分成m組，每一組包含n只青蛙。將P中第1只青蛙放置第一組，依次第m只青蛙放置第m組。第m+1只青蛙放置第1組，依次第m+m只青蛙放置第m組，依次共循環(huán)n次，F(xiàn)只青蛙分組完成；⑤ 每個子群執(zhí)行子群局部搜索，具體步驟見局部搜索；⑥判別是不是達到了最大迭代次數(shù)N′max，若達到了則算法結(jié)束，反之，重新混合所有的青蛙，執(zhí)行步驟③。

(2) 局部搜索。局部搜索的布置如下：① 設(shè)j=1，用于記錄每組內(nèi)的迭代次數(shù)；② 關(guān)于每一組青蛙適應(yīng)度值按降序排序，pb代表著每一組的最優(yōu)青蛙，pw代表著每一組的最差青蛙；③ 組內(nèi)更新，利用式(2)計算最差青蛙的移動步長sw1，若Ff(pwnew)>Ff(pwold)，執(zhí)行步驟⑥，否則執(zhí)行步驟④；

sw1=r·(pb-pw)swmin≤sw1≤swmax

(2)

pwnew=pwold+sw1

(3)

④ 全局最優(yōu)更新。利用式(4)計算最差青蛙的移動步長sw2，若Ff(pwnew)>Ff(pwold)，執(zhí)行步驟⑥，不然執(zhí)行步驟⑤；

sw2=r·(gx-pw)swmin≤sw2≤swmax

(4)

pwnew=pwold+sw2

(5)

⑤ 隨機更新。利用式(6)計算最差青蛙的移動步長sw3；

sw3=Pmax·r(1，d)swmin≤sw3≤swmax

(6)

pwnew=pwold+sw3

(7)

⑥ 將pwnew代替pwold，判別j>Ne是否成立，若成立則一組的局部搜索完成，反之，j=j+1，執(zhí)行步驟②。

圖1 混合算法流程圖

2 人工魚群蛙跳混合優(yōu)化算法

針對AFSA和SFLA算法優(yōu)缺點，本文提出一種AFSA-SFLA，該算法首先采用AFSA收斂速度快的優(yōu)勢快速尋找到待求解參數(shù)全局最優(yōu)解所在區(qū)域。后期為SFLA利用前期AFSA的迭代結(jié)果，進行SFLA的初始化。AFSA-SFLA的具體流程如圖1所示。具體步驟如下：① 設(shè)定主要初始參數(shù)，在給定的規(guī)模內(nèi)初始化魚群；②i=1作為一個循環(huán)變量來循環(huán)記錄人工魚的個數(shù)，人工魚的數(shù)目為N；③ 魚群執(zhí)行聚群行為得到(X1，Y1)，執(zhí)行追尾行為得到(X2，Y2)；④ 若Y1>Y2則Xi=X1，不然Xi=X2；⑤ 判別i>N是否成立，若成立執(zhí)行步驟⑥，不然i=i+1，執(zhí)行步驟③，gen=gen+1；⑥ 判別gen>Nmax是否成立，若成立則執(zhí)行步驟⑦，反之，執(zhí)行步驟②；⑦ 切換至SFLA，采用AFSA的最后一次迭代產(chǎn)生的人工魚群進行SFLA的初始化，設(shè)置SFLA參數(shù)種群分組數(shù)m、每組青蛙包含的青蛙個數(shù)n、組內(nèi)迭代數(shù)Ne、最大步長swmax、種群總的進化代數(shù)N′max，青蛙位置最大、最小值分別為Pmax、Pmin，循環(huán)變量ii=1。其中特意要說明的是初始化青蛙種群時，將AFSA迭代后的結(jié)果，取占取青蛙種群個數(shù)的L倍賦值給青蛙種群(0N′max是不是成立，若成立則輸出參數(shù)最優(yōu)值，不然ii=ii+1執(zhí)行步驟⑧。

3 仿真實驗與分析

本文采取Rastrigin函數(shù)、Griewank函數(shù)和Rosenbrock函數(shù)作為基準函數(shù)，這3個函數(shù)都具有數(shù)個局部最小值點和一個全局最小值點，可以很好地測驗算法規(guī)避局部極值搜索全局最優(yōu)的能力，標準測試函數(shù)如表1所示。

3.1 參數(shù)設(shè)置與測試函數(shù)

實驗中主要參數(shù)設(shè)置如下：人工魚的數(shù)目fishnum=100，最多試探次數(shù)try_number=100，最大步長step=0.1，蛙跳組內(nèi)迭代次數(shù)Ne=25，種群分組數(shù)m=10。本實驗的仿真軟件如下：Intel i3 CPU 2.40 GHz，RAM 4.00 GB，Window 2007操作系統(tǒng)，MatLab2016b。

表1 標準測試函數(shù)

3.2 仿真結(jié)果分析

3.2.1 固定迭代次數(shù)下算法求解精度對比 采用不同的維數(shù)d消除算法的隨機性干擾，在維數(shù)d為10和20時，對每一個測試函數(shù)分別用SFLA、AFSA-SFLA各自進行20次實驗，仿真結(jié)果如表2所示。圖2～圖7為3個基準測試函數(shù)在不同維數(shù)下的優(yōu)化結(jié)果圖，其中橫軸為迭代的次數(shù)，縱軸為log化的函數(shù)最優(yōu)解。

表2 3種基準測試函數(shù)仿真數(shù)據(jù)結(jié)果

圖2 Griewank函數(shù)在d=10時的進化曲線

圖3 Griewank函數(shù)在d=20時的進化曲線

圖4 Rosenbrock函數(shù)在d=10時的進化曲線

圖6 Rastrigin函數(shù)在d=10時的進化曲線

圖7 Rastrigin函數(shù)在d=20時的進化曲線

由表2可以看出，當維數(shù)d相同時，AFSA-SFLA的尋優(yōu)結(jié)果優(yōu)于單獨SFLA的尋優(yōu)結(jié)果。當維數(shù)d由10增大至20時，對Griewank函數(shù)，SFLA平均尋優(yōu)結(jié)果由1.106 29增大至2.256 83，增大了2.04倍，AFSA-SFLA平均尋優(yōu)結(jié)果由0.000 70增大至0.015 42，增大了22倍。當維數(shù)d由10增大至20時，對Rosenbrock函數(shù)，SFLA平均尋優(yōu)結(jié)果由10.054 70增大至87.308 12，增大了8.6倍，AFSA-SFLA的平均尋優(yōu)結(jié)果由3.574 68增大至7.456 81，增大了2.08倍，說明AFSA-SFLA相對SFLA對該函數(shù)的維數(shù)適應(yīng)性更好。當維數(shù)d由10增大至20時，對Rastrigin函數(shù)，SFLA平均尋優(yōu)結(jié)果由0.167 38增大至4.361 75，增大了26倍，AFSA-SFLA的平均尋優(yōu)結(jié)果由1.03×10-4，增大至0.102 65，增大了996倍，雖然AFSA-SFLA增大的倍數(shù)較大，但是AFSA-SFLA的求解精度優(yōu)于SFLA的求解精度。

由圖2可知，對于Griewank函數(shù)，SFLA在后期迭代效果比較明顯，前期迭代的效果不佳，AFSA-SFLA相對SFLA能快速地在其前期找到可行解，并于迭代70次左右收斂。由圖4和圖5可知，對于Rosenbrock函數(shù)在維數(shù)為20時，SFLA的平均尋優(yōu)曲線接近直線，開始就陷入局部最優(yōu)，全局尋優(yōu)能力不強。由圖6和7可以看出，對于Rastrigin函數(shù)，AFSA-SFLA在前期尋優(yōu)結(jié)果明顯，SFLA收斂慢且平均尋優(yōu)結(jié)果遠大于AFSA-SFLA的尋優(yōu)結(jié)果。

綜合圖2～7可知，SFLA的尋優(yōu)結(jié)果要遠小于AFSA-SFLA的尋優(yōu)結(jié)果，且在高緯數(shù)時更易陷入局部最優(yōu)解，而AFSA-SFLA能更快地找到全局最優(yōu)解所在的區(qū)域，迭代速度快，尋優(yōu)結(jié)果更佳。需要指出的是AFSA-SFLA前段使用AFSA，并將AFSA最后一次迭代產(chǎn)生的人工魚群按照適應(yīng)度值大小降序排列，取前一定比例賦值給青蛙種群，使得青蛙種群更接近最優(yōu)范圍，因而其收斂曲線在前期能快速的找到最優(yōu)解所在的區(qū)域，且迭代較為緩慢。

3.2.2 指定精度下算法迭代次數(shù)對比 表3為AFSA-SFLA在指定精度下求解基準函數(shù)迭代次數(shù)的對比，其中成功率是指算法達到指定求解精度的實驗次數(shù)除以總實驗次數(shù)20。Griewank函數(shù)、Rosenbrock函數(shù)、Rastrigin函數(shù)指定精度分別為10-1、10、10-1，最大迭代次數(shù)為300次，即算法迭代300次仍未達到指定精度時，表示迭代失敗。

表3 指定精度下算法迭代次數(shù)對比

從表3中可以看出，在指定收斂精度下，對Griewank函數(shù)SFLA算法達到指定精度的成功率只有5%，平均迭代次數(shù)為263次，對Rosenbrock函數(shù)SFLA算法達到指定精度的成功率只有66.67%，平均迭代次數(shù)為156次，對Rastrigin函數(shù)SFLA算法未能達到指定精度，平均迭代次數(shù)為300次。AFSA-SFLA對3個基準測試函數(shù)成功率均為100%，并且迭代次數(shù)比SFLA迭代次數(shù)少很多。

以上仿真結(jié)果分析表明，在指定精度下，AFSA-SFLA的成功率、穩(wěn)定性和計算效率均比SFLA算法有一定優(yōu)勢。

3.2.3 與他算法尋優(yōu)結(jié)果對比分析 粒子群算法(Particle Swarm Optimization, PSO)的參數(shù)設(shè)置為速度更新參數(shù)C1=1.494 45、C2=1.494 45，種群規(guī)模Spop=100，AFSA及AFSA-SFLA的參數(shù)設(shè)置同3.1小節(jié)的參數(shù)設(shè)置一樣。在d維數(shù)為10時對于每一個測試函數(shù)均采用AFSA、PSO、AFSA-SFLA各自進展20次試驗，仿真數(shù)據(jù)如表4所示。

由表4中的仿真數(shù)據(jù)能看出，對于Griewank函數(shù)，AFSA-SFLA的平均尋優(yōu)結(jié)果為0.000 70，PSO的平均尋優(yōu)結(jié)果為0.004 01，AFSA的平均尋優(yōu)結(jié)果為0.083 99，AFSA-SFLA的平均尋優(yōu)結(jié)果是PSO的平均尋優(yōu)結(jié)果的5.74倍，是AFSA的平均尋優(yōu)結(jié)果的119.48倍；對于Rosenbrock函數(shù)，AFSA-SFLA的平均尋優(yōu)結(jié)果為3.574 68，PSO的平均尋優(yōu)結(jié)果為9.659 31，AFSA的平均尋優(yōu)結(jié)果為11.326 70，AFSA-SFLA的平均尋優(yōu)結(jié)果是PSO的平均尋優(yōu)結(jié)果的2.70倍，是AFSA的平均尋優(yōu)結(jié)果的3.17倍；對于Rastrigin函數(shù)AFSA-SFLA的平均尋優(yōu)結(jié)果為1.03×104，PSO的平均尋優(yōu)結(jié)果為5.912 86，AFSA的平均尋優(yōu)結(jié)果為49.499 70，AFSA-SFLA的平均尋優(yōu)結(jié)果是PSO的平均尋優(yōu)結(jié)果的5.74×104倍，是AFSA的平均尋優(yōu)結(jié)果的4.806×105倍。由此可以看出在維數(shù)相同的情況下AFSA-SFLA的尋優(yōu)精度是最小的，尋優(yōu)能力是較強的。

4 參數(shù)L值對AFSA-SFLA的影響分析

初始化青蛙種群過程中，將AFSA最后一次產(chǎn)生的人工魚群依據(jù)適應(yīng)度值大小降序排序，取占青蛙種群個數(shù)的L倍賦值給青蛙種群，作為初始化青蛙種群的一部分，剩余青蛙種群則依照常規(guī)的方法進行青蛙的初始化，L為采用人工魚群初始化青蛙的個數(shù)占青蛙種群總個數(shù)的比例。分析不同比例對AFSA-SFLA所帶來的影響，分別取L為0.3、0.5、0.7時對測試函數(shù)進行優(yōu)化實驗，函數(shù)參數(shù)設(shè)定同3.1節(jié)參數(shù)設(shè)定一樣，其中d為20，每組進行20次實驗，圖8～圖10給出了L值不同的情況下，AFSA-SFLA對測試函數(shù)的平均優(yōu)化結(jié)果。

圖8 L取值不同時對Griewank函數(shù)的影響

圖9 L取值不同時對Rosenbrock函數(shù)的影響

圖10 L取值不同時對Rastrigin函數(shù)的影響

由圖8可知，對Griewank函數(shù)，L為0.5時，平均尋優(yōu)優(yōu)化結(jié)果最好，且L為0.3時在迭代40次左右收斂，而L為0.5時在迭代90次左右仍有迭代的趨勢。由圖9可知：對Rosenbrock函數(shù)L為0.3時迭代效果最好，且平均尋優(yōu)結(jié)果最好。由圖10可知，對Rastrigin函數(shù)L為0.7時平均尋優(yōu)結(jié)果最好，但L為0.5時的迭代效果是較好的。由此可見應(yīng)根據(jù)不同的目標函數(shù)選取合適的L值。

5 結(jié) 論

為改善SFLA前期收斂速度慢及易陷入局部最優(yōu)的問題，本文提出了一種人工魚群-蛙跳混合優(yōu)化算法。算法前期采用ASFA前期搜索速度快的優(yōu)勢，迅速找到可能的最優(yōu)解，后期切換至SFLA，初始化青蛙種群時，將ASFA迭代后的結(jié)果，取一定比例賦值給青蛙種群，提高了青蛙種群的質(zhì)量。通過與ASFA、SFLA、PSO 3種算法的比較與分析驗證了混合算法能有效的避免陷入局部最優(yōu)，且優(yōu)化精度高。分析混合算法中初始青蛙種群中前期AFSA迭代結(jié)果所占的比例對混合算法的影響，結(jié)果表明：不同L值對函數(shù)的影響不同，故應(yīng)根據(jù)不同的目標函數(shù)選擇不同的L值。