一種改進(jìn)的自適應(yīng)慣性權(quán)重布谷鳥算法

孫敏，韋慧

(安徽理工大學(xué)數(shù)學(xué)與大數(shù)據(jù)學(xué)院，安徽 淮南 232001)

20世紀(jì)后期，各種啟發(fā)式算法已經(jīng)成為智能計(jì)算領(lǐng)域的研究熱點(diǎn)，如蟻群算法[1]、粒子群算法[2]等。近幾年來(lái)，一些更高效的新型啟發(fā)式算法不斷脫穎而出，如在2009年，劍橋大學(xué)的Yang和Deb模擬布谷鳥尋窩產(chǎn)卵行為，提出了布谷鳥搜索算法(CS算法)[3]。CS算法具有參數(shù)少、魯棒性強(qiáng)、高效易于實(shí)現(xiàn)以及隨機(jī)搜索路徑優(yōu)等特點(diǎn)，已成功解決了許多實(shí)際難題，如商業(yè)優(yōu)化問題[4]、銑削操作優(yōu)化問題[5]等。

雖然CS算法有很多優(yōu)點(diǎn)，但仍存在搜索速度較慢、易陷入局部最優(yōu)、缺少活力等缺點(diǎn)。目前通過(guò)改進(jìn)算法參數(shù)、調(diào)整算法結(jié)構(gòu)提高算法性能是一個(gè)重要的研究方向。國(guó)內(nèi)外眾多學(xué)者對(duì)此進(jìn)行研究，并給出了一些改進(jìn)方法：文獻(xiàn)[6]建議采用隨迭代次數(shù)遞減的步長(zhǎng)因子來(lái)提高算法的收斂速度,但未改進(jìn)偏好隨機(jī)游動(dòng)部分，算法的局部能力提升不足；文獻(xiàn)[7]引入貪婪機(jī)制提高算法的計(jì)算精度，但是會(huì)增加計(jì)算時(shí)間；文獻(xiàn)[8]將粒子群算法思想用于CS算法的位置更新過(guò)程，提出基于粒子群算法的布谷鳥搜索算法，進(jìn)一步改善了算法的自適應(yīng)性，然而對(duì)于高維問題該算法沒有明顯的優(yōu)勢(shì)；文獻(xiàn)[9]利用布谷鳥的鳥窩位置和最優(yōu)鳥窩位置之間的距離進(jìn)行自適應(yīng)調(diào)整，提出了一種基于自適應(yīng)步長(zhǎng)的布谷鳥算法，提高了算法的收斂速度，但計(jì)算精度沒有明顯增加。

由于布谷鳥算法完全依賴于Lévy飛行和偏好隨機(jī)游走，二者平衡了算法的全局搜索和局部搜索[10]，而Lévy飛行主要受到步長(zhǎng)參數(shù)的影響，偏好隨機(jī)游動(dòng)主要受發(fā)現(xiàn)概率參數(shù)的影響，因此對(duì)這2個(gè)參數(shù)進(jìn)行合理調(diào)整，是提高CS算法計(jì)算效率的主要研究方向。Valian等[11]引入自適應(yīng)步長(zhǎng)和自適應(yīng)發(fā)現(xiàn)概率，提出一種改進(jìn)的CS算法(improved CS，記作ICS-1)。ICS-1算法的計(jì)算效率和精度優(yōu)于基本的CS算法?；贑S算法的尋優(yōu)過(guò)程，筆者給出了一種改進(jìn)的自適應(yīng)慣性權(quán)重布谷鳥搜索算法(ICS-2)：通過(guò)在尋優(yōu)過(guò)程中自適應(yīng)地改變發(fā)現(xiàn)概率和步長(zhǎng)因子，以及在偏好隨機(jī)游動(dòng)機(jī)制中加入一種根據(jù)種群最優(yōu)適應(yīng)度值、最差適應(yīng)度值以及個(gè)體適應(yīng)度值自適應(yīng)調(diào)整慣性權(quán)重，實(shí)現(xiàn)對(duì)算法的整體動(dòng)態(tài)調(diào)整。

1 布谷鳥搜索算法

