劉亞奇

（河南工業(yè)大學(xué)，河南 鄭州 450001）

0 引言

群智能算法是模擬生物群體行為規(guī)律的算法，用來解決復(fù)雜的優(yōu)化問題，如蟻群算法[1]、粒子群優(yōu)化算法[2]、麻雀搜索算法[3]等。2017年，Jiang和Li受到天牛覓食和尋偶過程的啟發(fā)，提出了天牛須搜索（Beetle Antennae Search，BAS）算法[4]。該算法不需要函數(shù)的梯度信息就能實(shí)現(xiàn)優(yōu)化，因此復(fù)雜度低，其核心代碼僅有4行。BAS算法一經(jīng)提出就受到了廣泛關(guān)注，同時(shí)對BAS算法的改進(jìn)也是很熱門的研究方向。Lin等人[5]把BAS算法和粒子群優(yōu)化（Partical Swarm Optimization，PSO）算法結(jié)合起來，前期用PSO算法更新粒子的速度和位置，后期用BAS算法進(jìn)行局部的搜索優(yōu)化，取得了比單純采用BAS算法或PSO算法更好的優(yōu)化效果。邵良杉等人[6]提出了一種基于BAS的花朵授粉算法，記為BASFPA。此算法在全局搜索的時(shí)候用BAS算法加快收斂速度，在局部搜索的時(shí)候引入變異策略，加快了收斂速度，提高了搜索的成功率。廖列法等人[7]提出了一種基于二次插值的BAS算法QIBAS，在天牛搜索的過程中引入二次插值更新BAS算法的最優(yōu)適應(yīng)度值，避免陷入局部最優(yōu)。

本文在總結(jié)以上改進(jìn)方法的基礎(chǔ)上，提出了一種基于量子進(jìn)化策略的BAS算法（QBAS），把當(dāng)前最優(yōu)解認(rèn)為是“正”“偽”兩種狀態(tài)概率的線性疊加，用實(shí)數(shù)編碼的量子（RCQ）表示當(dāng)前最優(yōu)解，然后用量子旋轉(zhuǎn)門（Quantum Rotation Gate，QRG）更新當(dāng)前最優(yōu)解的概率。

1 BAS算法

1.1 數(shù)學(xué)模型

BAS算法的數(shù)學(xué)模型如下文所述。在D維空間中，天牛左右須xl和xr的位置表示為：

式中：xt為天牛在t次迭代時(shí)的位置；dt為天牛兩須之間的距離；b為天牛的隨機(jī)朝向。b的計(jì)算方式為：

式中：rands(·)為隨機(jī)函數(shù)。

根據(jù)兩側(cè)觸須的氣味濃度，更新天牛的位置：

式中：δt為步長因子；f(·)為適應(yīng)度函數(shù)；sgn(x)為符號函數(shù)。

更新下一步的搜索范圍和步長：

式中：eta為兩須距離和步長的衰減系數(shù)，通常取0.95。

1.2 算法流程

BAS算法的具體運(yùn)算過程如下文所述。

步驟1：設(shè)置控制參數(shù)，初始化天牛的位置信息xt(t=0,1,2,…,n)。

步驟2：計(jì)算天牛適應(yīng)度函數(shù)值fitness(xt)并存儲當(dāng)前最優(yōu)解xbest和fitness(xbest)。

步驟3：隨機(jī)生成步長b，根據(jù)式（2）進(jìn)行歸一化處理。

步驟4：根據(jù)式（1）計(jì)算天牛的左須xl與右須xr位置。

步驟5：根據(jù)式（3）更新天牛的位置xt+1(t=0,1,2,…,n)。

步驟6：根據(jù)式（4）和式（5），更新搜索范圍δ和步長d；

步驟7：判斷是否滿足迭代終止條件，若是則跳轉(zhuǎn)到步驟8，否則跳轉(zhuǎn)至步驟2。

步驟8：輸出全局最優(yōu)解xbest和fitness(xbest)，結(jié)束。

2 基于量子的天牛須搜索算法

1996年，Narayanan等人[8]將量子理論與進(jìn)化算法相結(jié)合，提出了量子遺傳算法（Quantum-Inspired Genetic Algorithm，QIGA）。2004年，Han等人[9]在此基礎(chǔ)上將此算法擴(kuò)展為量子進(jìn)化算法（Quantum Evolutionary Algorithms，QEA），用 量子位編碼表示染色體（RCQ），在算法后期用QRG完成更新。Chen等人[10]設(shè)計(jì)了一種基于量子進(jìn)化的鴿群算法，經(jīng)過實(shí)驗(yàn)驗(yàn)證其具有優(yōu)越的尋優(yōu)性能。

