一種參數(shù)動(dòng)態(tài)更新的布谷鳥(niǎo)搜索算法

閆 河，謝 敏，趙其峰，李曉玲

1(重慶理工大學(xué) 兩江人工智能學(xué)院，重慶 401135)

2(重慶理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，重慶 400054)

E-mail：cqxiemin@gmail.com

1 引 言

在自然界中，布谷鳥(niǎo)[1]會(huì)將卵產(chǎn)在宿主鳥(niǎo)巢里，布谷鳥(niǎo)幼鳥(niǎo)會(huì)本能地模仿宿主幼鳥(niǎo)行為來(lái)降低被宿主鳥(niǎo)發(fā)現(xiàn)的概率[2]，當(dāng)幼鳥(niǎo)被發(fā)現(xiàn)時(shí)，布谷鳥(niǎo)需重新尋找鳥(niǎo)巢產(chǎn)卵.大量實(shí)驗(yàn)表明，布谷鳥(niǎo)尋找宿主鳥(niǎo)巢的飛行行為屬于隨機(jī)游走，飛行步長(zhǎng)滿足Lévy分布[3]，是生物界中常見(jiàn)的動(dòng)物覓食飛行方式[4].布谷鳥(niǎo)搜索(Cuckoo Search，CS)算法就是依據(jù)布谷鳥(niǎo)“寄巢產(chǎn)卵”行為提出的模型[5]，其主要思想是利用Lévy飛行策略產(chǎn)生候選解，并利用貪婪策略更新解，在一定概率下舍棄部分解后，通過(guò)偏好隨機(jī)游走策略產(chǎn)生新解替換淘汰解，通過(guò)不斷迭代最終使得解達(dá)到全局最優(yōu).

CS算法作為一種典型的群智能優(yōu)化算法，具有參數(shù)少，結(jié)構(gòu)簡(jiǎn)單，易于實(shí)現(xiàn)等優(yōu)點(diǎn)[6]，在各領(lǐng)域均得到了廣泛的應(yīng)用[7，8].但是固定的步長(zhǎng)縮放因子使得算法容易陷入局部最優(yōu)[9]，且偏好隨機(jī)游走策略是通過(guò)任意選擇當(dāng)前鳥(niǎo)巢解來(lái)生成新解，具有隨機(jī)性[10]，因此有學(xué)者對(duì)存在的問(wèn)題進(jìn)行了改進(jìn).孫敏等人[11]將混沌擾動(dòng)策略引入CS算法(Chaotic Cuckoo Search Algorithm，CCSA)，通過(guò)Circle映射有效的防止了算法陷入局部最優(yōu)，文獻(xiàn)[12]提出了一種基于貝塔分布的CS算法(Cuckoo Search Algorithm with Beta Distribution，BCS)，采用貝塔分布隨機(jī)數(shù)設(shè)置Lévy飛行步長(zhǎng)，增強(qiáng)了算法收斂速度；文獻(xiàn)[13]針對(duì)高維優(yōu)化存在維間干擾現(xiàn)象，提出了基于逐維改進(jìn)的CS算法(Cuckoo Search Algorithm with Dimension by Dimension Improvement，DDICS)，將各維度最優(yōu)解組合成新解，有效地改善了解的質(zhì)量；文獻(xiàn)[14]利用教與學(xué)搜索策略(Teaching-Learning-Based Optimization，TLBO)提高算法局部搜索能力，采用精英解方法強(qiáng)化優(yōu)勢(shì)信息學(xué)習(xí)，引入模擬退火機(jī)制避免算法陷入局部最優(yōu)，面對(duì)復(fù)雜多目標(biāo)圖像分割具有一定優(yōu)勢(shì)，本文將文獻(xiàn)[14]提出方法暫命名為TLBOCS算法.