自然界中，布谷鳥繁衍后代的方式是將自己的卵悄悄的產(chǎn)入宿主鳥窩并由宿主鳥孵化。一旦宿主鳥發(fā)現(xiàn)自己的鳥窩有外來(lái)卵，就會(huì)將外來(lái)卵丟棄或者遺棄該鳥窩，并另筑新巢。為了模擬布谷鳥尋窩，Yang和Deb假定了以下3個(gè)理想規(guī)則[3]：①布谷鳥1次只產(chǎn)1個(gè)卵，并隨機(jī)選擇鳥窩孵化；②最好的鳥窩(解)將被保留到下一代；③可利用的鳥窩數(shù)量N是固定的,宿主鳥能發(fā)現(xiàn)外來(lái)卵的概率pa∈[0,1]，在這種情況下，宿主鳥可將該卵丟棄或放棄這個(gè)鳥窩，另尋地方重新建1個(gè)新鳥窩。

在以上3個(gè)規(guī)則的基礎(chǔ)上，布谷鳥按Lévy飛行方式搜索鳥窩的路徑和位置更新公式如下:

(1)

Lévy(λ)～μ=t-λ(1<λ≤3)

(2)

式(1)描述的隨機(jī)游動(dòng)是一個(gè)Markov鏈，即下一代的位置僅取決于當(dāng)前的位置。為從當(dāng)前最優(yōu)解獲取步長(zhǎng)信息，采用文獻(xiàn)[7]的步長(zhǎng)因子：

(3)

式中：α0是常數(shù)，一般取0.01；xbest表示當(dāng)前最優(yōu)解。為了便于計(jì)算，文獻(xiàn)[12]采用式(4)計(jì)算Lévy隨機(jī)數(shù)：

(4)

結(jié)合公式(1)～(4)，在Lévy飛行過(guò)程中CS算法采用式(5)生成新的解：

(5)

(6)

2 改進(jìn)的布谷鳥算法

2.1 自適應(yīng)參數(shù)pa

CS算法中，自適應(yīng)參數(shù)pa控制了全局隨機(jī)搜索和局部精細(xì)搜索之間的平衡，當(dāng)pa值越小，被更新的鳥窩數(shù)目越多，全局搜索的多樣性越強(qiáng)；反之，pa越大，越有利于提高局部搜索的能力[13]。將pa取為固定值0.25不利于全局與局部搜索之間的平衡，因此，筆者提出使pa隨算法進(jìn)程動(dòng)態(tài)變化的自適應(yīng)策略：

pa=pa max-(pa max-pa min)exp(-η(ti/tmax)θ)

(7)

式中:ti為當(dāng)前迭代次數(shù)；tmax為設(shè)置的最大迭代次數(shù)；pa max為最大發(fā)現(xiàn)概率；pa min為最小發(fā)現(xiàn)概率。

式(7)實(shí)現(xiàn)了pa隨算法進(jìn)程ti/tmax的增加而由小到大動(dòng)態(tài)變化的自適應(yīng)策略，使得改進(jìn)后的算法能夠在全局和局部搜索之間保持好的平衡，具體來(lái)說(shuō)，ICS-2算法通過(guò)pa的自適應(yīng)動(dòng)態(tài)變化，在算法前期能夠保持很強(qiáng)的全局搜索能力，同時(shí)兼顧局部搜索，而在后期，局部搜索逐漸增強(qiáng)，同時(shí)也兼顧全局搜索，從整體上提高了算法的收斂速度和精度，避免陷入局部最優(yōu)。

2.2 自適應(yīng)Lévy飛行

Lévy飛行機(jī)制中，步長(zhǎng)因子α0的選取影響著布谷鳥算法的尋優(yōu)特性，在尋優(yōu)過(guò)程中，步長(zhǎng)因子越大，全局搜索能力越強(qiáng)，但降低了算法的尋優(yōu)精度，相反，步長(zhǎng)因子越小，搜索速度變得越慢，提高了尋優(yōu)精度[14]。CS算法中將步長(zhǎng)因子固定，顯然不是最好的解決方法，使得尋優(yōu)過(guò)程缺乏自適應(yīng)性，進(jìn)而降低了算法的收斂速度和精度。為此，筆者提出了一種步長(zhǎng)的自適應(yīng)策略：

(8)

式中：ti為當(dāng)前迭代次數(shù)；tmax為設(shè)置的最大迭代次數(shù)。

