發(fā)現(xiàn)概率參數(shù)自適應(yīng)調(diào)節(jié)的布谷鳥改進(jìn)算法

賈 涵，連曉峰

北京工商大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，北京 100048

1 前言

迄今為止優(yōu)化算法分為傳統(tǒng)優(yōu)化算法和智能優(yōu)化算法。智能優(yōu)化算法的理論研究主要包括算法的穩(wěn)定性分析、收斂性分析、收斂速度分析及算法的計(jì)算復(fù)雜性分析等，這些研究中包含了對算法參數(shù)設(shè)置的一些理論性指導(dǎo)。其中，關(guān)于穩(wěn)定性的研究結(jié)果相對較多，但收斂速度、收斂性分析和計(jì)算復(fù)雜性的研究相對較少[1-2]。智能優(yōu)化算法的應(yīng)用研究覆蓋了計(jì)算機(jī)、航空、電力電子、電磁、地球物理、生物醫(yī)學(xué)等大部分科技領(lǐng)域。

大量學(xué)者對常用優(yōu)化算法進(jìn)行改進(jìn)研究，主要是通過對參數(shù)的動態(tài)調(diào)節(jié)，參數(shù)的動態(tài)調(diào)節(jié)可分為適應(yīng)性調(diào)節(jié)、自適應(yīng)性調(diào)節(jié)和非自適應(yīng)調(diào)節(jié)三種基本類型。探索與開發(fā)的權(quán)衡問題源于智能優(yōu)化算法，主要是針對一些基于種群的進(jìn)化算法。探索-開發(fā)的權(quán)衡關(guān)系控制著算法的計(jì)算代價和收斂質(zhì)量，在保證算法的計(jì)算時間較短的前提下，提高算法的收斂速度和尋優(yōu)能力。改進(jìn)算法的主要思想是借助探索-開發(fā)的平衡關(guān)系來動態(tài)調(diào)節(jié)某些相關(guān)參數(shù)。為了實(shí)現(xiàn)模態(tài)復(fù)雜問題的高效全局優(yōu)化，任何優(yōu)化算法必須兼具“全局探索”和“局部開發(fā)”能力，并在二者之間做出適當(dāng)?shù)臋?quán)衡，有效的權(quán)衡有助于減少計(jì)算代價和實(shí)現(xiàn)高效的優(yōu)化。

元啟發(fā)式群體智能算法是受“集體智慧”啟發(fā)而提出的高效算法。集體智慧是通過環(huán)境中大量相同因子的合作而出現(xiàn)的，例如魚群、鳥群和螞蟻群。在自然界中，集體智慧通常被用于解決動物覓食，逃避追捕或生存環(huán)境重新定位等問題。

群體智能優(yōu)化算法主要受兩個基本算法的啟發(fā)：（1）蟻群算法，是受螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為啟發(fā)；（2）粒子群優(yōu)化算法，是受鳥群和魚群的覓食行為啟發(fā)。群體智能“算法”或“策略”被認(rèn)為是自適應(yīng)策略，并且通常應(yīng)用于搜索和優(yōu)化領(lǐng)域。常用的群體智能優(yōu)化算法有遺傳算法（Genetic Algorithm，GA）、螢火蟲算法（Glowworm Swarm Optimization，GSO）、蟻群算法（Ant Colony Optimization，ACO）、人工蜂群算法（Artificial Bee Colony algorithm，ABC）和粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）等。

布谷鳥搜索算法（Cuckoo Search algorithm，CS）是由英國牛津大學(xué)的Yang等學(xué)者提出的一種元啟發(fā)式群體智能算法[3-5]。該算法是在長期研究布谷鳥生活習(xí)性的基礎(chǔ)上提出的，主要利用了布谷鳥卵育寄生和萊維（Lévy）飛行的特性，其優(yōu)點(diǎn)是具有良好的適應(yīng)性，參數(shù)少，隨機(jī)搜索路徑優(yōu)并且尋優(yōu)能力強(qiáng)[6]。

