基于隊長策略捕魚算法的改進及性能測試

梁 曉 龍

(石家莊職業技術學院 食品與藥品工程系,河北 石家莊 050800)

0 引言

捕魚算法(an optimization algorithm on using fishing strategy,簡寫為“FSOA”)是模擬漁夫捕魚行為策略而提出的一種群智能優化算法[1-2].該算法因具有魯棒性強、收斂速度快、搜索策略簡單、容易編程實現等優點,已被廣泛應用于水資源預測[3]、車間調度[4]、大數據中用戶特征信息優化定位[5]、無線電頻譜分配[6]等諸多領域,并取得了較好的效果.捕魚算法因其良好的尋優性能而被不斷改進和研究,有自適應精英捕魚算法[7]、與蜜蜂進化型遺傳算法相結合的算法[8]、改進二進制捕魚算法等[9].智能優化算法是通過模擬自然界生物行為或者自然現象規律而提出的搜索策略,如遺傳算法、粒子群算法、蟻群算法、灰狼算法、鯨魚算法、蝙蝠算法、布谷鳥算法等[10-13].諸多學者對智能優化算法的尋優性能、搜索策略、算法復合策略、推廣應用展開了研究,極大地豐富了優化技術理論,推動了智能優化算法的發展.傳統的優化方法(線性規劃法、最速下降法、二分法等)僅適合解決簡單問題,遇到多維度、非連續、多極值的問題時,則存在收斂速度慢、計算量隨維度增加呈指數增長、容易陷入局部極值等問題.智能優化算法在解決復雜問題、尋找較優方案時具有明顯的優勢.

本文針對捕魚算法缺少信息共享機制、對當前群體最優信息利用不充分的問題,提出隊長策略捕魚算法(fishing algorithm based on captain strategy,簡寫為“C-FSOA”),以期提升捕魚算法的尋優性能.

1 基于隊長策略捕魚算法的改進

1.1 捕魚算法的假設和方式

捕魚算法模擬漁夫捕魚行為策略基于以下假設:(1)搜索空間的靜態性和初始未知性.搜索空間的靜態性是指搜索空間內任意點的適應度值不隨搜索的進行而改變;初始未知性是指在搜索開始前,對搜索空間內任意點的適應度值均是未知的.(2)漁夫的趨優性、貪婪性和排斥性.趨優性是指漁夫總是趨向于在魚群密度大的區域內搜索;貪婪性是指對于魚群密度較大的區域,漁夫會用網眼更小的漁網捕魚以期捕獲更多的魚;排斥性是指漁夫之間相互排斥,避免在相同區域內搜索.

捕魚算法中各漁夫根據自己的狀態分別按照移動搜索、收縮搜索和隨機搜索3種策略獨立搜索,能夠較好地避免陷入局部極值,并最終搜索到最優解.

1.2 隊長策略

各漁夫按照移動搜索、收縮搜索和隨機搜索各自獨立搜索,不能充分發揮群體行為中最優個體的指導作用.針對這一現象,提出隊長策略,即所有漁夫完成一代搜索后,漁夫群體共享搜索信息,找出當前最優個體確定為隊長,在之后的搜索進程中處于劣勢的漁夫群體(尋優適應度值排名靠后的漁夫群體)認為隊長周圍的魚群密度會更高,在搜索過程中選擇跟隨隊長進行搜索的策略.因漁夫之間的排斥性,仍然保留處于優勢的漁夫群體(尋優適應度值排名靠前的漁夫群體)獨立搜索,從而避免過早陷入局部極值.

1.3 實現步驟

步驟一,初始化.N個漁夫隨機選擇自己在搜索空間D內的初始位置

步驟二,獨立搜索.各漁夫i在當前位置xi為中心的鄰域內,隨機選取p個搜索點,見公式(1),并求其適應度值).

其中,N為群體規模;rk∈(0,N]為漁夫搜索半徑調控系數;T為設定的迭代閾值;t為漁夫搜索迭代次數；為t代漁夫i的搜索中心;為t代漁夫i的第k次搜索;rand(0,1)為隨機數,模擬漁夫撒網的不確定性;A∈[1,10]為收縮調控系數;p為漁夫在當前位置的搜索次數.

步驟三,移動搜索.漁夫i當前搜索的最大適應度值|i=1,2,…,N;k=1,2,…p},判斷其是否大于原中心位置xi的適應度值,若f()＞f(),則漁夫i的中心位置移動至;反之,漁夫i中心位置不變,繼續搜索.

跳出機制:若搜索到的最優解滿足設定的誤差要求或迭代次數達到迭代閾值T,跳出搜索,輸出最優解,否則搜索繼續.