此時(shí)，式(5)修改為：

(9)

由式(8)可知，步長(zhǎng)因子α0按照非線性遞減的方式，在尋優(yōu)前期，加快了收斂速度，同時(shí)較大的步長(zhǎng)擴(kuò)大了搜索范圍，有利于搜索全局最優(yōu)。隨著算法進(jìn)程的增加，較小的步長(zhǎng)提高了尋優(yōu)精度。

2.3 動(dòng)態(tài)慣性權(quán)重的偏好隨機(jī)游動(dòng)

圖1 ICS-2算法流程圖

在基本CS算法的偏好隨機(jī)環(huán)節(jié)中，鳥巢位置更新是采用固定上一代位置為參考的更新方式，容易造成算法在迭代后期陷入局部最優(yōu)值。動(dòng)態(tài)慣性改進(jìn)策略[15]是一種能夠合理的控制算法全局探索能力和局部開發(fā)能力的機(jī)制，有效提高算法的搜索能力。Nickabadi等[16]對(duì)基于常數(shù)、線性遞減、非線性遞減和自適應(yīng),4種動(dòng)態(tài)慣性權(quán)重作了總結(jié)并比較，筆者在偏好隨機(jī)游動(dòng)過(guò)程中引入一種由鳥巢位置適應(yīng)度值變化決定的動(dòng)態(tài)慣性權(quán)重，動(dòng)態(tài)慣性權(quán)重w為：

(10)

式中：fi、fmin和fmax分別為每代種群中第i個(gè)個(gè)體、最優(yōu)個(gè)體以及最差個(gè)體的適應(yīng)度值。

改進(jìn)的偏好隨機(jī)游動(dòng)可表示為：

(11)

在算法運(yùn)行中，如果個(gè)體的適應(yīng)度與最優(yōu)個(gè)體的適應(yīng)度之間差異較大，則此時(shí)慣性權(quán)重w較小，從而加強(qiáng)了局部尋優(yōu)能力。若算法陷入局部最優(yōu)，則個(gè)體的適應(yīng)度與最優(yōu)個(gè)體的適應(yīng)度之間差異較小，此時(shí)w增大，擴(kuò)大了搜索空間，使得算法跳出局部極值，提高全局尋優(yōu)能力。因此，w隨著鳥窩適應(yīng)度值的變化而動(dòng)態(tài)改變，能夠平衡全局與局部之間的搜索且提高了其跳出局部最優(yōu)的能力。

2.4 ICS-2算法步驟

改進(jìn)的自適應(yīng)慣性權(quán)重布谷鳥算法(ICS-2算法)的具體步驟如下：

步3 通過(guò)動(dòng)態(tài)發(fā)現(xiàn)概率pa淘汰部分鳥窩，并用改進(jìn)的偏好隨機(jī)游動(dòng)搜索方式式(11)產(chǎn)生與淘汰鳥窩數(shù)量相同的新鳥窩。

ICS-2算法的流程圖如圖1所示。

3 測(cè)試

為驗(yàn)證ICS-2算法具有更快的收斂速度和更高的計(jì)算精度，以求解4個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)的最小值為例，同時(shí)將CS[3]和ICS-1[11]這2種算法加入對(duì)比。

3.1 試驗(yàn)設(shè)計(jì)

選取的測(cè)試函數(shù)包括單峰函數(shù)和復(fù)雜多峰函數(shù)，如表1所示。

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

表2 試驗(yàn)參數(shù)設(shè)置

試驗(yàn)中算法參數(shù)選取如表2所示：對(duì)于CS算法，采用文獻(xiàn)[3]的參數(shù)；對(duì)于ICS-1算法，取文獻(xiàn)[11]中的參數(shù)；并且η=8，θ=0.3。

ICS-1算法針對(duì)Lévy飛行步長(zhǎng)及參數(shù)pa進(jìn)行自適應(yīng)改進(jìn)，具有代表性，與ICS-2算法在不同維度的情況下進(jìn)行對(duì)比。試驗(yàn)中，各算法獨(dú)立運(yùn)行30次，3種算法終止條件為滿足最大迭代次數(shù)1000次或精度達(dá)到10-10。獲取統(tǒng)計(jì)數(shù)據(jù)與相應(yīng)仿真曲線，以便進(jìn)行比較。

