交互式學習的布谷鳥搜索算法

張海南，游曉明，劉 升，劉中強

1.上海工程技術大學 電子電氣學院，上海201620

2.上海工程技術大學 管理學院，上海201620

1 引言

布谷鳥搜索算法（Cuckoo Search Algorithm，CSA）作為一種較新的生物啟發式算法，由劍橋大學學者Yang 和Deb 于2009 年提出，該算法基于對布谷鳥尋窩寄生幼卵行為的模擬，具有高度創新性[1]。相對于典型的智能優化算法，如粒子群優化算法[2]（PSO）、蟻群優化算法[3]（ACO）、螢火蟲算法[4]、遺傳算法[5]以及雞群算法[6]，CS算法結構簡單、易于實現，設定參數少于PSO和ACO等智能算法，并且容易與其他算法相結合，進而獲得性能更加優越的混合算法。除CS 算法外，由于蟻群優化算法具有天然的并行性和較強的魯棒性，常被用于解決旅行商問題（TSP）、二次分配問題、機器人路徑規劃[7]、網絡路由選擇問題[8]等組合優化問題。

CS 算法引入了自然界鳥類、果蠅飛行軌跡的萊維飛行機制，能夠快速有效地尋找到連續優化問題的最優解，全局搜索能力較強。且關鍵參數僅為外來鳥蛋被發現的概率和種群數目，參數設置簡單。目前，CS算法已被用于多種工程優化問題[9]，具有潛在的研究價值。雖然CS算法控制參數少，結構簡單易于實現，但該算法同其他生物啟發式算法一樣，也存在后期收斂速度慢，易陷入局部最優問題，故針對這些問題，國內外眾多學者展開研究，提出一些改進算法。秦嶺等[10]提出一種具有記憶性的自適應布谷鳥搜索算法（MACS），根據種群適應度與個體適應度準確判定算法收斂速度并分別對不同鳥窩進行自適應調整，并在偏好隨機游動環節中引入記憶策略，該記憶策略在迭代前期跳出局部最優能力較強，但在迭代后期，在更新解的質量方面效果并不明顯。周歡[11]提出一種具有動態慣性權重的布谷鳥搜索算法，該算法引入動態慣性權重改進鳥窩位置的更新方式，依據動態慣性權重值保留上代鳥窩的最優位置并進行下一代位置更新，顯著減少了迭代次數和運行時間，但存在的問題是當種群規模增大后，慣性權重的選擇范圍不變，對于函數的優化效果有所下降。陳雷等[12]提出一種自適應動態鄰域布谷鳥混合算法（ADNHCS），利用一種圓限定突變的動態鄰域結構來降低經典算法的隨機性，并提出自適應參數調整的策略來提高全局尋優的能力，為2-opt 優化算子使用dropout策略，雖降低了無效計算力，但是其隨機性使解的質量降低。文獻[13]提出了一種ACO與CS相結合的ACO-CS算法，運用局部搜索和保留ACO 算法尋得最優解的方法，獲取最優鳥巢的位置，但存在的問題是該方法只適用于小規模問題，在大規模問題中易陷入局部最優。薩日娜[14]針對云計算中的資源調度問題，提出一種粒子群算法與蟻群優化算法相結合的ACO-PSO 算法，讓螞蟻利用蟻群優化算法進行一次周游，使其具有粒子特性，并結合編譯策略和交叉策略，在一定程度上提高算法的收斂能力，但該算法執行任務量較小，針對多任務問題并沒有進行實驗分析。文獻[15]將混沌理論融入布谷鳥搜索算法，提出一種混沌布谷鳥搜索優化方法，應用混沌映射來調整CS 算法中的步長，并引入精英策略，保留最優鳥巢，改進的算法增強了全局搜索能力，但存在的問題是混沌布谷鳥算法的尋優速度較慢，未能很好地平衡求解質量與速度之間的矛盾。

因此本文針對上述問題，提出了一種交互式學習的布谷鳥搜索算法（ILCSA）。根據布谷鳥和蟻群優化算法的特點，構建雙層交互學習模型，通過布谷鳥和蟻群互相學習雙方的最優解，彌補自身不足，并利用各自的優勢來平衡局部搜索與全局搜索。另引入強化學習策略到CS算法中，深度優化鳥巢初始解，從而加快初期尋優速度并提高解的精度。

