基于函數(shù)動態(tài)遞減因子的布谷鳥算法

羅 東,王曉東,段博文

(西安工程大學(xué) 理學(xué)院,陜西 西安 710048)

0 引 言

布谷鳥搜索(CS)算法是由楊新社等通過模擬某些種類布谷鳥的繁衍寄生行為而提出的一種新穎的智能優(yōu)化算法,可用來解決最優(yōu)化問題[1].該算法因具備所需參數(shù)少，前期收斂速度快，易實(shí)現(xiàn)等優(yōu)點(diǎn)而被廣泛應(yīng)用.但CS算法存在后期收斂速度慢，求解精度差等問題.為此，眾多學(xué)者對CS算法進(jìn)行了優(yōu)化和改進(jìn)研究.例如：王凡等[2]提出在鳥窩位置處引入高斯擾動,增加解的多樣性,提高原始算法的收斂速度.文獻(xiàn)[3-4]將模擬退火思想引入CS算法,增強(qiáng)了算法跳出局部最優(yōu)解的能力,同時也提高了算法的收斂速度.文獻(xiàn)[5-6]利用PSO算法來優(yōu)化CS算法,將PSO算法用于CS算法的位置更新過程中,有效地提高了求解的精度和穩(wěn)定性.文獻(xiàn)[7-9]利用混沌原理來改進(jìn)CS算法,使其增加了種群的多樣性,提高了搜尋精度和搜尋速度.在步長改進(jìn)方面已有很多有效的方法，例如：Valian等[10]利用自適應(yīng)改變步長因子的方法提高了算法的收斂速度.任璐等[11]提出了一種基于逐維改進(jìn)的自適應(yīng)步長布谷鳥搜索算法,得到了較好的搜索效果.李榮雨等[12]利用動態(tài)慣性權(quán)重和記憶策略改進(jìn)步長,既加快了算法的收斂速度,又提高了算法的穩(wěn)定性.林要華等[13]將貝塔分布引入步長中,動態(tài)調(diào)整步長,取得了很好的成果.文獻(xiàn)[14]將解的適應(yīng)度引入到發(fā)現(xiàn)概率中,有效地提高了解的質(zhì)量. 彭建新等[15]提出了一種基于適應(yīng)值分配的改進(jìn)步長和發(fā)現(xiàn)概率的布谷鳥搜索算法,大幅度地提高了算法精度和收斂速度.在前人研究的基礎(chǔ)上,本文根據(jù)CS算法不同搜索階段,在步長和發(fā)現(xiàn)概率中引入余弦函數(shù)和指數(shù)函數(shù)，自適應(yīng)地對步長和發(fā)現(xiàn)概率進(jìn)行調(diào)整,以提高CS算法的收斂速度和求解精度.

1 改進(jìn)布谷鳥搜索算法

1.1 布谷鳥搜索算法

在布谷鳥搜索算法中,通過Lévy飛行對鳥窩進(jìn)行更新,位置更新公式如下:

(1)

楊新社教授等人將步長a取為

(2)

1.2 動態(tài)飛行步長

原布谷鳥算法中的a0=0.01,以一個定常數(shù)去限定步長a的變化范圍,由于算法在搜索前期大步長可以增強(qiáng)搜尋能力,在搜索后期小步長可以提高最優(yōu)解的精度,因此考慮在a0中引入余弦函數(shù),使其隨著迭代次數(shù)的增加在區(qū)間[0,1]上動態(tài)曲線遞減,文中設(shè)定最大迭代次數(shù)為500次,故a0改進(jìn)如下:

a0=0.001×tmax×cos(t/tmax).

(3)

原始CS算法中的a0恒等于0.01,本文將a0利用式(3)進(jìn)行替換,然后代入式(1)中,得到改進(jìn)后的自適應(yīng)Lévy飛行步長公式，即

(4)

1.3 動態(tài)發(fā)現(xiàn)概率

原始CS算法中的發(fā)現(xiàn)概率恒為0.25,而實(shí)際上不同的布谷鳥的發(fā)現(xiàn)概率應(yīng)有所不同,因此發(fā)現(xiàn)概率用一個變量去描述更為合理.在算法的搜尋前期,為了增加解的多樣性,將發(fā)現(xiàn)概率調(diào)整得大些,在算法的搜尋后期,減小發(fā)現(xiàn)概率,以便減少迭代次數(shù).因此將發(fā)現(xiàn)概率改進(jìn)為

pat=exp(t/tmax)×cos(t/tmax)×pab.

(5)

