一種新的量子行為衍生布谷鳥(niǎo)搜索算法

曲寶，李薈

（東北石油大學(xué)，大慶 163318）

布谷鳥(niǎo)搜索（Cuckoo Search，CS）作為一種群智能算法，目前已成為國(guó)內(nèi)外的研究熱點(diǎn)，最早是在2009 年由Yang 等[1]提出，主要通過(guò)計(jì)算機(jī)和數(shù)學(xué)模型模擬布谷鳥(niǎo)對(duì)幼鳥(niǎo)育雛時(shí)的自身特殊習(xí)性，同時(shí)仿照了鳥(niǎo)類的萊維飛行（Lévy flights）特性。該算法在數(shù)學(xué)模型描述過(guò)程中具有簡(jiǎn)單、參數(shù)較少的特點(diǎn)，并且非線性優(yōu)化時(shí)的性能略高于一些常見(jiàn)的群智能算法[2-3]。因此，國(guó)內(nèi)外很多學(xué)者將其應(yīng)用于工程設(shè)計(jì)[4-5]、神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)[6]、目標(biāo)非線性優(yōu)化[7]等問(wèn)題。Lévy flights 屬于隨機(jī)游走模式，步長(zhǎng)滿足一個(gè)重尾的穩(wěn)定概率分布。布谷鳥(niǎo)搜索算法采用小步長(zhǎng)和大步長(zhǎng)交替進(jìn)行，最終實(shí)現(xiàn)隨機(jī)游走的變量?jī)?yōu)化，完成算法收斂。Lévy flights 使得算法在早期尋優(yōu)階段可以確保種群的多樣性，并增大變量空間的搜索范圍；在后期，通過(guò)利用較大的步長(zhǎng)確保算法能夠逐漸收斂，完成全局最優(yōu)解的計(jì)算。同時(shí)，通過(guò)Biased 隨機(jī)走動(dòng)輔助萊維飛行，有效完成全局與局部的優(yōu)化計(jì)算和搜索平衡。很多學(xué)者對(duì)于布谷鳥(niǎo)搜索算法的研究，目前主要集中在自身算子的研究和算法融合兩個(gè)方面，其中第一個(gè)方面包括Lévy flights[8]、Biased 隨機(jī)走動(dòng)[9]、逐維改進(jìn)機(jī)制[10]、動(dòng)態(tài)自適應(yīng)發(fā)現(xiàn)[11-14]等。在算法融合研究方面，國(guó)內(nèi)外的研究通過(guò)將布谷鳥(niǎo)搜索算法與其他群智能算法融合，文獻(xiàn)[15-17]分別提出將該算法與粒子群、差分進(jìn)化進(jìn)行算子融合，改善算法的個(gè)體尋優(yōu)策略，避免陷入局部最優(yōu)。以上這些均較好的提升了CS 算法的收斂速度或求解質(zhì)量。

量子計(jì)算是目前國(guó)內(nèi)外廣泛關(guān)注的一種先進(jìn)計(jì)算理論，該理論應(yīng)用到優(yōu)化領(lǐng)域過(guò)程中，常將個(gè)體的實(shí)數(shù)或二進(jìn)制編碼采用量子比特表示，已被證明量子優(yōu)化算法在種群的多樣性和算法精度方面具有更強(qiáng)的優(yōu)勢(shì)[18]。文獻(xiàn)[19]提出BQGA 算法，使用Bloch 球坐標(biāo)實(shí)現(xiàn)三鏈編碼，量子位具有兩個(gè)轉(zhuǎn)角參數(shù)，尋優(yōu)能力優(yōu)于其他基于單位圓的QEA 算法，但個(gè)體更新時(shí)未解決轉(zhuǎn)角的協(xié)調(diào)問(wèn)題，影響優(yōu)化性能。文獻(xiàn)[20]在此基礎(chǔ)上提出QBEA 算法，引入量子計(jì)算理論，在Bloch 球面完成最短路徑旋轉(zhuǎn)，有效解決轉(zhuǎn)角更新的調(diào)整量匹配問(wèn)題，但存在以下問(wèn)題：（1）進(jìn)化算子中，所有個(gè)體的旋轉(zhuǎn)幅角均采用的隨機(jī)方式，有一定盲目性，未充分發(fā)揮最優(yōu)個(gè)體的路標(biāo)引導(dǎo)作用，進(jìn)化速度較慢；（2）變異算子僅考慮多樣性，未進(jìn)行貪婪擇優(yōu)，個(gè)體進(jìn)化經(jīng)驗(yàn)丟失。