2 前期工作

2.1 布谷鳥搜索算法

布谷鳥搜索算法源于布谷鳥繁育行為的模擬，是新型有效的全局優化算法。其原理是將布谷鳥所選宿主的鳥窩映射為空間中的解，用宿主鳥巢所在位置的優劣表示解的適應度值，布谷鳥搜索和選擇鳥窩的過程就是算法的搜索和優化過程。基本的CS算法的主要實現步驟見算法1。

算法1 Cuckoo Search

1.生成N 個鳥巢的初始位置(x1,x2,…,xi,…,xD)

2.計算適應度值F(X)

3.當不滿足迭代停止條件時，重復下述操作

4.對種群中的每個個體X，重復下述動作

5.采用Levy飛行生成候選解Y

6.計算候選解Y 的適應度F(Y)

7.If F(Y)＞F(X) Then

8.用候選解Y 替代種群中的解X

9.按發現概率pa丟棄差的解

10. 用偏好隨機游動產生新解替代丟棄的解

11.記錄全局最優解

12.返回全局最優解

為了實現CS 算法。假設種群中有N 只布谷鳥，每只布谷鳥尋得的鳥巢位置X 代表D維空間問題的一個解，X=(x1,x2,…,xi,…,xD)，xi表示D 維空間某一分量的值，則鳥巢位置更新公式如下：

式中的Levy(λ)是一個隨機數，它服從Levy 概率分布，分布如公式（3）所示：

其中參數μ 和ν 為服從標準正態分布的隨機數，λ 取值范圍為[1,3]，一般取1.5，φ 的取值可根據公式（4）計算得到，公式（4）中的Γ 函數表示Gamma函數。

當宿主發現外來蛋放棄鳥巢，新的鳥巢位置更新如公式（5）所示：

2.2 蟻群優化算法

20世紀90年代Dorigo根據自然界螞蟻的行為提出了Ant System（AS），由于最初用以求解TSP問題，故這里結合求解TSP問題來介紹基本ACO數學模型。

設擬求解的TSP中共有n 座城市，在算法的初始時刻，將m 只螞蟻隨機的放到n 座城市，同時，將每只螞蟻的禁忌表的第一個元素設置為它當前所在的城市。此時各路徑上的信息素量相等，記為τij=c（c 為一較小的常數）。接下來，每只螞蟻根據路徑上殘留的信息素量和啟發式信息（兩城市間的距離）獨立地選擇下一座城市，在時刻t，螞蟻k 從城市i 轉移到城市j 的概率為：

式中，[Jk(i)={1 ,2 ,…,n}-tabuk]表示螞蟻k 下一步允許選擇的城市集合。列表tabuk記錄了螞蟻k 當前走過的城市，即禁忌城市。當所有n 座城市都加入到tabuk中時，螞蟻k 便完成了一次周游，此時螞蟻k 所走過的路徑便是TSP的一個可行解。式（6）中，ηij(t)是一個啟發式因子，表示螞蟻從城市i 轉移到城市j 的期望程度。在AS 算法中，ηij(t)通常取城市i 與城市j 之間距離的倒數。α 和β 分別表示信息素和啟發式因子的相對重要程度。

當所有螞蟻完成一次周游后，各路徑上的信息素根據式（7）、（8）更新：

式中，ρ(0 ＜ρ ＜1)表示路徑上信息素的蒸發系數；1-ρ表示信息素的殘留系數；Δτij表示本次迭代結束后邊ij（城市i 到城市j）上信息素的增量。表示第k 只螞蟻在本次迭代中留在邊ij 上的信息素量。如果螞蟻k沒有經過邊ij，則的值為0。即表示為：

其中Q 表示信息素強度；Lk為第k 只螞蟻在當前循環中所走路徑長度。

2.3 TSP問題

TSP問題是找出一個包含所有N 個城市的路程的環路，假設N 個城市集合為{ x1, x2,…,xn} ，而其目標就是找到一個遍歷序列πi=( x1, x2,…,xn)，使得路徑長度總和f(πi)最短，函數f(π)定義如下：