該算法自提出以來得到了廣泛的研究。在文獻(xiàn)[7]中Yang和Rajabioun等人將CS算法應(yīng)用于工程優(yōu)化和多目標(biāo)優(yōu)化等實(shí)際問題中。文獻(xiàn)[8-9]中Walton等人在布谷鳥尋找鳥巢的時候引入了交換信息，但是由于對CS算法中的隨機(jī)步長進(jìn)行了改進(jìn)，導(dǎo)致算法極易陷入局部最優(yōu)并且全局搜索能力過弱。在文獻(xiàn)[10]中Tuba等學(xué)者對鳥巢的發(fā)現(xiàn)概率Pa和步長進(jìn)行了動態(tài)自適應(yīng)的調(diào)整，提高了算法的收斂性能，但是由于算法完全依賴隨機(jī)游走，很難保證其搜索精度。在文獻(xiàn)[11]中王凡等學(xué)者在迭代過程中對鳥窩位置加入高斯擾動，提高了CS算法的收斂速度，但是由于引入了高斯算子，使算法在搜索后期穩(wěn)定性下降。在文獻(xiàn)[12-13]中賀興時等學(xué)者通過分析鳥窩位置的群體狀態(tài)轉(zhuǎn)移過程，提高了算法的全局搜索能力，但是由于加入Markov鏈，導(dǎo)致算法在搜索后期收斂速度慢。文獻(xiàn)[14-15]通過對種群的再分組，并根據(jù)當(dāng)前不同的搜索階段對步長進(jìn)行預(yù)先設(shè)置，提高了CS算法的搜索性能，但是算法在轉(zhuǎn)換搜索階段時增加了算法的計(jì)算時間并且存在很大的隨機(jī)性。

從國內(nèi)外的研究現(xiàn)狀可以看出，CS算法還有很大的發(fā)展空間。但是CS算法也存在一些缺陷，比如在搜索后期收斂速度慢，全局尋優(yōu)能力弱，不穩(wěn)定并且易陷入局部最優(yōu)，因此本文在深入分析CS算法的基礎(chǔ)上，提出了發(fā)現(xiàn)概率參數(shù)自適應(yīng)調(diào)節(jié)的布谷鳥搜索算法（Adaptive Probability of Cuckoo Search algorithm，APCS）。首先設(shè)置一個狀態(tài)判別參數(shù)Ps用來切換探索和開發(fā)的狀態(tài)，然后設(shè)置一個探索開發(fā)平衡參數(shù)Peb使探索和開發(fā)階段達(dá)到一個互補(bǔ)，最后實(shí)現(xiàn)了對發(fā)現(xiàn)概率Pa的動態(tài)調(diào)整。實(shí)驗(yàn)結(jié)果表明了APCS算法較好地解決了CS算法后期存在的收斂速度慢、不穩(wěn)定等缺點(diǎn)。

2 CS算法的基本原理

布谷鳥搜索算法是模擬布谷鳥尋窩產(chǎn)卵的行為和萊維飛行特性實(shí)現(xiàn)的元啟發(fā)式群智能優(yōu)化算法，其中布谷鳥的卵育寄生行為和萊維飛行機(jī)制是算法的核心內(nèi)容。

2.1 布谷鳥的卵育寄生行為

根據(jù)生物學(xué)家長期觀察，布谷鳥的卵育寄生行為的繁殖步驟如下[3-5]：

步驟1布谷鳥會在繁殖期尋找合適的宿主（大多為雀形目鳥類）。

步驟2布谷鳥趁宿主外出時快速產(chǎn)蛋并將自己的蛋放在宿主鳥巢里。

步驟3同時為了提高幼雛的成活率會移走一枚宿主自己的蛋，使得巢中鳥蛋數(shù)量不變，在宿主不發(fā)現(xiàn)的情況下代為孵化。

步驟4布谷鳥的蛋孵化時間短，通常最先孵出。之后會將同巢的其余鳥蛋推出巢外，以至于得到更高的成活率。

布谷鳥算法示意圖如圖1。

圖1 布谷鳥算法示意圖

2.2 布谷鳥的萊維飛行