在之前研究的基礎(chǔ)上，受布谷鳥(niǎo)搜索啟發(fā)，提出一種量子行為衍生布谷鳥(niǎo)算法（Quantum-behaved Inspired Cuckoo Search，QBICS）。QBICS 采用Logistic混沌映射產(chǎn)生初始種群，使種群具有較好的多樣性。根據(jù)量子計(jì)算理論，量子染色體使用Bloch 球面坐標(biāo)描述，在更新時(shí)繞軸旋轉(zhuǎn)，同時(shí)更新兩個(gè)轉(zhuǎn)角。全局搜索方面，使用當(dāng)代最優(yōu)解指導(dǎo)種群進(jìn)化，根據(jù)萊維飛行計(jì)算量子比特逼近目標(biāo)的旋轉(zhuǎn)幅角。通過(guò)投影測(cè)量和解空間變化計(jì)算適應(yīng)度，并進(jìn)行貪婪擇優(yōu)。局部搜索方面，使用Biased 隨機(jī)走動(dòng)和差分項(xiàng)引入新個(gè)體，替換較差解。通過(guò)對(duì)全局最優(yōu)解的Bloch 球面分布的證明，搜索范圍縮小為Bloch 球面的半球搜索。在仿真實(shí)驗(yàn)中，通過(guò)四種常見(jiàn)的標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行多種算法的非線性優(yōu)化對(duì)比，實(shí)驗(yàn)結(jié)果證明，所提的QBICS 的尋優(yōu)能力和優(yōu)化精度有較為明顯的提升。

1 標(biāo)準(zhǔn)布谷鳥(niǎo)算法

CS 中使用鳥(niǎo)巢代表求解問(wèn)題的優(yōu)化解，每次進(jìn)化主要包括兩個(gè)步驟：首先對(duì)當(dāng)前解使用萊維飛行向最優(yōu)解逼近，產(chǎn)生新鳥(niǎo)巢位置，并對(duì)二者貪婪擇優(yōu)；然后按照發(fā)現(xiàn)概率丟棄較差解，使用Biased 隨機(jī)走動(dòng)和差分項(xiàng)生成與丟棄數(shù)量相同的新解。

（1）萊維飛行隨機(jī)走動(dòng)

設(shè)Xg，i=（xi1，xi2，…，xm）為第g 代中第i 個(gè)鳥(niǎo)巢位置，得到的新鳥(niǎo)巢為：

其中，α 是步長(zhǎng)，表示萊維飛行的搜索范圍控制，利用尋優(yōu)解與最優(yōu)解的距離來(lái)完成，具體過(guò)程如下：

其中，α0為常數(shù)，Xbest為當(dāng)前最優(yōu)解。

式（1）中，⊕是點(diǎn)乘積，Leνy（β）是服從Lévy 概率分布的隨機(jī)數(shù)。

（2）Biased 隨機(jī)走動(dòng)

在當(dāng)代種群中隨機(jī)選擇兩個(gè)不同的個(gè)體，按下式生成新解。

其中，r 是縮放因子，是（0，1）之間的隨機(jī)數(shù)，Xg，j和Xg，k是隨機(jī)選擇的兩個(gè)個(gè)體。

2 量子衍生布谷鳥(niǎo)算法QBICS

2.1 Bloch 球面編碼

根據(jù)量子疊加原理，在二維復(fù)希爾伯特空間中，一個(gè)量子比特可描述為：

量子染色體表示待優(yōu)化問(wèn)題可行解，在QBICS中即為鳥(niǎo)窩位置。設(shè)種群規(guī)模為m，優(yōu)化空間維數(shù)為D，第i 條量子染色體的編碼方法如下：