雖然改進(jìn)的布谷鳥(niǎo)算法都在不同程度上提升了算法性能，但尋優(yōu)的準(zhǔn)確性依然較低.因此，本文提出了一種參數(shù)動(dòng)態(tài)更新的布谷鳥(niǎo)搜索算法.首先，利用柯西分布隨機(jī)數(shù)生成Lévy飛行步長(zhǎng)，記錄每代最優(yōu)解對(duì)應(yīng)均值參數(shù)，以此生成下一次迭代所需的新的柯西分布[15，16]，這種步長(zhǎng)更新策略能夠充分利用迭代信息，使得局部搜索更加靈活；其次，提出正態(tài)干擾策略生成干擾解，同時(shí)保留每代最優(yōu)解對(duì)應(yīng)的均值參數(shù)，以此生成下一次迭代所需的新的正態(tài)分布[15，17]，完成正態(tài)干擾參數(shù)的更新；再利用模擬退火算法(Simulated Annealing，SA)[18]的Metropolis準(zhǔn)則在新解和干擾解中擇優(yōu)，該方法使得算法具有容差性，在一定概率下保留適應(yīng)度較低的解，避免陷入局部最優(yōu)；最后，利用輪盤賭選擇[19]和雙向隨機(jī)搜索策略強(qiáng)化優(yōu)勢(shì)解的學(xué)習(xí)，生成新解來(lái)替換被淘汰的解.實(shí)驗(yàn)結(jié)果表明，本文提出方法具有較高的準(zhǔn)確性和穩(wěn)定性.

2 基于參數(shù)動(dòng)態(tài)更新的CS算法

2.1 基于柯西分布的Lévy飛行策略

在經(jīng)典CS算法中，步長(zhǎng)縮放因子是固定的，易陷入局部最優(yōu)[10]，步長(zhǎng)大，損害搜索精度，步長(zhǎng)小，降低搜索速度.文獻(xiàn)[12]采用Beta分布設(shè)置步長(zhǎng)縮放因子，雖然提高了算法性能，但容易陷入局部最優(yōu)，且隨著維度增加，算法性能有所下降.針對(duì)該問(wèn)題，本文采用柯西隨機(jī)數(shù)進(jìn)行更新，更新公式如下：

Xg+1=Xg+Cauchy?Levy(β)

(1)

(2)

(3)

Cauchyi=randci(μCauchy，0.1)

(4)

μCauchy=(1-d)·μCauchy+d·meanL(SCauchy)

(5)

(6)

2.2 基于正態(tài)擾動(dòng)和模擬退火的更新策略

為了避免算法陷入局部最優(yōu)，引入SA算法的Metropolis準(zhǔn)則，在一定概率上保留適應(yīng)度較差的解可以有效避免算法陷入局部最優(yōu).Metropolis準(zhǔn)則評(píng)價(jià)的兩組解為2.1節(jié)生成的新解以及采用正態(tài)隨機(jī)數(shù)生成的干擾解.解的評(píng)價(jià)準(zhǔn)則以及干擾解生成方法如下：

exp(F(XNormal)-F(Xg))/Tg)>rand

(7)

XNormal=Normal?Xg

(8)

Normali=randni(μN(yùn)ormal，0.1)

(9)

μN(yùn)ormal=(1-d)·μN(yùn)ormal+d·meanA(SNormal)

(10)

Tg+1=kTg

(11)

其中，式(7)為Metropolis準(zhǔn)則，F(xiàn)(·)為適應(yīng)度函數(shù)，Tg為當(dāng)前退火溫度，設(shè)定初始溫度T0=F(Xpbest)/ln(5)，Xpbest為當(dāng)代最優(yōu)解，rand為(0，1)隨機(jī)數(shù)，XNormal為自適應(yīng)正態(tài)隨機(jī)數(shù)生成的新解，Normali為第i個(gè)正態(tài)隨機(jī)數(shù)，Normal=(Normal1，…，NormalN)，randni(·)為正態(tài)分布，μN(yùn)ormal為正態(tài)分布均值，meanA為標(biāo)準(zhǔn)的算術(shù)均值，k為降溫衰減系數(shù)，SNormal與SCauchy一樣，均為成功參數(shù)集合.正態(tài)隨機(jī)數(shù)的生成方式與2.1節(jié)柯西隨機(jī)數(shù)生成方式相似，利用每代最優(yōu)解對(duì)應(yīng)的正態(tài)分布均值生成新的正態(tài)分布，并以此生成下一代新解所需參數(shù).

2.3 基于輪盤賭和雙向隨機(jī)搜索策略

