一種改進的自適應慣性權重布谷鳥算法

孫敏，韋慧

(安徽理工大學數學與大數據學院，安徽 淮南 232001)

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

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

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

1 布谷鳥搜索算法

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

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

(1)

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

(2)

式(1)描述的隨機游動是一個Markov鏈，即下一代的位置僅取決于當前的位置。為從當前最優解獲取步長信息，采用文獻[7]的步長因子：

(3)

式中：α0是常數，一般取0.01；xbest表示當前最優解。為了便于計算，文獻[12]采用式(4)計算Lévy隨機數：

(4)

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

(5)

(6)

2 改進的布谷鳥算法

2.1 自適應參數pa

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

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

(7)

式中:ti為當前迭代次數；tmax為設置的最大迭代次數；pa max為最大發現概率；pa min為最小發現概率。

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

2.2 自適應Lévy飛行

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

(8)

式中：ti為當前迭代次數；tmax為設置的最大迭代次數。

此時，式(5)修改為：

(9)

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

2.3 動態慣性權重的偏好隨機游動

圖1 ICS-2算法流程圖

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

(10)

式中：fi、fmin和fmax分別為每代種群中第i個個體、最優個體以及最差個體的適應度值。

改進的偏好隨機游動可表示為：

(11)

在算法運行中，如果個體的適應度與最優個體的適應度之間差異較大，則此時慣性權重w較小，從而加強了局部尋優能力。若算法陷入局部最優，則個體的適應度與最優個體的適應度之間差異較小，此時w增大，擴大了搜索空間，使得算法跳出局部極值，提高全局尋優能力。因此，w隨著鳥窩適應度值的變化而動態改變，能夠平衡全局與局部之間的搜索且提高了其跳出局部最優的能力。

2.4 ICS-2算法步驟

改進的自適應慣性權重布谷鳥算法(ICS-2算法)的具體步驟如下：

步3 通過動態發現概率pa淘汰部分鳥窩，并用改進的偏好隨機游動搜索方式式(11)產生與淘汰鳥窩數量相同的新鳥窩。

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

3 測試

為驗證ICS-2算法具有更快的收斂速度和更高的計算精度，以求解4個標準測試函數的最小值為例，同時將CS[3]和ICS-1[11]這2種算法加入對比。

3.1 試驗設計

選取的測試函數包括單峰函數和復雜多峰函數，如表1所示。

表1 測試函數

表2 試驗參數設置

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

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

3.2 試驗結果與分析

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

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

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

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

從表4可以看出，當n=30，對于函數f1，f2，ICS-2算法的搜索精度遠優于CS和ICS-1算法，并且ICS-2算法以最少的迭代次數收斂于目標精度；對于函數f3，ICS-2算法用最短時間收斂至全局最優值，平均運行時間比CS和ICS-1分別減少了近382、301ms，然而此時CS算法無法收斂于全局最優值，ICS-1算法達到目標精度比ICS-2算法多迭代479次左右；對于函數f4，3種算法尋優能力相當，但ICS-2的計算結果仍優于其他2種算法。

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

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

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

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

不同維度下的函數測試結果表明，ICS-2算法在整體性能上優于CS、ICS-1算法，且能較好地解決標準CS算法存在的收斂速度慢、易陷入局部最優等問題，這是因為該算法在其尋優過程中采用自適應步長進行搜索，且在偏好隨機游動中引入了自適應慣性權重策略，提高了算法的搜索能力，平衡了局部搜索和全局搜索，同時，參數pa的自適應使得種群能夠保持多樣性。所以，算法用時較少，收斂精度和速度明顯提高。

4 結語

分析了布谷鳥搜索算法的尋優過程與特性，給出了一種改進的自適應慣性權重布谷鳥算法。該算法通過對發現概率和步長因子自適應調整，并將動態慣性權重引入偏好隨機環節中，由所給的經典測試函數，討論了CS、ICS-1和ICS-2算法的收斂速度快慢和精度高低問題。仿真試驗結果表明，無論是簡單的單峰函數還是復雜的多峰函數，改進的布谷鳥算法具有更好的尋優能力，加快了算法的收斂速度，提高了計算精度，克服了標準CS算法易陷入局部最優等不足，在求解連續函數問題上具備優勢。