基于量子進化的天牛須搜索算法*

劉亞奇

（河南工業大學，河南 鄭州 450001）

0 引言

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

本文在總結以上改進方法的基礎上，提出了一種基于量子進化策略的BAS算法（QBAS），把當前最優解認為是“正”“偽”兩種狀態概率的線性疊加，用實數編碼的量子（RCQ）表示當前最優解，然后用量子旋轉門（Quantum Rotation Gate，QRG）更新當前最優解的概率。

1 BAS算法

1.1 數學模型

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

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

式中：rands(·)為隨機函數。

根據兩側觸須的氣味濃度，更新天牛的位置：

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

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

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

1.2 算法流程

BAS算法的具體運算過程如下文所述。

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

步驟2：計算天牛適應度函數值fitness(xt)并存儲當前最優解xbest和fitness(xbest)。

步驟3：隨機生成步長b，根據式（2）進行歸一化處理。

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

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

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

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

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

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

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

2.1 RCQ操作

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

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

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

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

當前最優解被認為是“0”態和“1”態的線性疊加，最優解的量子由RCQ表示為：

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

在量子力學中，量子態可以用波函數ω(x,t)表示。波函數的平方|ω(x,t)|2稱為概率密度，表示量子態在對應時間和位置出現的概率。式（10）表示當前RCQ的觀測值，可以用概率密度求得，概率密度的表達式為：

式中：μi為期望值，用當前最優解表示；σi為方差。σi定義為：

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

2.2 QRG操作

在量子進化算法中，因為量子位編碼下的染色體不是單一狀態，不能進行傳統的選擇、交叉、變異等操作。本文采用QRG[11]作用于量子位上，使其狀態位發生變化，進而改變αi的分布域。對于有n個量子位的個體，第i個量子位的更新情況如下：

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

2.3 QBAS算法流程

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

步驟2：計算天牛適應度函數值fitness(xt)并存儲當前最優解xbest和fitness(xbest)。

步驟3：根據式（9），對當前最優解用實數編碼的量子（RCQ）表示。

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

步驟5：隨機生成步長b，根據式（2）進行歸一化處理。

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

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

步驟8：計算更新位置后的適應度值fitness(xt+1)，存儲當前最優解

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

步驟10：判斷是否滿足迭代終止條件，若是則執行步驟12，否則跳轉至步驟11。

（a）根據式（13），執行量子旋轉門（QRG）操作；

（b）根據式（9），對當前最優解用實數編碼的量子（RCQ）表示；

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

3 仿真實驗與結果分析

3.1 測試函數介紹

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

表1 測試函數的名稱、搜索范圍和全局最優解

本實驗中選取3個指標評價算法的性能：（1）最優值是算法輸出的適應度值中，趨近函數全局最優解的值，反映了算法的尋優能力；（2）平均值是算法多次迭代結束后輸出的適應度值的平均值，反映了算法求解能力的好壞；（3）方差是迭代結束輸出的適應度值與均值之間的方差，能夠反映算法的穩定性。

3.2 算法優越性檢驗

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

表2 測試函數的最優解、平均值和方差

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

圖1 函數F1收斂情況

圖2 函數F2收斂情況

圖3 函數F3收斂情況

圖4 函數F4收斂情況

圖5 函數F5收斂情況

圖6 函數F6收斂情況

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

4 結語

本文在天牛須算法中引入量子進化算法的實數編碼的量子（RCQ）和量子旋轉門（QRG）策略。實驗結果表明，對于9個標準測試函數，基于量子進化的天牛須搜索算法（QBAS）具有更優越的尋優性能，能利用較小的種群和較快的迭代速度獲取最優值。