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

梁 曉 龍

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

0 引言

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

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

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

1.1 捕魚算法的假設和方式

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

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

1.2 隊長策略

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

1.3 實現(xiàn)步驟

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

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

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

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

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

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

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

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

2 C-FSOA搜索性能測試

2.1 函數(shù)測試

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

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

表2 FSOA 與C-FSOA 參數(shù)設置

2.2 FSOA 和C-FSOA 測試結(jié)果分析

2.2.1 尋優(yōu)速率

在參數(shù)設定相同的條件下,FSOA 和C-FSOA分別對6個測試函數(shù)迭代10次.為方便表示,各測試函數(shù)的適應度值設置為: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個測試函數(shù)的適應度值隨迭代次數(shù)t變化趨勢見圖1.

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

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

2.2.2 尋優(yōu)性能

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

表3 FSOA 與C-FSOA 測試結(jié)果比較

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

3 結(jié)論

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