其中xi為第i 個訪問城市，xi+1為第i+1 個被訪問的城市，D(xi,xi+1)表示兩個城市的歐拉距離，假設兩個城市的坐標為(x1,y1)和(x2,y2)，則其距離計算如公式（11）所示：

3 交互式學習的布谷鳥搜索算法

3.1 布谷鳥搜索算法的離散化

在第2 章中介紹的布谷鳥搜索算法為連續型優化算法，TSP 是組合優化問題，需要先將布谷鳥搜索算法離散化。在2.3節已知TSP問題的解是遍歷n 個城市的路徑長度，因此定義適應度函數為：

將TSP 問題的解進行編碼，每個解表示一個鳥巢，并初始化N 個鳥巢，設第i 個鳥巢的解為Xi=(Xi1,Xi2,…,Xin)，其中Xi1,Xi2,…,Xin代表n 個城市的編號，表示從Xi1出發經過Xi2,…,Xin等城市，最終回到起點。

3.2 雙層交互學習模型

由于TSP 是組合優化問題，而ACO 算法善于解決TSP 等組合優化問題，且算法具有天然的并行性，易與其他優化算法結合，但收斂速度慢，易陷入局部最優；CS 算法參數設置簡單，利用萊維飛行策略進行全局搜索，即全局尋優能力較強，但算法初期尋優速度較慢。結合ACO 算法和CS 算法的特性，故選擇CS 算法與ACO 算法相結合，提出布谷鳥和蟻群合作搜尋最優解的思想，構建雙層交互學習模型，如圖1 所示。為解決CS算法初期尋優速度較慢的問題，先利用ACO算法并行搜索最優解，將尋找的最優解作為CS算法初始解，提高CS 算法初期尋優速度。CS 算法將優化后的解反饋給ACO 算法，并更新其信息素，增加ACO 算法解的多樣性，進而避免ACO算法陷入局部最優。

圖1 雙層交互學習模型

ACO算法作為先行搜索算法，故將其放在底層，采用并行搜索的方式進行尋優，以提高搜尋效率。將蟻群均分為n 個子群，并行搜索最優解，第k 個子群中適應度最好的解定義為fbest,k，將n 個子群的最優解(fbest,1…fbest,k…fbest,n)傳送到高層，作為CS 算法n 個鳥巢的初始解。在CS算法中，引入強化學習策略（RLS），用于平衡全局搜索和局部搜索，深度優化初始解，設優化后的解為全局最優解gbest，將其反饋到底層的子群中，子群利用得到的信息，繼續進行探索解空間，為高層提供初始解。ACO算法和CS算法通過合作尋優，交互學習雙方的最優解，既解決了ACO算法易陷入局部最優的問題，解的質量得到提高，又彌補了CS算法初期信息不足，尋優速度慢的缺陷，收斂速度得到提升。

3.3 具有強化學習策略的CS算法

為能夠充分學習底層優化得到的初始解，將強化學習策略引入CS算法當中，其中包括自適應更新步長，動態調整鳥巢被發現概率以及改進偏好隨機游動位置的更新方式，實施強化學習策略，使其達到深度優化最優解的目的。

3.3.1 自適應步長更新機制

CS算法的眾多改進版本提出了多種自適應更新步長的方案，如文獻[16]中，將尋優步長與迭代次數構成負相關函數，作為步長的更新公式，這些算法改善了基本CS 算法因步長因子固定從而收斂速度慢、易陷入局部最優的缺點。但此類方法的缺陷亦顯而易見：算法在處理復雜優化問題時難以準確把握迭代次數與收斂程度的關系，TSP問題規模不同，收斂程度也不相同，僅通過迭代次數調整步長的方法通用性不佳。

結合以上分析，本小節提出一種新的自適應步長更新機制，設置收斂因子λ 衡量解的收斂程度，依據收斂程度的大小，實時調整每次尋優的步長，使CS算法能夠充分探索解空間。首先利用底層ACO算法尋找的n 個最優解，計算各個鳥巢適應度fbest,k，以及n 個鳥巢適應度的平均值favg，為更好地衡量解的收斂程度大小，在n個適應度中取一權重適應度fc，定義為：

