曲寶,李薈
(東北石油大學(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)化精度有較為明顯的提升。
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è)體。
根據(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)系。
在群智能算法和進(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è)量子位為:
其中Pauli 矩陣如下:
量子比特經(jīng)投影測(cè)量后包含3 個(gè)數(shù)值,染色體包含3 條基因鏈,經(jīng)解空間變換可分別代表3 組解,因此擴(kuò)大算法的遍歷范圍。設(shè)第j 維變量取值范圍為[min(j),max(j)],解空間變換如下:
由于量子比特有兩個(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)化效率。
量子比特在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)角幅度大小。
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)選擇。
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。
為驗(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ì)比。
對(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ù)相同。
實(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 的因素。
量子計(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)化能力均有一定程度的提高。
黑龍江八一農(nóng)墾大學(xué)學(xué)報(bào)2021年4期