3.2 試驗(yàn)結(jié)果與分析

表3～表5分別給出了3種算法對(duì)測(cè)試函數(shù)f1～f4在維數(shù)n=10、30、50下的最優(yōu)值、最差值、平均值、平均運(yùn)行時(shí)間及算法達(dá)到精度時(shí)所需的平均迭代次數(shù)，表中，“-”表示最大迭代次數(shù)達(dá)到1000次時(shí)，沒有收斂于所設(shè)置的精度。

表3 10維情況下各算法的性能比較

從表3可以看出，當(dāng)n=10時(shí)，對(duì)測(cè)試函數(shù)f1和f2，3種算法都能達(dá)到所要求的精度，但I(xiàn)CS-2算法明顯具有較快的收斂速度(平均迭代次數(shù)和運(yùn)行時(shí)間)；對(duì)于復(fù)雜的多峰函數(shù)f3，ICS-2算法的優(yōu)勢(shì)更加明顯，最優(yōu)值比CS和ICS-1分別高出了13、12個(gè)數(shù)量級(jí)，運(yùn)行時(shí)間分別減少了近77、33ms，并且ICS-2算法只需511次左右就可以達(dá)到目標(biāo)精度，而CS和ICS-1至少需要1000次，因此ICS-2算法計(jì)算精度較高同時(shí)擁有更快的收斂速度；對(duì)于復(fù)雜的多峰函數(shù)f4，ICS-2比CS和ICS-1的最優(yōu)值分別提高了7個(gè)和4個(gè)數(shù)量級(jí)，雖然在平均值和運(yùn)行時(shí)間上優(yōu)勢(shì)不大，但I(xiàn)CS-2算法迭代856次左右就可以達(dá)到目標(biāo)精度，而CS和ICS-1至少需要1000次。

表4 30維情況下各算法的性能比較

從表4可以看出，當(dāng)n=30，對(duì)于函數(shù)f1，f2，ICS-2算法的搜索精度遠(yuǎn)優(yōu)于CS和ICS-1算法，并且ICS-2算法以最少的迭代次數(shù)收斂于目標(biāo)精度；對(duì)于函數(shù)f3，ICS-2算法用最短時(shí)間收斂至全局最優(yōu)值，平均運(yùn)行時(shí)間比CS和ICS-1分別減少了近382、301ms，然而此時(shí)CS算法無(wú)法收斂于全局最優(yōu)值，ICS-1算法達(dá)到目標(biāo)精度比ICS-2算法多迭代479次左右；對(duì)于函數(shù)f4，3種算法尋優(yōu)能力相當(dāng)，但I(xiàn)CS-2的計(jì)算結(jié)果仍優(yōu)于其他2種算法。

從表5可以看出，當(dāng)n=50，對(duì)于函數(shù)f1，在CS算法無(wú)法收斂于全局最優(yōu)值的情況下，ICS-2算法以最少的運(yùn)行時(shí)間收斂于全局最優(yōu)值，并且只需迭代224次左右就可以達(dá)到目標(biāo)精度；ICS-1雖然可以收斂于全局最優(yōu)值，但是耗費(fèi)的時(shí)間較多，達(dá)到所設(shè)置的目標(biāo)精度至少迭代1000次，相比之下，ICS-2算法的計(jì)算精度較高，具有較快的收斂速度；對(duì)于函數(shù)f2，3種算法都可以收斂于全局最優(yōu)值，ICS-2算法仍然比CS和ICS-1算法有更快的計(jì)算效率(平均運(yùn)行時(shí)間和迭代次數(shù))；對(duì)于函數(shù)f3，ICS-2的最優(yōu)值、最差值和平均值都達(dá)到理論最優(yōu)，平均運(yùn)行時(shí)間比CS和ICS-1分別減少了520、462ms，且ICS-2算法只需要346次就可以達(dá)到目標(biāo)精度，其他2種算法至少需要1000次，因此，對(duì)于函數(shù)f3在高維情況下，ICS-2算法的收斂速度和計(jì)算精度的優(yōu)勢(shì)更加明顯；對(duì)于函數(shù)f4，雖然3種算法都沒有達(dá)到所需求的精度，ICS-2算法明顯具有較快的收斂速度(平均運(yùn)行時(shí)間)。