以法國數(shù)學(xué)家保羅·萊維（Paul Lévy）命名的萊維飛行機(jī)制具有較強(qiáng)的隨機(jī)性，其步長服從冪律分布。這是一種典型的隨機(jī)游走過程，布谷鳥搜索算法使用的就是這種飛行機(jī)制。當(dāng)布谷鳥在尋找鳥巢時，其飛行就是一種方向隨機(jī)的運(yùn)動，飛行軌跡和前一時刻的飛行軌跡存在一定的偏差。布谷鳥飛行的過程主要以小步長為主，但是偶爾有較大步長的位移，因此布谷鳥不會重復(fù)停留在一個地方進(jìn)行搜索[16-17]。

2.3 CS算法的實(shí)現(xiàn)

在CS算法的具體實(shí)現(xiàn)中，首先提出以下三個理想化的條件：

（1）布谷鳥每次隨機(jī)選擇一個最優(yōu)的鳥巢完成寄生；

（2）孵化效果最好的鳥巢將會繼續(xù)利用；

（3）每次選擇寄生的鳥巢數(shù)量是不變的，布谷鳥蛋在宿主巢中被發(fā)現(xiàn)的概率為Pa。在這種情況下，宿主可以拋出鳥蛋或者放棄當(dāng)前鳥巢，并建一個新的巢。為了方便研究和計(jì)算，這個理想化規(guī)則可以近似為被新巢替換（新的隨機(jī)解決方案）的概率為Pa[18]。

在理想化的條件下，布谷鳥的位置更新公式如下：

式中，t表示隨機(jī)步長。

上述是布谷鳥卵育寄生行為、萊維飛行機(jī)制和布谷鳥搜索算法的具體實(shí)現(xiàn)步驟。通過上述內(nèi)容可以看出，布谷鳥搜索算法具有參數(shù)少，對目標(biāo)問題的初始狀態(tài)低，隨機(jī)搜索路徑優(yōu)和尋優(yōu)能力強(qiáng)等優(yōu)點(diǎn)。

3 發(fā)現(xiàn)概率參數(shù)自適應(yīng)調(diào)節(jié)的布谷鳥搜索算法

CS算法在計(jì)算時比較繁瑣，并且因?yàn)殡S機(jī)游走的飛行機(jī)制導(dǎo)致相關(guān)性能會受到影響[19]。于是本文將基本CS算法中的Pa由固定值調(diào)整為動態(tài)值，固定值將會影響算法的全局搜索（探索）和局部搜索（開發(fā)）性能，并且會導(dǎo)致算法收斂性能弱。

為此，本文提出一種發(fā)現(xiàn)概率參數(shù)自適應(yīng)調(diào)節(jié)的布谷鳥改進(jìn)算法（APCS）。該算法的核心思想是通過協(xié)調(diào)探索（全局）和開發(fā)（局部）的平衡關(guān)系，使參數(shù)Pa由固定值變成自適應(yīng)的動態(tài)參數(shù)，以提高算法的收斂性能和尋優(yōu)能力。

3.1 狀態(tài)判別參數(shù)

若算法處在探索階段的時候，局部搜索能力較弱，容易陷入局部最優(yōu)；若算法處在開發(fā)階段的時候，全局搜索能力較弱[20]。為了實(shí)現(xiàn)多目標(biāo)問題的優(yōu)化，任何優(yōu)化算法必須兼具“全局探索”和“局部開發(fā)”能力，并在二者之間做出適當(dāng)?shù)臋?quán)衡，才能使算法的性能達(dá)到最優(yōu)。APCS算法將利用Pareto最優(yōu)解，使探索和開發(fā)的性能在一定程度上達(dá)到最好的狀態(tài)，在全局搜索能力最優(yōu)的同時局部搜索能力也保持較優(yōu)狀態(tài)。從Pareto最優(yōu)解集中選擇合適的解來作為探索-開發(fā)的判別標(biāo)準(zhǔn)[21-22]。

在可行性區(qū)域 Xf中，對于 x∈(0,1)，不存在 x′∈Xf，使 得 F(x′)=(f1(x′),f2(x′),…,fk(x′)) 占 優(yōu) 于 F(x)=(f1(x),f2(x),…,fk(x))，則稱 x為Xf上的Pareto最優(yōu)解。

APCS算法的探索-開發(fā)模式如式（3）所示：

