張海南，游曉明，劉 升，劉中強(qiáng)

1.上海工程技術(shù)大學(xué) 電子電氣學(xué)院，上海201620

2.上海工程技術(shù)大學(xué) 管理學(xué)院，上海201620

1 引言

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

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

因此本文針對(duì)上述問(wèn)題，提出了一種交互式學(xué)習(xí)的布谷鳥(niǎo)搜索算法（ILCSA）。根據(jù)布谷鳥(niǎo)和蟻群優(yōu)化算法的特點(diǎn)，構(gòu)建雙層交互學(xué)習(xí)模型，通過(guò)布谷鳥(niǎo)和蟻群互相學(xué)習(xí)雙方的最優(yōu)解，彌補(bǔ)自身不足，并利用各自的優(yōu)勢(shì)來(lái)平衡局部搜索與全局搜索。另引入強(qiáng)化學(xué)習(xí)策略到CS算法中，深度優(yōu)化鳥(niǎo)巢初始解，從而加快初期尋優(yōu)速度并提高解的精度。

2 前期工作

2.1 布谷鳥(niǎo)搜索算法

布谷鳥(niǎo)搜索算法源于布谷鳥(niǎo)繁育行為的模擬，是新型有效的全局優(yōu)化算法。其原理是將布谷鳥(niǎo)所選宿主的鳥(niǎo)窩映射為空間中的解，用宿主鳥(niǎo)巢所在位置的優(yōu)劣表示解的適應(yīng)度值，布谷鳥(niǎo)搜索和選擇鳥(niǎo)窩的過(guò)程就是算法的搜索和優(yōu)化過(guò)程?；镜腃S算法的主要實(shí)現(xiàn)步驟見(jiàn)算法1。

算法1 Cuckoo Search

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

2.計(jì)算適應(yīng)度值F(X)

3.當(dāng)不滿足迭代停止條件時(shí)，重復(fù)下述操作

4.對(duì)種群中的每個(gè)個(gè)體X，重復(fù)下述動(dòng)作

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

6.計(jì)算候選解Y 的適應(yīng)度F(Y)

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

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

9.按發(fā)現(xiàn)概率pa丟棄差的解

10. 用偏好隨機(jī)游動(dòng)產(chǎn)生新解替代丟棄的解

11.記錄全局最優(yōu)解

12.返回全局最優(yōu)解

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

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

其中參數(shù)μ 和ν 為服從標(biāo)準(zhǔn)正態(tài)分布的隨機(jī)數(shù)，λ 取值范圍為[1,3]，一般取1.5，φ 的取值可根據(jù)公式（4）計(jì)算得到，公式（4）中的Γ 函數(shù)表示Gamma函數(shù)。

當(dāng)宿主發(fā)現(xiàn)外來(lái)蛋放棄鳥(niǎo)巢，新的鳥(niǎo)巢位置更新如公式（5）所示：

2.2 蟻群優(yōu)化算法

20世紀(jì)90年代Dorigo根據(jù)自然界螞蟻的行為提出了Ant System（AS），由于最初用以求解TSP問(wèn)題，故這里結(jié)合求解TSP問(wèn)題來(lái)介紹基本ACO數(shù)學(xué)模型。

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

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

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

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

其中Q 表示信息素強(qiáng)度；Lk為第k 只螞蟻在當(dāng)前循環(huán)中所走路徑長(zhǎng)度。

2.3 TSP問(wèn)題

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

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

3 交互式學(xué)習(xí)的布谷鳥(niǎo)搜索算法

3.1 布谷鳥(niǎo)搜索算法的離散化

在第2 章中介紹的布谷鳥(niǎo)搜索算法為連續(xù)型優(yōu)化算法，TSP 是組合優(yōu)化問(wèn)題，需要先將布谷鳥(niǎo)搜索算法離散化。在2.3節(jié)已知TSP問(wèn)題的解是遍歷n 個(gè)城市的路徑長(zhǎng)度，因此定義適應(yīng)度函數(shù)為：