在三維笛卡爾坐標(biāo)系表示的Bloch 球面上，根據(jù)轉(zhuǎn)角θ 和φ，可確定一個(gè)Bloch 球面點(diǎn)坐標(biāo)p（x，y，z）=（cosφsinθ，sinφsinθ，cosθ），因此可用Bloch 球面上的點(diǎn)來(lái)描述量子比特，球面點(diǎn)和存在對(duì)應(yīng)關(guān)系。

2.2 QBICS 的初始種群混沌初始化

在群智能算法和進(jìn)化算法中，種群的初始多樣性，即個(gè)體的搜索空間分布，對(duì)于算法的進(jìn)化搜索過(guò)程中極為重要?；煦绗F(xiàn)象具有明顯的隨機(jī)特性，在自然界中普遍存在。在所提算法中，QBICS 采用了混沌理論中的具有蟲(chóng)口特性的Logistic 混沌映射方式，具體計(jì)算過(guò)程如下：

其中，uj=4 時(shí)進(jìn)入混沌狀態(tài)。種群初始化時(shí)首先隨機(jī)生成D 個(gè)實(shí)數(shù)向量σ1=［σ11，σ12，…，σ1D］，σ1i∈（0，1）。令θij=σijπ，φij=σij2π，按式（7）產(chǎn)生第1 條量子染色體。再按式（9）依次生成m-1 組向量，同理產(chǎn)生其余m-1 條染色體。此時(shí)，種群中第2 條染色體的第1 個(gè)量子位為：

2.3 投影測(cè)量和解空間變換

其中Pauli 矩陣如下：

量子比特經(jīng)投影測(cè)量后包含3 個(gè)數(shù)值，染色體包含3 條基因鏈，經(jīng)解空間變換可分別代表3 組解，因此擴(kuò)大算法的遍歷范圍。設(shè)第j 維變量取值范圍為［min（j），max（j）］，解空間變換如下：

2.4 量子比特繞軸旋轉(zhuǎn)

由于量子比特有兩個(gè)轉(zhuǎn)角，為避免兩個(gè)轉(zhuǎn)角分別進(jìn)化，導(dǎo)致二者無(wú)法協(xié)同影響算法搜索效率的問(wèn)題，QBICS 算法在Bloch 球面上建立搜索了機(jī)制，通過(guò)繞旋轉(zhuǎn)軸旋轉(zhuǎn)完成量子比特的θ 和φ 同時(shí)進(jìn)化，通過(guò)量子位的投影測(cè)量直接得到Bloch 球面坐標(biāo)，所經(jīng)過(guò)的路徑為Bloch 球大圓上的劣弧，實(shí)現(xiàn)兩個(gè)參數(shù)調(diào)整量的最佳匹配，從而保證兩個(gè)轉(zhuǎn)角的調(diào)整具有更高的優(yōu)化效率。

2.5 QBICS 的萊維飛行個(gè)體進(jìn)化策略

量子比特在Bloch 球上繞軸旋轉(zhuǎn)角度大小對(duì)算法性能較為重要，此外搜索區(qū)域?qū)λ惴ǖ倪M(jìn)化效率也有一定影響。所提的QBICS 搜索范圍可定義到Bloch 的上半球，減小球面搜索范圍，提高搜索效率。因此QBICS 的Bloch 球面搜索范圍限定如下：

萊維飛行是一種服從Lévy 分布的隨機(jī)走動(dòng)策略，行走方式為短距離搜索和偶爾長(zhǎng)距離搜索相間隔。對(duì)于進(jìn)化過(guò)程，使用萊維飛行可有效增加種群多樣性，搜索范圍可以擴(kuò)大，易跳出局部極值[1]。量子個(gè)體更新策略引入萊維飛行隨機(jī)走動(dòng)，確定量子比特向目標(biāo)逼近時(shí)的Bloch 球面轉(zhuǎn)角幅度大小。

2.6 QBICS 的交叉變異策略