式中，Ps主要用于判斷當(dāng)前搜索過程處于探索階段還是開發(fā)階段；nupdate為更新的鳥巢數(shù)量；nall為全部的鳥巢數(shù)量。當(dāng)Ps＜x時，APCS算法處于開發(fā)階段，正在進(jìn)行局部搜索，此時算法極易陷入局部最優(yōu)解，導(dǎo)致算法的種群多樣性下降，并且收斂性能不佳；當(dāng)Ps＞x時，APCS算法處于探索階段，正在進(jìn)行全局搜索，此時雖然算法保持了種群多樣性，但是全局性太強(qiáng)并且易陷入局部最優(yōu)，使算法的性能不能達(dá)到最優(yōu)狀態(tài)。

3.2 探索開發(fā)平衡參數(shù)

探索（Exploration）是指在搜索優(yōu)化過程中從整個解空間范圍內(nèi)獲取目標(biāo)函數(shù)的信息，以便定位全局最優(yōu)解所在的局部區(qū)域。開發(fā)（Exploitation）是指在搜索優(yōu)化過程中對解空間中有希望包含最優(yōu)解的局部區(qū)域進(jìn)行搜索，以便找到局部最優(yōu)解甚至全局最優(yōu)解的搜索策略。通常將探索和開發(fā)分別視為全局搜索和局部搜索。

為了協(xié)調(diào)兩個階段的不足并發(fā)揮各階段的優(yōu)勢，設(shè)置參數(shù)Peb使探索和開發(fā)階段達(dá)到一個互補(bǔ)狀態(tài)，使APCS算法的收斂性能和尋優(yōu)能力在兼具“全局探索”和“局部開發(fā)”兩個階段下發(fā)揮出最好的性能，如式（4）所示：

當(dāng)Ps較大時，算法處于探索階段，那么為了提高算法的開發(fā)能力，使得Peb為較小值；同理，當(dāng)Ps較小時，算法處于開發(fā)階段，那么為了提高算法的全局搜索能力，此時需要Peb為較大值。

3.3 發(fā)現(xiàn)概率參數(shù)

APCS算法將發(fā)現(xiàn)概率Pa由一個固定值改成動態(tài)值，主要通過對參數(shù)Ps和Peb的動態(tài)調(diào)整而提出用式（5）實(shí)現(xiàn)算法參數(shù)Pa的自適應(yīng)調(diào)整：

其中，i為當(dāng)前迭代次數(shù)；imax為最大迭代次數(shù)；μ是在區(qū)間[0,1]內(nèi)均勻分布隨機(jī)產(chǎn)生的實(shí)數(shù)；λ為隨機(jī)搜索軌跡(1＜λ≤3)；表示當(dāng)Ps的狀態(tài)處于探索（開發(fā)）階段時，可以對開發(fā)（探索）的性能進(jìn)行互補(bǔ)，達(dá)到一種平衡狀態(tài)。

當(dāng)Ps＞x時，雖然計(jì)算時間短，但是收斂性能極差，算法的全局搜索性能過強(qiáng)，因此通過對算法進(jìn)行改善。以全局搜索為主，局部搜索為輔，使探索階段和開發(fā)階段保持平衡，最后求出使算法收斂性能和尋優(yōu)能力較好的動態(tài)Pa值。當(dāng)Ps＜x時，算法的局部搜索性能過強(qiáng)，將會極易陷入局部最優(yōu)。同理通過對算法進(jìn)行改善，進(jìn)行局部搜索的同時也在進(jìn)行全局搜索，最終將會隨著迭代的增加而達(dá)到全局最優(yōu)和局部最優(yōu)的一種平衡。

APCS算法將參數(shù)Pa由固定值調(diào)整成動態(tài)值，實(shí)現(xiàn)了自適應(yīng)的搜索策略，通過迭代次數(shù)的增加Pa的值也同時增大，使算法同時兼具探索性和開發(fā)性。算法的全局搜索能力往往會隨著迭代的進(jìn)行而減弱，逐漸向局部搜索轉(zhuǎn)變，隨著算法的逐漸收斂，多數(shù)解將集中到較小的局部區(qū)域，最終使算法的各項(xiàng)性能得到提升。

3.4 算法實(shí)現(xiàn)

根據(jù)上述的條件，APCS算法的具體實(shí)現(xiàn)步驟如下：