自然界中，當(dāng)卵被宿主發(fā)現(xiàn)時(shí)，布谷鳥(niǎo)需要重新尋找鳥(niǎo)巢產(chǎn)卵，而尋找新巢的方式是隨機(jī)的.基本CS算法中，是根據(jù)偏好隨機(jī)游走策略生成新解來(lái)替換被淘汰的解，這種策略采用雙隨機(jī)解來(lái)更新隨機(jī)游走步長(zhǎng)，沒(méi)有充分利用優(yōu)勢(shì)解的信息，且隨機(jī)游走搜索方向由(0，1)區(qū)間的隨機(jī)數(shù)決定，這種單向搜索在一定程度上限制了搜索的隨機(jī)性[13].輪盤賭方法是遺傳算法中使用最多的選擇策略之一，其基本思想是每個(gè)解被選中的概率與其適應(yīng)度大小成正比，本文利用輪盤賭選擇適應(yīng)度較好的優(yōu)勢(shì)解替代隨機(jī)解，并增加解的反向搜索能力，在保證算法朝著全局最優(yōu)解迭代的同時(shí)，也保留了解的多樣性.偏好隨機(jī)游走公式如下：

Xg+1=Xg+φ?Heaviside(Pa-ε)?(Xi-Xp)

(12)

其中，Heaviside()為單位階躍函數(shù)，φ為(-1，1)區(qū)間內(nèi)的隨機(jī)方向系數(shù)，使得算法具有雙向搜索能力[13]，Pa為解被淘汰的概率，ε為(0，1)區(qū)間內(nèi)的隨機(jī)數(shù)，Xi為當(dāng)代隨機(jī)解，Xp為輪盤賭選出的解.

2.4 改進(jìn)算法的流程

算法流程抽象如下.其中，逐維更新解策略采用的是文獻(xiàn)[13]的方法，pbestFit為當(dāng)前迭代最優(yōu)適應(yīng)度，Xpbest為每次迭代的最優(yōu)解集，gbestFit為全局最優(yōu)適應(yīng)度，Xgbest為全局最優(yōu)解，Xa，i為L(zhǎng)évy飛行生成的第i個(gè)新解，Xnew，i為需進(jìn)行逐維比較的第i個(gè)解，Xnew，(i，j)為Xnew，i的第j維解，Xa，(i，j)為Xa，i的第j維數(shù)據(jù)，Xnew，i其他維度的解為第g代對(duì)應(yīng)維度解，Xg，i為第g代的解集第i個(gè)解，Xpbest，i為第g代最優(yōu)解集的第i個(gè)解.

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

begin

初始化種群大小N和解：Xi，(i=1，2，…，N)；

計(jì)算解的適應(yīng)度F(Xi)，保留最優(yōu)適應(yīng)度pbestFit，對(duì)應(yīng)解Xpbest；

設(shè)置初始溫度T0；

設(shè)置柯西分布μCauchy與正態(tài)分布μN(yùn)ormal的初始均值；

while(未達(dá)到最大迭代數(shù))

fori=1 to N

生成柯西隨機(jī)數(shù)Cauchyi；

利用公式(1)-公式(6)生成新解Xa，i；

Xnew，i=Xg；

// 逐維更新解

forj=1 toD

Xnew，(i，j)=Xa，(i，j)；

ifF(Xnew，(i，j))>F(Xg)//適應(yīng)度比較

Xg=Xnew，(i，j)；//單維度更新

end

//當(dāng)前解優(yōu)于全局解，跳出逐維更新循環(huán)

ifF(Xnew，(i，j))>F(Xgbest)

break；

end

end

end

更新當(dāng)代解的適應(yīng)度F(Xg)；

fori=1 to N

生成正態(tài)分布隨機(jī)數(shù)Normali；

利用公式(8)生成干擾解XNormal，i；

end

根據(jù)Metropolis準(zhǔn)則在新解和干擾解中擇優(yōu)；

退溫操作，Tg+1=kTg；

fori=1 toN

ifr>Pa

利用輪盤賭選出Xp，按照式(12)生成新解代替Xg，i；

end

end

//更新當(dāng)代最優(yōu)解，并記錄對(duì)應(yīng)參數(shù)

fori=1 toN

ifF(Xg，i)>F(Xpbest，i)

Xpbest，i=Xg，i；

pbestFit_i=F(Xg，i)；

記錄SCauchy和SNormal；

end

end

利用公式(5)和公式(10)更新μCauchy和μN(yùn)ormal；

保留全局最優(yōu)解Xgbest以及適應(yīng)度gbestFit；

end

輸出全局最優(yōu)解；end

3 改進(jìn)算法性能測(cè)試實(shí)驗(yàn)與分析

3.1 基本測(cè)試函數(shù)實(shí)驗(yàn)與分析