式中：pat為第t次迭代的發(fā)現(xiàn)概率,exp(t/tmax)×cos(t/tmax)為函數(shù)動態(tài)遞減因子,初始發(fā)現(xiàn)概率pab=0.4.ICS算法步驟為:

Step 1 設(shè)定算法參數(shù):鳥窩數(shù)量m,維數(shù)n,最大迭代次數(shù),搜尋上下界,初始化鳥窩位置并計(jì)算所有鳥窩位置的適應(yīng)度.

Step 2 對每個鳥窩采用動態(tài)調(diào)整步長的Lévy飛行(式(4)),產(chǎn)生新的鳥窩.

Step 3 將新鳥窩的適應(yīng)度與舊鳥窩適應(yīng)度作比較,保留適應(yīng)度更好的鳥窩.

Step 4 按照動態(tài)調(diào)整的發(fā)現(xiàn)概率去隨機(jī)淘汰部分解(式(5)),然后進(jìn)入隨機(jī)偏好游動過程,產(chǎn)生新解來代替被淘汰的解,并保留最好的一組鳥窩位置.

Step 5 判斷Step 4中最好的位置是否滿足算法終止條件,若滿足則輸出全局最優(yōu)鳥窩位置和適應(yīng)度值,否則進(jìn)入Step 2中繼續(xù)搜尋最優(yōu)解.

2 仿真實(shí)驗(yàn)

為了檢驗(yàn)改進(jìn)后的布谷鳥搜索算法的性能,采用3個常用的測試函數(shù)對基本布谷鳥搜索算法和改進(jìn)后的布谷鳥搜索算法進(jìn)行對比實(shí)驗(yàn).設(shè)置鳥窩數(shù)量m=25,最大迭代次數(shù)為500,ICS算法和CS算法均獨(dú)立運(yùn)行100次,測試函數(shù)見表1.圖1～3為測試函數(shù)最優(yōu)值變化趨勢圖,表2為測試函數(shù)最優(yōu)解位置以及兩種算法的搜尋結(jié)果,表3為兩種算法搜索到的最優(yōu)值情況.

表 1 測試函數(shù)

圖 1 Sphere函數(shù)最優(yōu)值變化趨勢圖 圖 2 Beale函數(shù)最優(yōu)值變化趨勢圖 Fig.1 Diagram of the optimal value Fig.2 Diagram of the optimal value change of Sphere function change of Beale function

圖 3 Lévy函數(shù)最優(yōu)值變化趨勢圖Fig.3 Diagram of the optimal value change of Lévy function

對圖1進(jìn)行觀察,發(fā)現(xiàn)ICS算法在迭代初期就出現(xiàn)拐點(diǎn)，比CS算法出現(xiàn)拐點(diǎn)更早,說明ICS算法比CS算法提前進(jìn)入局部最優(yōu),隨著迭代次數(shù)的增加,兩種算法均出現(xiàn)了多次拐點(diǎn),然后跳出了局部最優(yōu),但I(xiàn)CS算法在第120次迭代時收斂到最優(yōu)值0,CS算法則在迭代240次收斂到最優(yōu)值0,這說明了ICS算法率先達(dá)到最優(yōu)值. 從圖2可以看出,兩種算法在迭代前期收斂速度很快,ICS算法在第10次迭代就出現(xiàn)了拐點(diǎn),CS算法在第15次迭代出現(xiàn)拐點(diǎn),然后二者跳出局部最優(yōu),但是可以看出ICS算法比CS算法更早收斂到最優(yōu)值0. 從圖3可以看出,對于Lévy函數(shù)來說,ICS算法在第20次出現(xiàn)拐點(diǎn),然后迅速收斂,CS算法在第25次迭代出現(xiàn)拐點(diǎn),二者在后期迭代過程中均出現(xiàn)多次拐點(diǎn),但I(xiàn)CS算法在迭代220次收斂于最優(yōu)值0,而CS算法在500次迭代時仍沒有收斂,這說明改進(jìn)后的算法收斂速度有較大改善.圖1～3說明ICS算法比CS算法擁有更快的收斂速度,具有更強(qiáng)大的全局搜尋能力.

在n=30的條件下,通過搜尋Sphere函數(shù)、Beale函數(shù)及Lévy函數(shù)最優(yōu)值位置來測試ICS算法和CS算法的精度,測試結(jié)果如下:

Sphere函數(shù):測試函數(shù)最優(yōu)值位置:(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0).