步驟1定義目標(biāo)函數(shù) f(x)，并隨機(jī)生成nall個鳥巢的初始位置xi(i=1,2,…,nall)。

步驟2計(jì)算每個鳥巢對應(yīng)的目標(biāo)函數(shù)，得到最優(yōu)值，并且利用位置更新公式對其余鳥巢的位置進(jìn)行更新。

步驟3對比目前函數(shù)最優(yōu)值，并作出相應(yīng)改變。

步驟4計(jì)算參數(shù)Ps并與Pareto最優(yōu)解求出的判別標(biāo)準(zhǔn)x進(jìn)行對比，若Ps＜x時，處于開發(fā)階段，反之則處于探索階段。

步驟5計(jì)算參數(shù)Peb實(shí)現(xiàn)對當(dāng)前階段性能的互補(bǔ)。

步驟6在位置更新后，用隨機(jī)數(shù)r∈[0,1]和更新后的Pa進(jìn)行對比，若r＞Pa，則對x(t+1)i進(jìn)行改變，相反則保持不變。最后保留最好的一組鳥巢位置y(t+1)i。

步驟7若未達(dá)到最大迭代次數(shù)或最小誤差要求，則返回步驟2，否則，繼續(xù)下一步。

APCS算法的流程圖如圖2所示。

圖2 APCS算法流程圖

4 數(shù)值仿真與分析

通過仿真實(shí)驗(yàn)，測試上述改進(jìn)算法的性能，并與CS算法的性能進(jìn)行比較。仿真環(huán)境為Windows 7操作系統(tǒng)，Intel處理器，2.10 GHz，內(nèi)存為4 GB，仿真軟件為MATLAB 2014a。

4.1 測試函數(shù)

為了充分測試算法的性能和特點(diǎn)，選擇8個標(biāo)準(zhǔn)函數(shù)進(jìn)行測試，其中涵蓋了單模態(tài)和多模態(tài)函數(shù)，包括Sphere、Shelter、Griewank和Rastrigin等。各基準(zhǔn)函數(shù)的參數(shù)設(shè)置如表2所示，CS算法和APCS算法分別進(jìn)行30次獨(dú)立實(shí)驗(yàn)，鳥巢n=30，最大迭代次數(shù)imax為600，發(fā)現(xiàn)概率Pa按式（10）進(jìn)行動態(tài)調(diào)整，若收斂精度小于1.00E-15視為0。

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

表2和表3分別記錄了APCS算法和CS算法在10維和30維的情況下，通過表1的8種測試函數(shù)得到的全局最優(yōu)值、最差值和平均值的相關(guān)實(shí)驗(yàn)數(shù)據(jù)，來對比兩種算法的收斂性能和全局尋優(yōu)能力。

在10維的狀態(tài)下實(shí)驗(yàn)結(jié)果如表2所示，最佳適應(yīng)度值隨迭代次數(shù)變化的曲線如圖3所示。

f1和 f2是一類簡單的單峰且可分函數(shù)，這類函數(shù)在整個搜索空間內(nèi)只有一個峰值，APCS算法分別比CS算法的最優(yōu)值提高了43個和28個數(shù)量級，并且APCS基本接近了理論最優(yōu)值。從圖3（a）和圖3（b）可以看出APCS算法的收斂性能優(yōu)于CS算法，就穩(wěn)定性而言，也比CS算法更加穩(wěn)定；f3也是簡單的單峰且可分函數(shù)，APCS算法的最優(yōu)值提高了54個數(shù)量級，在該基準(zhǔn)函數(shù)下，APCS算法具有更強(qiáng)的收斂性；f4和 f6是一類復(fù)雜的多峰、可分且高維的函數(shù)，并且這兩個函數(shù)都是典型的多模態(tài)非線性全局優(yōu)化函數(shù)，整個搜索空間中存在多個局部最優(yōu)值，適用于衡量算法的尋優(yōu)能力，并且使算法的全局尋優(yōu)能力和局部尋優(yōu)能力保持平衡。隨著迭代次數(shù)的增加，APCS算法可以更快地收斂，并且減少了計(jì)算代價。在這兩個基準(zhǔn)函數(shù)的測試下，APCS算法的最優(yōu)值、最差值和平均值均為0，說明該算法的穩(wěn)定性較好；f5和 f7是一類復(fù)雜的多峰、不可分且高維的函數(shù)，通過圖3（e）和圖3（g）可以看出，APCS算法的收斂速度明顯優(yōu)于CS算法，并且從表2的實(shí)驗(yàn)數(shù)據(jù)中可以看出APCS算法的最優(yōu)值分別提高了50個和65個數(shù)量級，因此較CS算法而言，其收斂精度和全局搜索能力得到了較大的改善；f8是一類復(fù)雜的多峰、不可分且低維的函數(shù)，如圖3（h）所示，APCS算法和CS算法皆避免了過早收斂，但是APCS算法較CS算法在尋優(yōu)能力上更能兼顧全局搜索和局部搜索，使算法不易陷入局部最優(yōu)又能在較短時間內(nèi)尋找到局部最優(yōu)。