為了測(cè)試改進(jìn)算法性能，選取了6個(gè)優(yōu)化算法常用的測(cè)試函數(shù)進(jìn)行試驗(yàn)[20，21]，如表1所示，6個(gè)測(cè)試函數(shù)最優(yōu)值均為0.表2為各算法參數(shù)配置.

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

表2 各算法參數(shù)Table 2 Parameters of each algorithm

表3為本文改進(jìn)算法與粒子群算法(Particle Swarm Optimization，PSO)[22]、遺傳算法(Genetic Algorithm，GA)[23]、經(jīng)典CS算法、BCS、DDICS等7個(gè)算法在6個(gè)基本測(cè)試函數(shù)上的運(yùn)行結(jié)果，圖1為對(duì)應(yīng)適應(yīng)度曲線圖.算法各執(zhí)行20次，單個(gè)迭代次數(shù)為500，由于篇幅限制，表3只顯示種群維度為6時(shí)各算法的平均適應(yīng)度值，圖1也是6維的適應(yīng)度曲線圖.

從表3可以看出，本文算法能夠較穩(wěn)定的迭代到最優(yōu)解，算法穩(wěn)定的原因主要有：

表3 各算法平均適應(yīng)度Table 3 Average fitness of each algorithm

1)Lévy飛行步長(zhǎng)的更新以及逐維求解策略，使得算法搜索在不受維間干擾的同時(shí)，能夠始終向著全局最優(yōu)解迭代；

2)利用正態(tài)隨機(jī)數(shù)生成干擾解，加上模擬退火機(jī)制使得算法具有容差能力，保證解的豐富性，避免陷入局部最優(yōu)；

3)充分利用優(yōu)勢(shì)解信息，通過(guò)輪盤賭方法選擇適應(yīng)度較優(yōu)的解來(lái)輔助生成新解，完成替換.

從圖1可以看出，本文提出算法能夠較快的收斂到全局最優(yōu)，雖然在圖1(b)中比TLBOCS和CCSA算法效果差一點(diǎn)，但是從其他圖來(lái)看，TLBOCS算法具有一定的不穩(wěn)定性，而CCSA算法在其他基本函數(shù)上的結(jié)果比本文算法差了一點(diǎn).使用柯西隨機(jī)數(shù)更新Lévy飛行步長(zhǎng)，收集每代最優(yōu)解的柯西分布均值，利用這些參數(shù)構(gòu)建新的柯西概率分布，使得步長(zhǎng)能夠根據(jù)迭代情況更新，這也是本文算法能夠穩(wěn)定迭代到全局最優(yōu)解的關(guān)鍵.

圖1 測(cè)試函數(shù)的適應(yīng)度曲線Fig.1 Fitness curves of test functions

3.2 多閾值圖像分割實(shí)驗(yàn)與分析

為驗(yàn)證本文算法優(yōu)化能力，采用文獻(xiàn)[24]的多閾值Otsu分割函數(shù)作為適應(yīng)度函數(shù)，并選擇一張經(jīng)典的Lena圖像以及伯克利大學(xué)圖像分割庫(kù)中的一張圖像進(jìn)行試驗(yàn).試驗(yàn)環(huán)境為Ubuntu 18.04系統(tǒng)，3.6GHz和32GB內(nèi)存微處理器，運(yùn)行軟件為MatlabR2018a.

本文除了與上節(jié)7個(gè)算法進(jìn)行對(duì)比，還增加了去除2.1-2.3節(jié)改進(jìn)方法的3組對(duì)比實(shí)驗(yàn)，分別命名為Ours1，Ours2和Ours3.

圖2和圖3為算法各執(zhí)行20次得到的結(jié)果，從圖2可以看出，本文改進(jìn)方法分割效果優(yōu)于大部分對(duì)比算法，在一些細(xì)節(jié)上和原圖更為接近，說(shuō)明本文提出的方法能夠較好的分割圖像，圖2(i)～圖2(k)對(duì)比CS等算法也體現(xiàn)出了優(yōu)勢(shì)，但是在背景細(xì)節(jié)上處理得比圖2(l)差一點(diǎn)，說(shuō)明本文提出的3個(gè)改進(jìn)點(diǎn)對(duì)于算法性能均有提升.圖3(a)是目標(biāo)更為復(fù)雜的伯克利圖像，在處理衣服和褲子這種顏色比較接近的目標(biāo)時(shí)，其他算法如CA等將這兩部分視為同一目標(biāo)進(jìn)行分割，而本算法依然能夠較為完整的分割，說(shuō)明本文提出算法更加高效，能夠成功分割不同圖像.