2.1 RCQ操作

量子進(jìn)化算法是基于量子比特和量子力學(xué)態(tài)疊加的概念，其中量子比特又稱為量子位，是指存儲在量子計(jì)算機(jī)中的最小的信息單位。量子位可以用正態(tài)與偽態(tài)表示，具體表現(xiàn)為“0”態(tài)和“1”態(tài)。量子位狀態(tài)被表示為：

式中：α和β分別為兩種狀態(tài)的線性概率。α和β滿足：

則n個(gè)量子位的染色體形式表示為：

式中：n為算法種群；t為迭代次數(shù)；qjt為染色體。

當(dāng)前最優(yōu)解被認(rèn)為是“0”態(tài)和“1”態(tài)的線性疊加，最優(yōu)解的量子由RCQ表示為：

此時(shí)，天牛的收斂方向重新被觀測后定義為xbest，表達(dá)式為：

在量子力學(xué)中，量子態(tài)可以用波函數(shù)ω(x,t)表示。波函數(shù)的平方|ω(x,t)|2稱為概率密度，表示量子態(tài)在對應(yīng)時(shí)間和位置出現(xiàn)的概率。式（10）表示當(dāng)前RCQ的觀測值，可以用概率密度求得，概率密度的表達(dá)式為：

式中：μi為期望值，用當(dāng)前最優(yōu)解表示；σi為方差。σi定義為：

式中：σi為量子進(jìn)入正確方向的概率；|ψi〉由隨機(jī)得到。

2.2 QRG操作

在量子進(jìn)化算法中，因?yàn)榱孔游痪幋a下的染色體不是單一狀態(tài)，不能進(jìn)行傳統(tǒng)的選擇、交叉、變異等操作。本文采用QRG[11]作用于量子位上，使其狀態(tài)位發(fā)生變化，進(jìn)而改變αi的分布域。對于有n個(gè)量子位的個(gè)體，第i個(gè)量子位的更新情況如下：

式中：Δθ為旋轉(zhuǎn)角度，是與收斂速度有關(guān)的設(shè)計(jì)參數(shù)，等同于定義當(dāng)前最優(yōu)解的收斂速度的步長。為了防止量子位被困在0或1，對α施加一個(gè)約束，使概率αi2(t)收斂于ε或者1-ε，而不是0或者1。本文中，使用QRG策略是為了讓量子位的概率趨近于正確的方向，從而提高了正概率的變異策略。如果迭代后當(dāng)前最優(yōu)解沒有變化，就通過QRG增加α，意味著更有可能是全局最優(yōu)解，讓算法跳出局部最優(yōu)解，避免早熟收斂，否則量子位的概率值就被重置為初始值，以保持對算法欺騙性的警惕，其計(jì)算方式為：

2.3 QBAS算法流程

步驟1：設(shè)置控制參數(shù)，初始化天牛的位置信息xt(t=0,1,2,…,n)。

步驟2：計(jì)算天牛適應(yīng)度函數(shù)值fitness(xt)并存儲當(dāng)前最優(yōu)解xbest和fitness(xbest)。

步驟3：根據(jù)式（9），對當(dāng)前最優(yōu)解用實(shí)數(shù)編碼的量子（RCQ）表示。

步驟4：根據(jù)式（10），重新定義天牛的收斂方向xbest,i。

步驟5：隨機(jī)生成步長b，根據(jù)式（2）進(jìn)行歸一化處理。

步驟6：根據(jù)式（1）計(jì)算天牛的左須xl與右須xr位置。

步驟7：根據(jù)式（3）和式（10），由新的收斂方向更新天牛的位置xt+1(t=0,1,2,…,n)。

步驟8：計(jì)算更新位置后的適應(yīng)度值fitness(xt+1)，存儲當(dāng)前最優(yōu)解

步驟9：根據(jù)式（4）和式（5），更新搜索范圍δ和步長d。

步驟10：判斷是否滿足迭代終止條件，若是則執(zhí)行步驟12，否則跳轉(zhuǎn)至步驟11。

（a）根據(jù)式（13），執(zhí)行量子旋轉(zhuǎn)門（QRG）操作；

（b）根據(jù)式（9），對當(dāng)前最優(yōu)解用實(shí)數(shù)編碼的量子（RCQ）表示；

迭代至t=t+1，返回步驟4。

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

3.1 測試函數(shù)介紹