QBICS 算法的交叉變異策略仍采用Biased 隨機(jī)走動(dòng)方式計(jì)算，優(yōu)化過(guò)程中根據(jù)種群的多樣性和退化程度，自適應(yīng)計(jì)算發(fā)現(xiàn)概率。初始化種群采用Logistic 混沌映射產(chǎn)生，具有較好的多樣性，所有個(gè)體較為均勻的分布在Bloch 球面上，應(yīng)減小丟棄較差個(gè)體的發(fā)現(xiàn)概率。此時(shí)進(jìn)行交叉變異，勢(shì)必會(huì)浪費(fèi)一定的目標(biāo)函數(shù)評(píng)價(jià)次數(shù)。當(dāng)種群多樣性降低時(shí)，為避免優(yōu)化過(guò)程陷入局部，QBICS 增大發(fā)現(xiàn)概率，確保新個(gè)體的生成，從而提高種群多樣性。

定義1 記種群在t 代的適應(yīng)度為fit（t），歷史平均適應(yīng)度，則認(rèn)為種群發(fā)生退化。

發(fā)現(xiàn)概率κc與種群的退化程度的關(guān)系如下：

若κc（0）=0.01，種群發(fā)生退化時(shí)的發(fā)現(xiàn)概率為單調(diào)遞增且κc（t+1）∈［0.05，0.1］。

其中，λ 為縮放因子。計(jì)算pi（t）和pb（t）的旋轉(zhuǎn)軸Raxis（i，b），根據(jù)式（20）計(jì)算pi（t）各量子比特的旋轉(zhuǎn)角度，按式（14）將pi（t）繞軸Raxis（i，b）旋轉(zhuǎn)，旋轉(zhuǎn)后生成的新量子染色體為。最后按式（18）進(jìn)行p（it）和的擇優(yōu)選擇。

2.7 QBICS 的算法步驟

Step1 設(shè)置算法參數(shù)，包括種群規(guī)模n、量子編碼長(zhǎng)度D、Lévy flights 步長(zhǎng)α0、發(fā)現(xiàn)概率初值κc（0）、迭代次數(shù)G；

Step2 t←0，根據(jù)Logistic 映射隨機(jī)初始種群；

Step3 計(jì)算適應(yīng)度。按式（10）、（11）進(jìn)行量子位測(cè)量、投影和解空間變換，計(jì)算量子染色體適應(yīng)度；

Step4 存儲(chǔ)當(dāng)代種群中的最優(yōu)個(gè)體，并替換之前記錄的全局最優(yōu)個(gè)體，計(jì)算當(dāng)代平均適應(yīng)度f(wàn)it（t）和歷史平均適應(yīng)度

Step5 個(gè)體萊維飛行進(jìn)化。按式（17）計(jì)算旋轉(zhuǎn)幅角，個(gè)體繞軸旋轉(zhuǎn)產(chǎn)生新個(gè)體，通過(guò)貪婪策略擇優(yōu)；

Step6 按式（19）計(jì)算發(fā)現(xiàn)概率并丟棄較差解，按式（18）計(jì)算轉(zhuǎn)角，生成與丟棄解數(shù)量相同的新個(gè)體，并貪婪擇優(yōu)；

Step7 t←t+1。若t≥G 或者達(dá)到計(jì)算精度，存儲(chǔ)最優(yōu)解，算法計(jì)算完。否則轉(zhuǎn)Step3。

3 仿真實(shí)驗(yàn)

為驗(yàn)證所提算法的性能，采用標(biāo)準(zhǔn)的函數(shù)極值優(yōu)化問(wèn)題，并與標(biāo)準(zhǔn)的布谷鳥(niǎo)算法[1]（Standard Cuckoo Search，SCS）、Bloch 量子遺傳算法BQGA[19]、Bloch 量子行為進(jìn)化算法QBEA[20]進(jìn)行對(duì)比。

3.1 測(cè)試函數(shù)

3.2 參數(shù)設(shè)置