fc是所有鳥巢適應度值的一個權重值，隨迭代時期變化，各鳥巢將集中在最優鳥巢附近，fc反映出CS 算法在整個迭代周期的尋優狀況。利用以上參數，設置收斂因子λ，計算公式為：

λ 值越小，表明鳥巢位置集中，解趨向于收斂，基于λ 反饋的收斂信息，定義步長更新的調節系數δ：

δ 依據收斂因子的變化，動態調節更新步長的大小，則自適應步長更新公式定義為：

其中，αmin與αmax為步長的上下限，經多次實驗取值表明，αmin設為0.001，αmax設為0.005，CS 算法尋優效果最好。

本小節提出的自適應步長更新機制，將底層各子群尋找到的最優解，作為鳥巢初始解，利用此信息，大幅度加快了初期尋優速度。通過收斂因子λ 衡量初始解的收斂程度，基于λ 提供的收斂信息，δ 合理調整步長。在整個迭代周期，步長更新機制實時監控各鳥巢位置的變化，鳥巢位置較為擁擠時，適當增大步長，使其跳出局部最優，提升全局尋優能力；鳥巢位置較為分散時，適當減小步長，使其在各自區域進行搜索，強化局部尋優能力，此更新機制較好地平衡了CS 算法局部尋優能力和全局尋優能力。

3.3.2 概率動態調整機制

傳統的CS 算法中，鳥巢被發現概率Pa為固定值，無法根據迭代時期的變化調整大小，這將會導致好解的丟失，隨機性較強。本小節設置概率動態調整機制，依據各鳥巢適應度值和迭代時期的變化，合理調整發現概率，第k 個鳥巢被發現概率Pk定義為：

計算當前各鳥巢的適應度值，根據適應度值降序排列n 個鳥巢，即適應度值最大的鳥巢排首位，順序l=( 1,2 ,…,n)。其中，γ 為自適應迭代系數，設為：

結合上一小節自適應步長更新機制對鳥巢位置的優化，本節建立概率動態調整機制丟棄鳥巢，根據迭代時期的變化與鳥巢質量的優劣，合理控制丟棄鳥巢的概率。Pk在迭代前期保持較小的發現概率，保證鳥巢位置的多樣性，提升全局搜索能力，使解空間能夠得到充分勘探；隨著迭代次數的增加，自適應迭代系數γ 增大，在局部尋優的同時，保留搜尋到更優解的可能性；另外根據各鳥巢適應度的排名調整發現概率，降低丟棄解的隨機性，避免較優解初期被丟棄，保證算法能夠快速收斂到最優解。

3.3.3 偏好隨機游動位置更新

當鳥巢被發現丟棄時，CS算法按照公式（5）更新鳥巢位置，替換舊鳥巢，更新方式隨機性較強，且無法保證新鳥巢位置的優劣。為保證替換后鳥巢位置的質量，新的位置更新公式定義為：

3.4 算法流程

底層

步驟1 初始化蟻群，設置參數：螞蟻總數m，隨機均分為n 個子群，NCmax=2 000。

步驟2 根據式（6）尋找最優解，根據式（7）更新信息素。

步驟3 根據式（12）計算每個子群中每只螞蟻的適應度，將各子群的最優適應度作為該子群的最優解，將整個種群的最優適應度作為底層最優解。

步驟4 將n 個子群最優解送入高層，重新將螞蟻隨機均分為n 個子群。

高層

步驟5 將n 個子群最優解作為n 個鳥巢初始位置，初始化CS算法各參數。

步驟6 保留當前最優鳥巢位置，根據式（15）更新步長，式（1）更新其他鳥巢位置，計算各鳥巢適應度，若本次迭代最優適應度優于上代，則將本代適應度作為當前最優適應度。

步驟7 根據式（17）計算鳥巢被發現概率Pk，如果隨機數大于Pk，則根據式（19）更新鳥巢的位置，計算更新后鳥巢的適應度，若優于當前最優適應度，則將其替換。

步驟8 輸出最終得到的最優解，并作為高層最優解與底層最優解進行比較，若優于底層最優解，則將高層最優解送入底層各子群，并更新路徑上的信息素；否則返回步驟6。