將TSP 問(wèn)題的解進(jìn)行編碼，每個(gè)解表示一個(gè)鳥(niǎo)巢，并初始化N 個(gè)鳥(niǎo)巢，設(shè)第i 個(gè)鳥(niǎo)巢的解為Xi=(Xi1,Xi2,…,Xin)，其中Xi1,Xi2,…,Xin代表n 個(gè)城市的編號(hào)，表示從Xi1出發(fā)經(jīng)過(guò)Xi2,…,Xin等城市，最終回到起點(diǎn)。

3.2 雙層交互學(xué)習(xí)模型

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

圖1 雙層交互學(xué)習(xí)模型

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

3.3 具有強(qiáng)化學(xué)習(xí)策略的CS算法

為能夠充分學(xué)習(xí)底層優(yōu)化得到的初始解，將強(qiáng)化學(xué)習(xí)策略引入CS算法當(dāng)中，其中包括自適應(yīng)更新步長(zhǎng)，動(dòng)態(tài)調(diào)整鳥(niǎo)巢被發(fā)現(xiàn)概率以及改進(jìn)偏好隨機(jī)游動(dòng)位置的更新方式，實(shí)施強(qiáng)化學(xué)習(xí)策略，使其達(dá)到深度優(yōu)化最優(yōu)解的目的。

3.3.1 自適應(yīng)步長(zhǎng)更新機(jī)制

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

結(jié)合以上分析，本小節(jié)提出一種新的自適應(yīng)步長(zhǎng)更新機(jī)制，設(shè)置收斂因子λ 衡量解的收斂程度，依據(jù)收斂程度的大小，實(shí)時(shí)調(diào)整每次尋優(yōu)的步長(zhǎng)，使CS算法能夠充分探索解空間。首先利用底層ACO算法尋找的n 個(gè)最優(yōu)解，計(jì)算各個(gè)鳥(niǎo)巢適應(yīng)度f(wàn)best,k，以及n 個(gè)鳥(niǎo)巢適應(yīng)度的平均值favg，為更好地衡量解的收斂程度大小，在n個(gè)適應(yīng)度中取一權(quán)重適應(yīng)度f(wàn)c，定義為：

fc是所有鳥(niǎo)巢適應(yīng)度值的一個(gè)權(quán)重值，隨迭代時(shí)期變化，各鳥(niǎo)巢將集中在最優(yōu)鳥(niǎo)巢附近，fc反映出CS 算法在整個(gè)迭代周期的尋優(yōu)狀況。利用以上參數(shù)，設(shè)置收斂因子λ，計(jì)算公式為：

λ 值越小，表明鳥(niǎo)巢位置集中，解趨向于收斂，基于λ 反饋的收斂信息，定義步長(zhǎng)更新的調(diào)節(jié)系數(shù)δ：

δ 依據(jù)收斂因子的變化，動(dòng)態(tài)調(diào)節(jié)更新步長(zhǎng)的大小，則自適應(yīng)步長(zhǎng)更新公式定義為：

其中，αmin與αmax為步長(zhǎng)的上下限，經(jīng)多次實(shí)驗(yàn)取值表明，αmin設(shè)為0.001，αmax設(shè)為0.005，CS 算法尋優(yōu)效果最好。

本小節(jié)提出的自適應(yīng)步長(zhǎng)更新機(jī)制，將底層各子群尋找到的最優(yōu)解，作為鳥(niǎo)巢初始解，利用此信息，大幅度加快了初期尋優(yōu)速度。通過(guò)收斂因子λ 衡量初始解的收斂程度，基于λ 提供的收斂信息，δ 合理調(diào)整步長(zhǎng)。在整個(gè)迭代周期，步長(zhǎng)更新機(jī)制實(shí)時(shí)監(jiān)控各鳥(niǎo)巢位置的變化，鳥(niǎo)巢位置較為擁擠時(shí)，適當(dāng)增大步長(zhǎng)，使其跳出局部最優(yōu)，提升全局尋優(yōu)能力；鳥(niǎo)巢位置較為分散時(shí)，適當(dāng)減小步長(zhǎng)，使其在各自區(qū)域進(jìn)行搜索，強(qiáng)化局部尋優(yōu)能力，此更新機(jī)制較好地平衡了CS 算法局部尋優(yōu)能力和全局尋優(yōu)能力。