表5 50維情況下各算法的性能比較

圖2 f1，f2，f3，f4收斂曲線

圖2給出了3種算法在維數(shù)n=30下的4個(gè)測(cè)試函數(shù)收斂曲線。從圖2(a)可以看出，對(duì)于函數(shù)f1，ICS-2算法尋優(yōu)時(shí)最小適應(yīng)度值的下降速度明顯最快，ICS-1次之，CS最慢；當(dāng)?shù)螖?shù)達(dá)到1000次時(shí)，ICS-2的精度明顯比CS和ICS-1算法高，尋優(yōu)精度的優(yōu)勢(shì)較為明顯。從圖2(b)可以看出，對(duì)于函數(shù)f2，由于該函數(shù)的全局最優(yōu)點(diǎn)位于一個(gè)平滑、狹長(zhǎng)的拋物線形山谷內(nèi)，計(jì)算復(fù)雜度隨問題維度增加而增大，CS和ICS-1算法無(wú)法找到有效的搜索方向，皆陷入局部最優(yōu)位置；ICS-2算法雖然在前期收斂速度優(yōu)勢(shì)并不明顯，但當(dāng)?shù)?00次后，ICS-2算法最小適應(yīng)度值下降的速度明顯加快，克服局部極值能力更強(qiáng)，在收斂性能上更優(yōu)，改進(jìn)的效果較為明顯。從圖2(c)可以看出，對(duì)于函數(shù)f3，尋優(yōu)前期，ICS-1的適應(yīng)度值下降速度和CS相比優(yōu)勢(shì)不大，然而迭代400次之后，適應(yīng)度值下降速度明顯比CS快；而整個(gè)尋優(yōu)過(guò)程中，ICS-2最小適應(yīng)度值的下降速度一直明顯最快。從圖2(d)可以看出，對(duì)于函數(shù)f4，由于該函數(shù)本身具有強(qiáng)烈震蕩性，不易求得全局最優(yōu)解，ICS-1的尋優(yōu)曲線差于標(biāo)準(zhǔn)的CS算法；ICS-2尋優(yōu)精度雖然不高，但仍高于其他2種算法，且當(dāng)?shù)?00次之后，ICS-2算法的適應(yīng)度值下降速度明顯比CS、ICS-1快。

不同維度下的函數(shù)測(cè)試結(jié)果表明，ICS-2算法在整體性能上優(yōu)于CS、ICS-1算法，且能較好地解決標(biāo)準(zhǔn)CS算法存在的收斂速度慢、易陷入局部最優(yōu)等問題，這是因?yàn)樵撍惴ㄔ谄鋵?yōu)過(guò)程中采用自適應(yīng)步長(zhǎng)進(jìn)行搜索，且在偏好隨機(jī)游動(dòng)中引入了自適應(yīng)慣性權(quán)重策略，提高了算法的搜索能力，平衡了局部搜索和全局搜索，同時(shí)，參數(shù)pa的自適應(yīng)使得種群能夠保持多樣性。所以，算法用時(shí)較少，收斂精度和速度明顯提高。

4 結(jié)語(yǔ)

分析了布谷鳥搜索算法的尋優(yōu)過(guò)程與特性，給出了一種改進(jìn)的自適應(yīng)慣性權(quán)重布谷鳥算法。該算法通過(guò)對(duì)發(fā)現(xiàn)概率和步長(zhǎng)因子自適應(yīng)調(diào)整，并將動(dòng)態(tài)慣性權(quán)重引入偏好隨機(jī)環(huán)節(jié)中，由所給的經(jīng)典測(cè)試函數(shù)，討論了CS、ICS-1和ICS-2算法的收斂速度快慢和精度高低問題。仿真試驗(yàn)結(jié)果表明，無(wú)論是簡(jiǎn)單的單峰函數(shù)還是復(fù)雜的多峰函數(shù)，改進(jìn)的布谷鳥算法具有更好的尋優(yōu)能力，加快了算法的收斂速度，提高了計(jì)算精度，克服了標(biāo)準(zhǔn)CS算法易陷入局部最優(yōu)等不足，在求解連續(xù)函數(shù)問題上具備優(yōu)勢(shì)。