對(duì)于前兩個(gè)二維函數(shù)，4 種算法的種群規(guī)模m=20，最大迭代步數(shù)G=500，其中SCS 和QBICS 的α0=0.01、κc（0）=0.02。對(duì)比算法QIEA 的轉(zhuǎn)角步長(zhǎng)δ=0.01π、變異概率pm=0.05，對(duì)比算法BQGA 的轉(zhuǎn)角初值Δθ0=Δφ0=0.02π。對(duì)于后兩個(gè)高維函數(shù)，變量維數(shù)D=50，4種算法的種群規(guī)模m=30，最大迭代步數(shù)G=5 000，其他參數(shù)與前兩個(gè)函數(shù)相同。

3.3 實(shí)驗(yàn)對(duì)比分析

實(shí)驗(yàn)環(huán)境：Matlab R2012a、CPU：i7-3770 3.4 GHz，內(nèi)存4 G、win7-64。仿真實(shí)驗(yàn)過(guò)程中，為保證實(shí)驗(yàn)結(jié)果記錄的客觀性，實(shí)驗(yàn)對(duì)比的四種算法在相同實(shí)驗(yàn)環(huán)境下獨(dú)立運(yùn)行50 次。每次運(yùn)行結(jié)束后，分別記錄各個(gè)實(shí)驗(yàn)對(duì)比指標(biāo)。其中，對(duì)于四種算法在函數(shù)f1～f4極值優(yōu)化時(shí)的單步迭代運(yùn)行時(shí)間見(jiàn)表1，收斂能力對(duì)比，包括收斂次數(shù)、平均步數(shù)、平均結(jié)果和標(biāo)準(zhǔn)偏差，請(qǐng)見(jiàn)表2～表5。

表1 單次迭代的平均時(shí)間對(duì)比Table 1 Average time comparison of each iteration

表2 函數(shù)f1 優(yōu)化結(jié)果對(duì)比Table 2 Comparison of function f1 optimization results

表3 函數(shù)f2 優(yōu)化結(jié)果對(duì)比Table 3 Comparison of function f2 optimization results

表4 函數(shù)f3 優(yōu)化結(jié)果對(duì)比Table 4 Comparison of function f3 optimization results

表5 函數(shù)f4 優(yōu)化結(jié)果對(duì)比Table 5 Comparison of function f4 optimization results

從表1 可以看出，單步迭代時(shí)間從長(zhǎng)到短分別是QBICS、QBEA、BQGA、SCS。原因如下：（1）QBICS和QBEA 在每次迭代過(guò)程中，都需要對(duì)量子比特做投影測(cè)量、計(jì)算旋轉(zhuǎn)矩陣和繞軸旋轉(zhuǎn)操作，增加了算法的計(jì)算量。此外QBICS 和QBEA 幾乎一致，原因在于：QBICS 增加的旋轉(zhuǎn)幅角計(jì)算、種群退化程度這兩個(gè)算子沒(méi)有復(fù)雜操作，可忽略不計(jì)。QBICS 萊維飛行產(chǎn)生新解后的貪婪擇優(yōu)與QBEA 的任一個(gè)體隨機(jī)旋轉(zhuǎn)后的適應(yīng)度計(jì)算的復(fù)雜度也是一致的。QBICS 僅是在交叉變異后，對(duì)變異個(gè)體需要重新投影測(cè)量，但數(shù)量少，并不耗時(shí)；（2）BQGA 與QBICS 相同，在Bloch 球面上也分別對(duì)應(yīng)三個(gè)坐標(biāo)，采用三鏈編碼結(jié)構(gòu)，但是染色體進(jìn)化操作時(shí)不需要投影測(cè)量、繞軸旋轉(zhuǎn)操作，更新過(guò)程相對(duì)簡(jiǎn)單，因此時(shí)間較短；（3）SCS是4 種算法中編碼結(jié)構(gòu)、個(gè)體更新最為簡(jiǎn)單的，染色體是單鏈結(jié)構(gòu)，只有萊維飛行、Biased 隨機(jī)擾動(dòng)和貪婪擇優(yōu)，無(wú)需量子比特的Pauli 矩陣投影測(cè)量、繞軸旋轉(zhuǎn)等復(fù)雜操作，因此單步迭代時(shí)間最短。

從表2 到表5 可以看出，算法的優(yōu)化能力從高到低分別是QBICS、QBEA、BQGA、SCS。原因如下：