本文在MATLAB 2018a軟件上進(jìn)行仿真測試，用6組標(biāo)準(zhǔn)測試函數(shù)進(jìn)行對比實(shí)驗(yàn)，測試函數(shù)的名稱、表達(dá)式以及搜索范圍和全局最優(yōu)解，結(jié)果如表1所示。其中，F(xiàn)1、F2和F3是單峰函數(shù)，在其定義域上只有一個(gè)全局最優(yōu)解，可以用來測試算法挖掘群體信息的能力和收斂精度的高低；F4、F5和F6是多峰函數(shù)，意味著函數(shù)擁有多個(gè)局部極值，可以很好地測試算法深度搜索種群以外其他信息的能力和解決復(fù)雜優(yōu)化問題的能力。

表1 測試函數(shù)的名稱、搜索范圍和全局最優(yōu)解

本實(shí)驗(yàn)中選取3個(gè)指標(biāo)評價(jià)算法的性能：（1）最優(yōu)值是算法輸出的適應(yīng)度值中，趨近函數(shù)全局最優(yōu)解的值，反映了算法的尋優(yōu)能力；（2）平均值是算法多次迭代結(jié)束后輸出的適應(yīng)度值的平均值，反映了算法求解能力的好壞；（3）方差是迭代結(jié)束輸出的適應(yīng)度值與均值之間的方差，能夠反映算法的穩(wěn)定性。

3.2 算法優(yōu)越性檢驗(yàn)

本文將QBAS算法與PSO[2]和遺傳算法（Genetic Algorithm，GA）做對比測試。把3個(gè)算法的參數(shù)設(shè)置成一樣，最大迭代次數(shù)為100，種群個(gè)數(shù)為10，搜索空間維度為30，QBAS算法的步長衰減系數(shù)eta為0.95，步長δ為10。PSO算法的學(xué)習(xí)因子設(shè)置為c1=c2=1.5，慣性權(quán)重ω為0.8。GA算法的交叉算子CR設(shè)置為0.1，變異算子F設(shè)置為0.4。對每個(gè)測試函數(shù)各運(yùn)行30次，記錄輸出的適應(yīng)度值，同樣取3個(gè)指標(biāo)列成表格，如表2所示。

表2 測試函數(shù)的最優(yōu)解、平均值和方差

為了更加直觀地比較QBAS與其他兩種優(yōu)化算法的尋優(yōu)性能，本文將各算法的收斂曲線用電腦軟件MATLAB 2018a進(jìn)行仿真，結(jié)果分別如圖1、圖2、圖3、圖4、圖5和圖6所示。

圖1 函數(shù)F1收斂情況

圖2 函數(shù)F2收斂情況

圖3 函數(shù)F3收斂情況

圖4 函數(shù)F4收斂情況

圖5 函數(shù)F5收斂情況

圖6 函數(shù)F6收斂情況

對F1、F2和F3這3個(gè)單峰函數(shù)求解可知，除函數(shù)F1外，QBAS算法輸出的最優(yōu)值更加趨近于函數(shù)的實(shí)際全局最優(yōu)值，尤其是對函數(shù)F3的求解中，PSO算法和GA算法從運(yùn)算的一開始就陷入了局部最優(yōu)值，并且無法跳出來。對函數(shù)F1的求解中，由均值和方差兩個(gè)指標(biāo)可知QBAS算法的穩(wěn)定性更強(qiáng)。由函數(shù)F1、F2和F3的收斂圖可知，QBAS算法的收斂速度更快，基本不會陷入局部最優(yōu)，獲得最優(yōu)解的迭代次數(shù)也較少，運(yùn)算速度更快。對F4、F5和F6這3個(gè)多峰函數(shù)求解可知，QBAS算法輸出的最優(yōu)值均更加趨近于函數(shù)的實(shí)際全局最優(yōu)值，尤其求解函數(shù)F4和F6的輸出適應(yīng)度值均等于函數(shù)實(shí)際全局最優(yōu)值。由此可見相比單峰函數(shù)，QBAS算法對多峰函數(shù)的尋優(yōu)性能更加優(yōu)越。

4 結(jié)語

本文在天牛須算法中引入量子進(jìn)化算法的實(shí)數(shù)編碼的量子（RCQ）和量子旋轉(zhuǎn)門（QRG）策略。實(shí)驗(yàn)結(jié)果表明，對于9個(gè)標(biāo)準(zhǔn)測試函數(shù)，基于量子進(jìn)化的天牛須搜索算法（QBAS）具有更優(yōu)越的尋優(yōu)性能，能利用較小的種群和較快的迭代速度獲取最優(yōu)值。