圖2 Lena的閾值分割結(jié)果圖Fig.2 Lena figure of threshold segmentation

圖3 伯克利圖像的閾值分割結(jié)果圖Fig.3 Berkeley figure of threshold segmentation

圖4和圖5為各算法執(zhí)行1次得到的適應(yīng)度進(jìn)化曲線，從兩圖中可以看出，本文能夠較快的完成收斂，自適應(yīng)步長(zhǎng)使得算法局部搜索能力更加靈活；正態(tài)擾動(dòng)和模擬退火避免了算法陷入局部最優(yōu)，而經(jīng)典CS算法在早期迭代時(shí)就陷入了局部最優(yōu).去除改進(jìn)步驟的3個(gè)結(jié)果也優(yōu)于部分對(duì)比實(shí)驗(yàn)，驗(yàn)證了算法改進(jìn)的有效性.

圖4 Lena的分割結(jié)果適應(yīng)度曲線Fig.4 Fitness curves of Lena′s segmentation images

圖5 伯克利圖像分割結(jié)果適應(yīng)度曲線Fig.5 Fitness curves of Berkeley′s segmentation images

為了更直觀的評(píng)價(jià)圖像分割效果，本文選用峰值信噪比(Peak Signal to Noise Ratio，PSNR)[9]和結(jié)構(gòu)相似性(Structural Similarity，SSIM)[9]來(lái)進(jìn)行量化評(píng)價(jià).峰值信噪比計(jì)算公式如下：

PSNR=10log(255/MSE)

(13)

(14)

結(jié)構(gòu)相似性計(jì)算公式如下：

(15)

表4為各算法分割結(jié)果性能指標(biāo)，可以看出，本文算法在低維時(shí)和其他布谷鳥(niǎo)類算法幾乎沒(méi)有差距，隨著維度的增加，PSNR和SSIM的差距也越明顯，DDICS在5維的時(shí)候雖然比較高，但是在6維的時(shí)候算法性能降低.非布谷鳥(niǎo)類算法在低維空間處理時(shí)具有一定的優(yōu)越性，但是部分算法在高維空間具有不穩(wěn)定性，如PSO算法在6維空間時(shí)PSNR與SSIM均有明顯的下降.本文算法對(duì)比GA算法部分效果雖然要差一點(diǎn)，但是GA算法在5維空間上處理時(shí)，PSNR有所下降，SSIM算法在6維空間處理時(shí)也比不如5維空間的結(jié)果，而本文算法效果在維度上升的同時(shí)，保持了本身的穩(wěn)定性，逐步優(yōu)化，驗(yàn)證了本文算法的有效性.本文改進(jìn)算法在去除部分步驟后的性能有所下降，體現(xiàn)了改進(jìn)部分的重要性.

表4 各算法性能指標(biāo)Table 4 Performance indexes of each algorithm

續(xù)表

4 結(jié) 論

為提升布谷鳥(niǎo)算法在高維空間的搜索能力與穩(wěn)定性，提出了一種參數(shù)動(dòng)態(tài)更新的布谷鳥(niǎo)搜索算法，隨著維度的增加，算法性能能夠穩(wěn)步提升.該算法提出的步長(zhǎng)更新策略能夠充分利用迭代信息，使得局部搜索更加靈活，正態(tài)隨機(jī)干擾保證了解的多樣性，Metropolis準(zhǔn)則使得算法具有容差性，避免算法陷入局部最優(yōu)，輪盤賭選擇和雙向隨機(jī)搜索方法充分利用優(yōu)勢(shì)解信息完成新舊解的替換.通過(guò)與PSO、CS、DDICS等算法進(jìn)行對(duì)比，發(fā)現(xiàn)本文算法搜索能力和穩(wěn)定性的結(jié)果更好.雖然改進(jìn)算法擁有較高的準(zhǔn)確性，但是因在原有算法基礎(chǔ)上增加了模擬退火機(jī)制，使得算法增加了擇優(yōu)判斷步驟，時(shí)間復(fù)雜度隨之提高，未來(lái)將繼續(xù)深入研究各種啟發(fā)式算法，使得改進(jìn)算法能夠在保證分割準(zhǔn)確的同時(shí)，保證分割效率.