步驟四,信息共享.當漁夫獨立搜索進行到T1代后,共享所有漁夫的當前適應度值,并對漁夫群體按其適應度值排序.取適應度值最大的漁夫為隊長,適應度值較小的[τ(N-1)]個(τ為追隨控制系數,控制追隨隊長移動的漁夫數量)漁夫向隊長所在位置移動,并進行搜索,遷移方式見公式(2).剩余適應度值較大的N-[τ(N-1)]個漁夫繼續保持獨立搜索.

其中,為隊長的當前中心位置；為漁夫i當前中心到隊長所處中心的向量;κ∈(0,1)為遷移控制系數,越靠近1,表示漁夫個體對于隊長的遷移程度越高.

步驟五,遷移.漁夫在向隊長移動之后在新的位置獨立搜索,轉入步驟二.

2 C-FSOA搜索性能測試

2.1 函數測試

為測試C FSOA 尋優性能,選取能夠反映尋優速率、全局收斂性能的6 個典型函數進行測試[11],并與FSOA 的尋優性能進行比較.6 個測試函數表達式、約束區間及理論最優解見表1.其中,DeJong F1 函數為單峰函數;Camel 函數、Schaffer F6函數、Shubert函數為多峰函數,存在較多的局部極值,容易使優化算法陷入局部極值,影響其尋優速率效果,這些函數能夠較好地反映出被測試算法的全局收斂性能;Rosenbrock函數為典型的單峰病態函數,其理論全局最優解位于函數的一個狹窄凹區間內,尋找難度較大,運用此函數能夠較好地反映出被測試算法的優化效率.

作為對比測試,FSOA 算法和C-FSOA 算法在測試過程中群體規模N、迭代閾值T、初始化狀態等參數設置均相同,見表2.

表2 FSOA 與C-FSOA 參數設置

2.2 FSOA 和C-FSOA 測試結果分析

2.2.1 尋優速率

在參數設定相同的條件下,FSOA 和C-FSOA分別對6個測試函數迭代10次.為方便表示,各測試函數的適應度值設置為:G1=1/(2+f1),G1=1/(1+f2),G3=1/(1+f3),G4=1/(188+f4),G5=1/(1+f5),G6=1/(1+f6).兩種算法對6個測試函數的適應度值隨迭代次數t變化趨勢見圖1.

圖1 FSOA 和C FSOA 對6個測試函數適應度值G j 的迭代曲線

由圖1可以看出,測試函數f1,f2,f3,f5,f6的C-FSOA 尋優速率具有明顯優勢;因多峰測試函數f4存在較多的局部極值,FSOA 尋優速率更快一些.整體測試反映出C-FSOA 在信息最優個體“隊長”指導下尋優速率有明顯的提升.

2.2.2 尋優性能

為進一步驗證算法的尋優性能,在參數設定相同條件下,FSOA 和C-FSOA 分別對6個測試函數獨立求解100次.分別記錄100次尋優結果的最優解、平均值、標準差和最差解,以此分析兩種優化算法的尋優性能.數據見表3.

表3 FSOA 與C-FSOA 測試結果比較

由表3 可以看出,對于Rosenbrock 函數、De-Jong F1函數、Rosenbrock 2函數,C-FSOA 優化結果的最優解、平均值、標準差和最差解較與FSOA優化的結果均提高了幾個數量級;對于Camel函數,兩種算法均找出了最優解,但是C FSOA 的尋優結果標準差要比FSOA 的尋優結果標準差小兩個數量級,表明C-FSOA 尋優穩定性更好;對測試函數Schaffer F6函數的尋優效果,兩種算法的測試結果相當,均能找到理論最優解;對于Shubert函數,C-FSOA 尋優結果中最差解、平均值和標準差均劣于FSOA 尋優結果,但也搜索出了理論最優解,尋優性能也屬合格.綜合來看,C-FSOA 在尋優速率、穩定性方面均有明顯提升.

3 結論

在參數設置相同的情況下,C-FSOA 算法的穩定性和收斂效率相較于FSOA均有所提高;而針對局部極值較多的函數尋優性能有所降低,其原因是部分漁夫在追隨隊長捕魚之后會影響漁夫的多樣性,對多極值函數的搜索效率會相應的降低,但是也搜索到了最優解,對該函數的搜索也是合格的.測試結果表明,基于隊長策略的捕魚算法利用群體最優個體信息能夠在一定程度上提升算法的搜索效率,原理簡單,容易編程實現,具有一定的推廣應用價值.