（1）QBICS、QBEA 和BQGA 三種算法都是Bloch 球面的三鏈結(jié)構(gòu)，每條染色體一次進(jìn)化都可以完成三個(gè)可行解的同時(shí)尋優(yōu)，這無(wú)疑擴(kuò)大了解空間的搜索遍歷，獲得問(wèn)題最優(yōu)解的概率得到提高，因此三種算法的收斂能力均高于SCS；

（2）QBICS 和QBEA 的進(jìn)化效率高于BQGA，主要原因在于二者都是根據(jù)量子計(jì)算理論，通過(guò)繞軸旋轉(zhuǎn)完成兩個(gè)轉(zhuǎn)角的協(xié)調(diào)更新和最佳匹配，向目標(biāo)比特逼近時(shí)沿最短的Bloch 劣弧進(jìn)行操作；

（3）比較QBICS 和QBEA：①繞軸旋轉(zhuǎn)的幅角大小對(duì)于算法的進(jìn)化速度和收斂至關(guān)重要。QBEA 采用的策略是δ∈［-0.05 π，0.05 π］的小距離隨機(jī)旋轉(zhuǎn)模式，QBICS 引入萊維飛行，在向目標(biāo)比特逼近時(shí)，采用多次短距離探索和偶爾長(zhǎng)距離行走的旋轉(zhuǎn)模式，因此能夠擴(kuò)大搜索范圍，更易跳出局部極值，因此收斂能力高于QBEA，可在更短的迭代步驟內(nèi)完成收斂。②變異算子：QBICS 是利用Biased 隨機(jī)走動(dòng)和差分項(xiàng)對(duì)較差的個(gè)體進(jìn)行變異，計(jì)算繞軸旋轉(zhuǎn)角度時(shí)，除隨機(jī)選擇的個(gè)體外，還增加了與最優(yōu)個(gè)體的夾角，并且根據(jù)貪婪策略進(jìn)行擇優(yōu)，此策略可以在增加多樣性的同時(shí)，在一定程度上增加了產(chǎn)生最優(yōu)解的可能性，QBEA 僅為增加種群多樣性使用Hadamard 門變異，變異后未進(jìn)行貪婪擇優(yōu)，這勢(shì)必可能會(huì)導(dǎo)致向種群引入更差的個(gè)體，個(gè)體前期的進(jìn)化經(jīng)驗(yàn)丟失，浪費(fèi)一定的目標(biāo)函數(shù)評(píng)價(jià)次數(shù)，此外，QBICS 變異概率是隨種群進(jìn)化程度動(dòng)態(tài)調(diào)節(jié)的，對(duì)于保持種群多樣性效果略優(yōu)一些。③萊維飛行、Biased 偏好隨機(jī)走動(dòng)和貪婪擇優(yōu)實(shí)現(xiàn)了QBICS 的全局搜索和局部搜索之間的平衡，這一點(diǎn)是QBEA 所不具備的。此外，QBICS在搜索時(shí)減小了Bloch 球面搜索范圍，引入Logistic混沌映射使得初始種群空間分布性較好，這兩點(diǎn)也是QBICS 進(jìn)化效率高于QBEA 的因素。

4 結(jié)論

量子計(jì)算與群智能算法的融合是目前的一個(gè)研究熱點(diǎn)，受到國(guó)內(nèi)外的關(guān)注。根據(jù)量子計(jì)算理論，提出一種量子行為衍生布谷鳥(niǎo)搜索算法。通過(guò)Bloch 球面描述的量子比特進(jìn)行個(gè)體編碼，表示當(dāng)前鳥(niǎo)窩位置，通過(guò)投影、測(cè)量、繞軸旋轉(zhuǎn)完成個(gè)體進(jìn)化。QBICS提出采用萊維飛行確定量子比特的旋轉(zhuǎn)角度，搜索范圍限定到Bloch 半球以內(nèi)，此外根據(jù)種群退化程度提出自適應(yīng)的發(fā)現(xiàn)概率。結(jié)果表明，對(duì)現(xiàn)有的布谷鳥(niǎo)算法和量子行為進(jìn)化算法的優(yōu)化能力均有一定程度的提高。