葉亞榮，賀興時(shí)，張 超

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

0 引 言

元啟發(fā)式算法[1]自提出以來(lái)越來(lái)越被人們所熟知，其中包括遺傳算法[2](genetic algorithm)、蟻群算法[3](ant colony optimization)、粒子群算法[4](particle swarm optimization)、螢火蟲算法[5](fire fly algorithm)等。諸多研究已經(jīng)證實(shí)了元啟發(fā)式算法在實(shí)際應(yīng)用中的可行性。

布谷鳥搜索算法是由英國(guó)劍橋大學(xué)楊新社和Suash Deb提出的，該算法模擬了布谷鳥尋找鳥窩放置新的鳥蛋行為，并有效結(jié)合了其他鳥類和果蠅的Levy飛行行為。這種算法不僅簡(jiǎn)單易行，參數(shù)較少，而且性能優(yōu)于粒子群和遺傳算法等啟發(fā)式算法[6]。

布谷鳥算法與其他智能算法一樣都存在易陷入局部最優(yōu)且收斂速度慢等缺陷。對(duì)此，王凡等提出了一種基于高斯擾動(dòng)的布谷鳥搜索算法(GCS)[7]，該算法與原有的布谷鳥算法相比能更好地跳出局部最優(yōu)；王李進(jìn)等提出了一種逐維改進(jìn)的布谷鳥搜索算法[8]，但是存在求解全局最優(yōu)解不夠快的問(wèn)題；薛益鴿等提出一種基于動(dòng)態(tài)分組與高斯擾動(dòng)的布谷鳥算法[9]，該算法求解速度快，精度高，但是易陷入局部最優(yōu)。在算法運(yùn)行過(guò)程中，初始化鳥群的質(zhì)量起著至關(guān)重要的作用，好的初始種群能加快種群的收斂速度；宋慶慶等提出基于混沌序列的布谷鳥算法[10]；鄭洪清等提出了一種自適應(yīng)步長(zhǎng)調(diào)整布谷鳥搜索算法[11]；陳華等提出了基于logistic模型的自適應(yīng)布谷鳥算法[12]；李榮雨等提出一種基于梯度的自適應(yīng)快速布谷鳥算法[13]。

受上述算法啟發(fā)，針對(duì)布谷鳥算法的缺陷，文中提出了一種基于隨機(jī)擾動(dòng)的自適應(yīng)布谷鳥算法。

1 CS算法

布谷鳥搜索算法(cuckoo search，SC)是模擬布谷鳥尋找鳥窩放置鳥蛋的行為，并結(jié)合Levy飛行更新鳥窩位置，完成了每代的更新，如果更新后的位置優(yōu)于當(dāng)前位置，則對(duì)鳥窩的位置進(jìn)行更新，否則保留當(dāng)前位置。由于布谷鳥算法簡(jiǎn)單、高效、搜索路徑優(yōu)等優(yōu)點(diǎn)，已在背包優(yōu)化[14]、機(jī)構(gòu)優(yōu)化[15]、工程優(yōu)化[16]等問(wèn)題中成功應(yīng)用。

布谷鳥算法是在三個(gè)理想狀態(tài)下進(jìn)行概述。

規(guī)則1：每個(gè)布谷鳥每次只產(chǎn)一個(gè)蛋，并隨機(jī)選擇鳥窩放置它。

規(guī)則2：最好的鳥窩(解)會(huì)被保留在下一代。

規(guī)則3：可用的巢主鳥窩為n，巢主鳥能夠發(fā)現(xiàn)外來(lái)鳥的概率是pa，其中pa∈[0,1]。在這種情況下，巢主鳥可將該鳥蛋丟棄，或者干脆拋棄這個(gè)鳥窩，在新的位置建立一個(gè)全新的鳥窩。

布谷鳥所選取的孵化鳥蛋的鳥窩，其實(shí)就是尋找搜索過(guò)程中的可行解，實(shí)質(zhì)是當(dāng)產(chǎn)生更好的鳥窩時(shí)，就代替上一代的鳥窩?；诓脊萨B育崽的習(xí)慣，布谷鳥下一代鳥窩的更新用levy飛行[5]進(jìn)行更新，公式如下：

Xi(t+1)=Xi(t)+α⊕L(s,λ)

(1)

其中

1<λ≤3

(2)

其中，α>0為步長(zhǎng)因子，它與問(wèn)題的利害關(guān)系的程度相關(guān)聯(lián)，大多數(shù)情況下取α=ο(L/10)，L為問(wèn)題利害關(guān)系的特征范圍。

2 自適應(yīng)步長(zhǎng)的隨機(jī)擾動(dòng)布谷鳥算法

2.1 自適應(yīng)鳥窩位置更新

為了加快布谷鳥算法的收斂速度，在原始的布谷鳥算法中定義步長(zhǎng)因子：

(3)

其中，ni表示第i代鳥窩的位置；nbest表示此代的最佳狀態(tài)的鳥窩位置；dmax表示最好位置與其他所有鳥窩的距離的最大值。

在式3的基礎(chǔ)上，引入了調(diào)解鳥窩位置的自適應(yīng)調(diào)整步長(zhǎng)策略：

stepsizei=stepmin+(stepmax-stepmin)di

(4)

其中，stepmax和stepmin分別表示步長(zhǎng)的最大值和最小值。