3.3.2 概率動(dòng)態(tài)調(diào)整機(jī)制

傳統(tǒng)的CS 算法中，鳥(niǎo)巢被發(fā)現(xiàn)概率Pa為固定值，無(wú)法根據(jù)迭代時(shí)期的變化調(diào)整大小，這將會(huì)導(dǎo)致好解的丟失，隨機(jī)性較強(qiáng)。本小節(jié)設(shè)置概率動(dòng)態(tài)調(diào)整機(jī)制，依據(jù)各鳥(niǎo)巢適應(yīng)度值和迭代時(shí)期的變化，合理調(diào)整發(fā)現(xiàn)概率，第k 個(gè)鳥(niǎo)巢被發(fā)現(xiàn)概率Pk定義為：

計(jì)算當(dāng)前各鳥(niǎo)巢的適應(yīng)度值，根據(jù)適應(yīng)度值降序排列n 個(gè)鳥(niǎo)巢，即適應(yīng)度值最大的鳥(niǎo)巢排首位，順序l=( 1,2 ,…,n)。其中，γ 為自適應(yīng)迭代系數(shù)，設(shè)為：

結(jié)合上一小節(jié)自適應(yīng)步長(zhǎng)更新機(jī)制對(duì)鳥(niǎo)巢位置的優(yōu)化，本節(jié)建立概率動(dòng)態(tài)調(diào)整機(jī)制丟棄鳥(niǎo)巢，根據(jù)迭代時(shí)期的變化與鳥(niǎo)巢質(zhì)量的優(yōu)劣，合理控制丟棄鳥(niǎo)巢的概率。Pk在迭代前期保持較小的發(fā)現(xiàn)概率，保證鳥(niǎo)巢位置的多樣性，提升全局搜索能力，使解空間能夠得到充分勘探；隨著迭代次數(shù)的增加，自適應(yīng)迭代系數(shù)γ 增大，在局部尋優(yōu)的同時(shí)，保留搜尋到更優(yōu)解的可能性；另外根據(jù)各鳥(niǎo)巢適應(yīng)度的排名調(diào)整發(fā)現(xiàn)概率，降低丟棄解的隨機(jī)性，避免較優(yōu)解初期被丟棄，保證算法能夠快速收斂到最優(yōu)解。

3.3.3 偏好隨機(jī)游動(dòng)位置更新

當(dāng)鳥(niǎo)巢被發(fā)現(xiàn)丟棄時(shí)，CS算法按照公式（5）更新鳥(niǎo)巢位置，替換舊鳥(niǎo)巢，更新方式隨機(jī)性較強(qiáng)，且無(wú)法保證新鳥(niǎo)巢位置的優(yōu)劣。為保證替換后鳥(niǎo)巢位置的質(zhì)量，新的位置更新公式定義為：

3.4 算法流程

底層

步驟1 初始化蟻群，設(shè)置參數(shù)：螞蟻總數(shù)m，隨機(jī)均分為n 個(gè)子群，NCmax=2 000。

步驟2 根據(jù)式（6）尋找最優(yōu)解，根據(jù)式（7）更新信息素。

步驟3 根據(jù)式（12）計(jì)算每個(gè)子群中每只螞蟻的適應(yīng)度，將各子群的最優(yōu)適應(yīng)度作為該子群的最優(yōu)解，將整個(gè)種群的最優(yōu)適應(yīng)度作為底層最優(yōu)解。

步驟4 將n 個(gè)子群最優(yōu)解送入高層，重新將螞蟻隨機(jī)均分為n 個(gè)子群。

高層

步驟5 將n 個(gè)子群最優(yōu)解作為n 個(gè)鳥(niǎo)巢初始位置，初始化CS算法各參數(shù)。