步驟9 判斷算法終止條件，若滿足則輸出結果；否則返回步驟2。

4 實驗與比較

為了分析ILCSA 的性能，在本章中選取了TSPLIB庫中14個不同的基準算例，進行仿真實驗，將ILCSA分別與經典智能算法中的ACS算法和CS算法，以及混合智能算法中的PSO-ACO[17]算法和CS-ACO[13]算法進行比較。

4.1 實驗環境和算法參數設置

實驗軟件為MATLAB R2016a，CPU 為Core i5，內存為8 GB，Windows10 操作系統。在仿真實驗中，每個TSP算例分別單獨優化20次，算法中的各參數取值如表1所示。

表1 ILCSA相關參數

4.2 對比分析

4.2.1 ILCSA與經典智能優化算法的比較

由于ILCSA基于CS算法和ACO算法，為全面地分析ILCSA的性能，本小節ILCSA將會與CS算法和ACS算法這兩個經典智能優化算法進行比較，其中，ACS 算法屬于ACO 算法，是較為優秀的一種算法，與ACS 對比，更能體現ILCSA 的優越性能。為方便對比，三種算法設置相同的參數，迭代次數最大為2 000，對TSP實例均優化20次。比較結果列于表2中，Opt表示算例的理論最優解，Best和Avg分別表示該算法的最優解和平均解，Dev表示最優解偏差，計算公式為：

表2 ILCSA與CS和ACS算法的比較

從表2 可以看出，在14 個TSP 算例中，ILCSA 找到最優解的算例數為10個，CS算法和ACS算法找到最優解的算例數為3個，表明ILCSA性能與其他兩種算法相比較優越。在未找到最優解的算例中，ILCSA的Dev值都在0.3%以內，其他兩種算法偏差值分別在4%和10%之內，遠大于ILCSA，表明算法穩定性較高，且尋優效果較好。

從算例角度分析，以kroA150 算例為例，ILCSA 的最優解偏差值為0.2%，是CS 和ACS 的和；對于kroB200 算例，ILCSA 的Dev 值分別是CS 和ACS 的和；對 于lin318 算 例，ILCSA 偏 差 值 僅 為0.29%，是CS 的，ACS 的。可見當算例城市數繼續增加時，ILCSA相比CS和ACS 仍然可以保持穩定的優越性。

為更加全面地分析算法的性能，下面從ILCSA求得解的多樣性及收斂速度兩個方面進行研究討論。首先從解的多樣性進行分析，以eil76和kroB100兩個算例為例，ILCSA求得解的分布如圖2（a）、（b）所示，CS和ACS求得解的分布如圖2（c）、（d）、（e）、（f）所示。由對比圖可知，CS 和ACS 算法在迭代前期，解的分布較為局限，多樣性較差，隨迭代時期的變化，解的分布仍保持在較小的范圍之內，表明陷入局部最優；而ILCSA 在整個迭代期內，解的分布范圍較廣，保持著較好的多樣性，表明強化學習策略起到了積極作用，較好地平衡了局部尋優與全局尋優。

圖2 多樣性對比圖

從收斂速度分析，將ILCSA 找到最優解所需迭代次數進行統計，并與其他兩種算法進行比較，結果如圖3 所示。從圖3 分析可知，3 種算法在相同算例中，ILCSA找到最優解所需迭代次數最少，以ch130算例為例，ILCSA 找到最優解所需迭代次數為158，CS 和ACS分別需要643次和1 553次，是ILCSA的4倍和10倍，與ILCSA相比收斂速度較慢。當城市數量增加時，ILCSA迭代次數有所增長，但增長趨勢較為平緩，表明ILCSA在求解不同規模的TSP 算例時，具有穩定性。綜上所述，從解的多樣性和收斂速度兩方面比較，ILCSA 能夠探尋較大的解空間，全局尋優能力較強，且收斂到最優解的速度較快，比經典智能優化算法更具有優勢。

圖3 收斂速度對比圖

4.2.2 ILCSA與混合優化算法的比較

為了進一步驗證ILCSA 的性能，本小節選擇PSOACO和CS-ACO 兩種混合算法進行比較，參數設置與4.2.1小節相同，比較結果列于表3中。