位置更新公式如下：

s=s+α⊕stepsizei⊕ε

(5)

其中，ε是與pt同階的隨機(jī)矩陣；α為常數(shù)，⊕表示點(diǎn)對(duì)點(diǎn)乘法，通過(guò)多次實(shí)驗(yàn)，α取0.05來(lái)控制鳥窩的活動(dòng)范圍。

2.2 隨機(jī)擾動(dòng)

即

(6)

其中，ε是與pt+1同階的隨機(jī)矩陣，⊕表示點(diǎn)對(duì)點(diǎn)乘法。由于ε的隨機(jī)取值范圍較大，容易使鳥窩位置的活動(dòng)范圍偏離過(guò)大，經(jīng)過(guò)多次實(shí)驗(yàn)取a=0.05來(lái)控制ε的搜索范圍。

2.3 改進(jìn)的布谷鳥算法(ASGCS)流程

1.初始化種群：nhost nestXi(i=1,2,…,n);

2.計(jì)算適應(yīng)值：Fi(i=1,2,…,n);

3.While(t<最大迭代次數(shù));

4.通過(guò)Levy flight與自適應(yīng)步長(zhǎng)來(lái)更新鳥窩Xi;

5.計(jì)算更新鳥窩的適應(yīng)值Fi;

6.從n個(gè)鳥窩中隨機(jī)選取一個(gè)鳥窩(記為j);

7.if(Fi

8.用新的解替換j;

9.Else對(duì)新的鳥窩進(jìn)行隨機(jī)擾動(dòng)(記為k)；

10.End if

11.通過(guò)與發(fā)現(xiàn)概率pa進(jìn)行比較，拋棄較差的解;

12.保留結(jié)果最優(yōu)的解;

13.end

3 實(shí)驗(yàn)與結(jié)果分析

在參數(shù)相同的前提下，通過(guò)7個(gè)測(cè)試函數(shù)對(duì)ASGCS與CS算法性能進(jìn)行比較，以MATLAB2016和Window7作為測(cè)試平臺(tái)進(jìn)行實(shí)驗(yàn)。對(duì)于所有的測(cè)試函數(shù)，種群的個(gè)數(shù)設(shè)置為n=8，最大迭代次數(shù)為500，搜索精度為105，擾動(dòng)因子α=0.05。測(cè)試函數(shù)如表1所示。

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

在所有參數(shù)都一致的條件下，由圖1可以看出，在Crownedcross函數(shù)下，原始的布谷鳥算法的初始值小于改進(jìn)以后的ASCS算法的初始值，在后期收斂速度明顯優(yōu)于原始的CS算法，迭代次數(shù)也明顯少于原始的CS算法。圖2、圖3在Matyas、Sphere函數(shù)下，無(wú)論是初始值還是收斂速度以及迭代次數(shù)，改進(jìn)后的ASCS算法都優(yōu)于原始的CS算法。由圖4可以看出，在Multigaussian函數(shù)下雖然進(jìn)化過(guò)程中收斂速度比較緩慢，但是改進(jìn)后的ASCS算法比原始的CS算法能更快收斂。由于篇幅限制，Threehumpcamel、Zakh、Salomon函數(shù)沒(méi)有進(jìn)行展示，但是從收斂速度和迭代次數(shù)方面看，改進(jìn)后的布谷鳥算法更好。故改進(jìn)的ASCS算法性能優(yōu)于原始的CS算法。

圖1 Crownedcross函數(shù)的尋優(yōu)曲線

圖2 Matyas函數(shù)的尋優(yōu)曲線

圖3 Sphere函數(shù)的尋優(yōu)曲線

圖4 Multigaussian函數(shù)的尋優(yōu)曲線

表2統(tǒng)計(jì)了兩種算法在7個(gè)標(biāo)準(zhǔn)的測(cè)試函數(shù)下計(jì)算的平均最優(yōu)值?？梢钥闯?，Crownedcross函數(shù)在ASCS的平均最優(yōu)值比CS算法提高了4個(gè)點(diǎn)，而ASCS的最大值也比原始的CS值大，最小值也優(yōu)于原始的CS算法。對(duì)于Matyas和Sphere函數(shù)的最大值與最小值，ASCS都優(yōu)于原始的CS算法，ASCS算法的平均最優(yōu)值也優(yōu)于原始的CS算法。對(duì)于Salomon函數(shù)，ASCS算法的最大、最小值，平均值都為0，但是優(yōu)于原始的CS算法。Zakh、Threehumpcamel函數(shù)在最大、最小值以及平均最優(yōu)值提高了幾十個(gè)點(diǎn)，雖然Multigaussian函數(shù)在ASCS算法下最優(yōu)值比原始CA算法只提高了0.000 1，但是綜上所述，ASCS在性能上優(yōu)于CS算法。

表2 ASCS與CS的性能比較

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

ASCS算法在Levy尋找鳥窩的過(guò)程中添加自適應(yīng)步長(zhǎng)因子，可以提高原始算法的搜索能力，之后在尋找最優(yōu)鳥窩時(shí)添加了擾動(dòng)因子，兩種思想的結(jié)合充分提高了鳥窩位置的多樣性，很大程度上提高了算法的性能。仿真實(shí)驗(yàn)結(jié)果證明了該算法的可行性。