步驟6 保留當(dāng)前最優(yōu)鳥(niǎo)巢位置，根據(jù)式（15）更新步長(zhǎng)，式（1）更新其他鳥(niǎo)巢位置，計(jì)算各鳥(niǎo)巢適應(yīng)度，若本次迭代最優(yōu)適應(yīng)度優(yōu)于上代，則將本代適應(yīng)度作為當(dāng)前最優(yōu)適應(yīng)度。

步驟7 根據(jù)式（17）計(jì)算鳥(niǎo)巢被發(fā)現(xiàn)概率Pk，如果隨機(jī)數(shù)大于Pk，則根據(jù)式（19）更新鳥(niǎo)巢的位置，計(jì)算更新后鳥(niǎo)巢的適應(yīng)度，若優(yōu)于當(dāng)前最優(yōu)適應(yīng)度，則將其替換。

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

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

4 實(shí)驗(yàn)與比較

為了分析ILCSA 的性能，在本章中選取了TSPLIB庫(kù)中14個(gè)不同的基準(zhǔn)算例，進(jìn)行仿真實(shí)驗(yàn)，將ILCSA分別與經(jīng)典智能算法中的ACS算法和CS算法，以及混合智能算法中的PSO-ACO[17]算法和CS-ACO[13]算法進(jìn)行比較。

4.1 實(shí)驗(yàn)環(huán)境和算法參數(shù)設(shè)置

實(shí)驗(yàn)軟件為MATLAB R2016a，CPU 為Core i5，內(nèi)存為8 GB，Windows10 操作系統(tǒng)。在仿真實(shí)驗(yàn)中，每個(gè)TSP算例分別單獨(dú)優(yōu)化20次，算法中的各參數(shù)取值如表1所示。

表1 ILCSA相關(guān)參數(shù)

4.2 對(duì)比分析

4.2.1 ILCSA與經(jīng)典智能優(yōu)化算法的比較

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

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

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

從算例角度分析，以kroA150 算例為例，ILCSA 的最優(yōu)解偏差值為0.2%，是CS 和ACS 的和；對(duì)于kroB200 算例，ILCSA 的Dev 值分別是CS 和ACS 的和；對(duì) 于lin318 算 例，ILCSA 偏 差 值 僅 為0.29%，是CS 的，ACS 的?？梢?jiàn)當(dāng)算例城市數(shù)繼續(xù)增加時(shí)，ILCSA相比CS和ACS 仍然可以保持穩(wěn)定的優(yōu)越性。

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

圖2 多樣性對(duì)比圖

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

圖3 收斂速度對(duì)比圖

4.2.2 ILCSA與混合優(yōu)化算法的比較

為了進(jìn)一步驗(yàn)證ILCSA 的性能，本小節(jié)選擇PSOACO和CS-ACO 兩種混合算法進(jìn)行比較，參數(shù)設(shè)置與4.2.1小節(jié)相同，比較結(jié)果列于表3中。

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

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

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

圖4 st70算例多樣性對(duì)比圖

圖5 kroA100算例多樣性對(duì)比圖

圖6 kroB200算例多樣性對(duì)比圖

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

圖7 收斂速度對(duì)比圖

4.3 ILCSA收斂效果圖

為了證明ILCSA 算法在不同類型數(shù)據(jù)集的收斂效果，選取6 個(gè)屬性各異的算例進(jìn)行測(cè)試分析，如圖8 所示。從圖中可以看出，在小規(guī)模的TSP 算例中，ILCSA可以找到最優(yōu)解且能夠快速收斂；在大規(guī)模的問(wèn)題中，由于算法引入強(qiáng)化學(xué)習(xí)策略，對(duì)于不同屬性的TSP 算例，ILCSA仍能夠較快的收斂，表明該策略有效，在尋優(yōu)速度方面具有一定的積極作用。

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

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

圖8 TSP實(shí)例最優(yōu)路徑圖和收斂曲線