在30維的狀態(tài)下實(shí)驗(yàn)結(jié)果如表3所示，最佳適應(yīng)度值隨迭代次數(shù)變化的曲線如圖4所示。

表1 基準(zhǔn)測試函數(shù)

圖3 10維測試結(jié)果

表2 10維實(shí)驗(yàn)結(jié)果分析

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

圖4 30維測試結(jié)果

表3列出了在30維情況下的測試結(jié)果，通過對比分析全局最優(yōu)值、最差值和平均值的實(shí)驗(yàn)數(shù)據(jù)驗(yàn)證了APCS算法的各項(xiàng)性能指標(biāo)優(yōu)于CS算法。對于 f1、f2和 f3函數(shù)，APCS算法的優(yōu)化程度較CS算法的優(yōu)化程度雖然不是十分明顯，但是收斂速度還是得到了改善，并且通過表3的實(shí)驗(yàn)數(shù)據(jù)可以看出，APCS算法具有更好的全局搜索能力，同時又增強(qiáng)了局部搜索能力；f5函數(shù)是高維且多峰函數(shù)，不易找到全局最優(yōu)解，但是通過對概率的自適應(yīng)調(diào)整以后，尋優(yōu)能力得到了提高，并且APCS算法的收斂速度較快，同時節(jié)省了計(jì)算時間；f6和 f8在30維的情況下，APCS算法的收斂速度遠(yuǎn)遠(yuǎn)高于CS算法的收斂速度，并且迭代次數(shù)減少。

通過8個基準(zhǔn)函數(shù)，對APCS算法和CS算法的各項(xiàng)性能指標(biāo)在10維和30維的狀態(tài)下進(jìn)行了對比分析。實(shí)驗(yàn)數(shù)據(jù)和曲線圖表明，APCS算法的收斂速度、尋優(yōu)能力、穩(wěn)定性和計(jì)算時間都優(yōu)于CS算法，驗(yàn)證了算法的有效性和改進(jìn)后的優(yōu)勢。

5 結(jié)束語

本文在原始的CS算法基礎(chǔ)上，著重研究了發(fā)現(xiàn)概率參數(shù)自適應(yīng)調(diào)節(jié)的布谷鳥改進(jìn)算法。由于基本的CS算法在搜索后期存在收斂速度慢，尋優(yōu)能力低，易陷入局部最優(yōu)并且不穩(wěn)定等問題，通過對概率的自適應(yīng)調(diào)整加快了算法的收斂速度，提升了算法在兼顧全局搜索和局部搜索時的尋優(yōu)能力，并且在多峰函數(shù)下都不易陷入局部最優(yōu)。實(shí)驗(yàn)結(jié)果更一步驗(yàn)證了，APCS算法的收斂性能優(yōu)并且相對穩(wěn)定。從本文參考的文獻(xiàn)中觀察到，CS算法及相關(guān)改進(jìn)算法在醫(yī)療、圖像處理、經(jīng)濟(jì)負(fù)荷調(diào)度、工程設(shè)計(jì)和數(shù)據(jù)聚類等各個領(lǐng)域均有涉及，具有十分廣闊的研究前景。與其他算法相比，CS算法的相關(guān)參數(shù)少，并且易于與其他算法相融合，若能針對上述問題展開深入研究，將會極大地促進(jìn)該算法的發(fā)展，未來將在理論分析方面對CS算法做進(jìn)一步的研究。