從表3 中的實驗數據整體可以看出，最優解、平均解和偏差值這3 個指標，ILCSA 均優于PSO-ACO 與CS-ACO算法。其中，ILCSA算法基本都能夠找到最優解，未找到最優解的算例中，ILCSA 與最優解的偏差率都保持在0.3%以下；PSO-ACO 與CS-ACO 算法找到最優解的算例與ILCSA 相比較少，偏差率分別在0.4%和0.7%以內，是ILCSA 的1 倍和2 倍。以pr76 算例為例，ILCSA與最優解偏差值為0，PSO-ACO與CS-ACO算法偏差值為0.01%和0.03%；對于kroB150 算例，ILCSA 偏差值為0，而PSO-ACO 和CS-ACO偏差值分別為0.37%和0.64%。綜合以上分析，ILCSA與其他兩種混合優化算法相比，在求解TSP問題中展現出良好的搜索性能。

與上節相同，為全面分析ILCSA 算法的性能，分別從求得解的多樣性和收斂速度兩個方面與混合算法對比分析。本節選取了3 組不同規模的TSP 算例進行多樣性分析，如圖4、圖5 和圖6 所示。在st70 算例中，ILCSA 與PSO-ACO、CS-ACO 相比，在整個迭代期內，求得的解能夠保持較好的多樣性，而其他兩種混合算法，解的質量較差，且分布范圍過于局限。在kroA100和kroB200 兩個算例中，由于城市數增多，PSO-ACO 和CS-ACO 都沒有充分探索解空間，解的分布較為集中，表明算法陷入局部最優，與其相比，ILCSA 由于具有跳出局部最優的能力，在城市數增多時沒有受影響而陷入局部最優，仍然可以保持搜索更大的解空間，因此解的分布范圍較廣，表明算法具有良好的穩定性。

表3 ILCSA與PSO-ACO和CS-ACO算法的比較

圖4 st70算例多樣性對比圖

圖5 kroA100算例多樣性對比圖

圖6 kroB200算例多樣性對比圖

從收斂速度分析，將PSO-ACO 和CS-ACO 找到最優解的最大迭代次數統計如圖7所示，并與ILCSA算法對比。從圖中可以看出，ILCSA 算法在每個算例中，找到最優解所需迭代次數都比其他兩個算法少。以kroA100為例，ILCSA迭代次數為139，PSO-ACO和CSACO算法所需迭代次數分別為253代和632代，比ILCSA多114代和496代；對于kroB150算例，PSO-ACO和CSACO 算法所需迭代次數分別為305 代和800 代，ILCSA為110代，是PSO-ACO的1/3，CS-ACO的1/8。綜合以上分析，ILCSA算法在不同規模算例的運算上都具有較好的收斂效果。

圖7 收斂速度對比圖

4.3 ILCSA收斂效果圖

為了證明ILCSA 算法在不同類型數據集的收斂效果，選取6 個屬性各異的算例進行測試分析，如圖8 所示。從圖中可以看出，在小規模的TSP 算例中，ILCSA可以找到最優解且能夠快速收斂；在大規模的問題中，由于算法引入強化學習策略，對于不同屬性的TSP 算例，ILCSA仍能夠較快的收斂，表明該策略有效，在尋優速度方面具有一定的積極作用。

5 結束語

本文分析了布谷鳥搜索算法和蟻群優化算法的尋優過程和特性，提出了一種交互式學習的布谷鳥搜索算法（ILCSA）。根據蟻群優化算法并行性強的特點和布谷鳥搜索算法全局搜索能力強的優勢，建立雙層交互學習模型，將蟻群優化算法作為底層優化算法，分成子群并行搜索最優解，布谷鳥搜索算法作為高層優化算法，將子群搜索的最優解作為初始解，減少了初期搜索的盲目性，加快了收斂速度；通過在布谷鳥搜索算法中加入強化學習策略，對初始解進行深度優化，進一步提高了解的質量。仿真實驗結果證明，改進的優化算法具有較強的全局搜索能力及魯棒性，避免了算法陷入局部最優，在解決TSP等組合優化問題上具備優勢。

圖8 TSP實例最優路徑圖和收斂曲線