CS算法搜尋的最優(yōu)值位置:(0.028 9,-0.014 8,-0.020 7,0.017 8,0.029 4,0.008 3,-0.014 9,-0.000 9,-0.015 1,0.037 5,0.019 9,0.001 4,0.001 1,0.010 8,0.016 2,-0.037 4,0.013 7,-0.004 3,0.008 5,0.023 4,0.004 5,-0.000 2,0.011 6,0.011 9,0.008 7,0.009 1,0.030 0,-0.006 9,0.002 8,0.011 4).

ICS算法搜尋的最優(yōu)值位置:(0.000 2,0.000 3,-0.000 4,0.000 6,0.000 2,-0.000 3,-0.000 5,-0.001 0,-0.000 0,0.000 1,-0.000 7,0.000 7,-0.000 9,0.000 4,0.000 5,0.000 3,-0.000 1,0.000 5,-0.000 2,0.000 3,0.000 3,0.000 5,-0.000 0,-0.000 3,0.000 1,-0.000 4,0.000 3,0.000 5,0.000 5,0.000 3).

Beale函數(shù):測試函數(shù)最優(yōu)值位置為(3,0.5).

CS算法搜尋的最優(yōu)值位置:(3,0.5).

ICS算法搜尋的最優(yōu)值位置:(3,0.5).

Lévy函數(shù):測試函數(shù)最優(yōu)值位置:(1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1).

CS算法搜尋的最優(yōu)值位置:(0.935 4,0.996 3,-0.142 5,0.907 7,0.854 8,0.828 0,0.798 0,0.680 3,-0.257 7,1.151 9,1.220 4,0.915 3,-0.199 0,0.662 1,-0.187 0,-0.174 9,-0.183 2,0.993 1,1.146 3,-0.262 2,0.497 6,-0.189 0,1.014 5,1.114 1,0.890 4,0.653 4,0.123 3,0.788 2,1.091 6,1.002 2).

ICS算法搜尋的最優(yōu)值位置:(1.003 1,0.999 9,0.998 8,0.998 4,1.000 4,0.999 9,0.999 3,0.993 4,0.994 7,0.994 4,0.997 2,1.000 4,1.005 7,0.995 3,1.002 9,0.994 8,1.000 1,0.998 8,1.006 9,0.997 8,1.000 1,1.000 5,0.990 2,0.997 8, 0.997 7, 0.995 8,0.998 1,1.004 7,1.000 8,0.999 1).

表 2 測試函數(shù)最優(yōu)解位置以及兩種算法搜尋結(jié)果對比

因?yàn)樽顑?yōu)值位置處坐標(biāo)中數(shù)字過多,表2中算法搜尋到最優(yōu)值位置處省略其中間部分?jǐn)?shù)字.

歐氏距離表示CS算法和ICS算法搜尋的最優(yōu)值位置與測試函數(shù)最優(yōu)值位置的距離.對于Sphere函數(shù),由于 0.096 7>0.002 5,這說明ICS算法搜尋的最優(yōu)值位置更加接近測試函數(shù)最優(yōu)值位置. 對于Beale函數(shù),CS算法和ICS算法搜尋的最優(yōu)值位置與函數(shù)最優(yōu)值相同.對于Lévy函數(shù),由于2.603 7>0.020 5,這說明ICS算法比CS算法搜尋到的最優(yōu)值位置更精確. 所以ICS算法比CS算法在搜尋精度方面有很大提升.

表 3 兩種算法搜索到的最優(yōu)值情況

在表3中,最優(yōu)值、最差值和平均值分別表示兩種算法在獨(dú)立運(yùn)行100次后搜索結(jié)果中最好的一次、最差的一次和平均值. 由表3可知,對于Sphere函數(shù),ICS算法搜索到的最優(yōu)值、最差值和平均值均更加接近于測試函數(shù)本身的最優(yōu)值0,這說明ICS算法更加優(yōu)于CS算法;對于Beale函數(shù),ICS算法搜索到的最優(yōu)值、最差值和平均值都為0;對于Lévy函數(shù),改進(jìn)后的算法明顯比CS算法更加接近測試函數(shù)本身的最優(yōu)值0,再一次證明了ICS算法優(yōu)于CS算法.

3 結(jié)束語

本文針對步長和發(fā)現(xiàn)概率進(jìn)行了自適應(yīng)調(diào)整,在步長和發(fā)現(xiàn)概率中加入余弦函數(shù)和指數(shù)函數(shù),動態(tài)地調(diào)整步長和發(fā)現(xiàn)概率.利用3種測試函數(shù)驗(yàn)證了ICS算法無論在收斂速度還是求解精度方面均優(yōu)于CS算法.