羅 東,王曉東,段博文

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

0 引 言

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

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

1.1 布谷鳥(niǎo)搜索算法

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

(1)

楊新社教授等人將步長(zhǎng)a取為

(2)

1.2 動(dòng)態(tài)飛行步長(zhǎng)

原布谷鳥(niǎo)算法中的a0=0.01,以一個(gè)定常數(shù)去限定步長(zhǎng)a的變化范圍,由于算法在搜索前期大步長(zhǎng)可以增強(qiáng)搜尋能力,在搜索后期小步長(zhǎng)可以提高最優(yōu)解的精度,因此考慮在a0中引入余弦函數(shù),使其隨著迭代次數(shù)的增加在區(qū)間[0,1]上動(dòng)態(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飛行步長(zhǎng)公式，即

(4)

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

原始CS算法中的發(fā)現(xiàn)概率恒為0.25,而實(shí)際上不同的布谷鳥(niǎo)的發(fā)現(xiàn)概率應(yīng)有所不同,因此發(fā)現(xiàn)概率用一個(gè)變量去描述更為合理.在算法的搜尋前期,為了增加解的多樣性,將發(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ù)動(dòng)態(tài)遞減因子,初始發(fā)現(xiàn)概率pab=0.4.ICS算法步驟為:

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

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

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

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

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

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

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

表 1 測(cè)試函數(shù)

圖 1 Sphere函數(shù)最優(yōu)值變化趨勢(shì)圖 圖 2 Beale函數(shù)最優(yōu)值變化趨勢(shì)圖 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)值變化趨勢(shì)圖Fig.3 Diagram of the optimal value change of Lévy function

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

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

Sphere函數(shù):測(cè)試函數(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ù):測(cè)試函數(shù)最優(yōu)值位置為(3,0.5).

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

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

Lévy函數(shù):測(cè)試函數(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 測(cè)試函數(shù)最優(yōu)解位置以及兩種算法搜尋結(jié)果對(duì)比

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

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

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

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

3 結(jié)束語(yǔ)

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