基于自尋優和交叉尋優的量子優化算法

曹茂俊，尤文菁，盧玉瑩

(東北石油大學 計算機與信息技術學院，黑龍江 大慶 163318)

0 引 言

啟發式算法常常用來解決某些難以得到精確解的優化問題，根據搜索過程中所依賴的解的數量，啟發式算法可分為單解和群解兩類。常見的單解啟發式算法有模擬退火算法[1]、禁忌搜索算法[2]等，而群解啟發式算法的代表有差分進化算法[3]、遺傳算法[4]、布谷鳥搜索算法[5]等。就搜索特性而言，單解和群解算法在開發和探索上各有優劣。自從20世紀80年代Feynman[6]首次提出利用量子計算模擬量子力學過程的思想[7]，Deutsch提出構建通用量子計算機的可行性[8]，人們開始關注如何利用量子特性來解決傳統計算機難以解決的問題，而量子計算也逐漸出現了量子算法和量子衍生技術這兩個不同的發展方向。而將量子特性引入啟發式算法，就出現了許多量子優化算法，如量子遺傳算法[9]、量子粒子群優化算法[10]等。

目前許多啟發式算法優化效率低、容易陷入局部最優值、高維優化效果差，對于一些群解算法，還存在著進化時不對種群個體作區分、不考慮個體差異性等問題。而在量子態的描述方式上，多數算法也只在平面單位圓上描述量子態[11-13]，削弱了量子計算的特性。對此，在利用Bloch球面來對量子態進行描述和變換的前提下，提出一種群解算法。針對種群的最優個體和普通個體分別提出優化策略，對于最優個體采用單解啟發算法中渦流搜索算法的自優化策略，對于普通個體則采用群解啟發算法中差分進化的交叉策略，即最優個體自尋優策略和普通個體交叉尋優策略。兩種尋優策略有機融合可構成一種全新的量子衍生優化模型，基于自尋優和交叉尋優的量子優化算法(quantum optimization algorithms based on self-optimization and cross-optimization，QOA-SAC)。通過函數極值優化問題進行仿真，并通過與普通遺傳算法(common genetic algorithm，CGA)、簡單量子遺傳算法(simple quantum genetic algorithm，SQGA)和人工魚群算法(artificial fish swarms algorithm，AFSA)對比，驗證了QOA-SAC的有效性。

1 基于量子比特的個體編碼和解碼

1.1 量子個體編碼

在量子計算中，一個量子比特是一個可以在二維復希爾伯特空間中描述的兩能級量子體系，根據量子疊加原理，量子比特的任何狀態都可以寫成：

|φ〉=cos(θ/2)|0〉+eiφsin(θ/2)|1〉

(1)

量子比特可以借助Bloch球面描述，該球為量子比特及其變換提供了幾何圖像，具體而言，量子比特可以用嵌入三維笛卡爾坐標系中的Bloch球面上的一個點來描述。

1.2 解空間變換

為了減少計算量，提高優化效率，設Xi=[xi1,xi2,…,xin]為問題可行解，其中xij∈[-1,1]，按下式將xij變換為實際優化空間[Minj,Maxj]中的解Xij。

(2)

2 算法設計與實現

2.1 最優個體的自尋優策略

對于最優個體上的所有量子比特，分別確定旋轉軸、計算旋轉角度、實施旋轉操作，所有量子比特都被旋轉之后，即可生成一個新個體，重復上述操作，即可生成多個新個體。將這些新個體進行解碼、計算目標函數值之后，利用貪婪選擇策略即可實現當代最優個體的更新。

2.1.1 旋轉軸的確定方法

若在Bloch球面上隨機選擇旋轉軸，不僅會顯著增加模型的復雜度，而且當選擇的軸與x軸夾角較小時，還會嚴重降低優化效率。所以在旋轉時要根據量子比特在Bloch球面上的具體位置選擇y軸或z軸作為旋轉軸。

2.1.2 旋轉角度的確定方法

在確定了量子比特旋轉軸之后，還需要確定旋轉角度。由于自尋優策略中量子比特的“移動”沒有確定的目標位置，所以無法根據目標位置確定轉角步長。此時對于最優個體上的所有量子比特，其轉角步長的確定可以設計一個不依賴于目標位置的統一原則。考慮到最優個體的量子比特在Bloch球面上移動的隨機性，轉角方向應該可正可負，又考慮到當前個體的最優性，小步長的探索次數應該多于大步長的探索次數。在QOA-SAC中，旋轉角度擬采用中心為0標準差逐代縮小的高斯分布隨機產生。對于最優個體上第j個量子比特|φj〉，其旋轉角度的計算式如公式(3)所示。

δj(t)=σj(t)×randn

(3)

式中，randn為服從N(0,1)分布的正態隨機數，t為迭代步數。

下面給出標準差σj(t)的計算方法。在算法執行的開始階段，尋優偏重于全局探索，旋轉角度應相對較大，而在后期階段則偏重于局部開發，旋轉角度應相對較小。為實現探索和開發兩階段的平衡，QOA-SAC擬采用使旋轉角度的標準差σj(t)隨迭代步數逐代減小的策略，具體可采用逆不完全伽馬函數實現σj(t)的計算。

設λ=0.1，a=t/MaxItr，其中MaxItr為限定迭代步數，此時逆不完全伽馬函數具有這樣一個優良特性：在迭代步數的前一半，接近線性下降，而在后一半，接近指數下降[14]，如圖1所示。用這樣的函數來動態調整最優解量子比特的轉角標準差σj(t)，能夠較好地實現探索與開發兩階段之間的平衡，進而有效避免早熟收斂。根據以上思路，最優個體量子比特旋轉角度的標準差σj(t)可按公式(4)計算。

圖1 逆不完全伽馬函數在λ=0.1，限定步數取100和10 000時的特性

σj(t)=σj(0)(1/λ)gammaincinv(λ,1-t/MaxItr)

(4)

式中，σj(0)為標準差初值。利用(公式3、4)，即可獲得最優個體量子比特的旋轉角度δj(t)。

2.1.3 最優個體自尋優策略的具體實現

確定了旋轉軸和旋轉角度之后，即可對|φj〉實施旋轉操作，繞y軸和繞z軸旋轉的旋轉矩陣分別如公式(5)和公式(6)所示。

(5)

(6)

2.2 普通個體的交叉尋優策略

對于種群中的當前個體，首先通過其他個體的隨機交叉確定目標位置，然后使當前個體的量子比特在Bloch球面上繞著某一旋轉軸，向著目標位置的量子比特旋轉，即可生成一個新個體，在當前個體和新個體之間通過貪婪選擇，即可實現當前普通個體的交叉尋優。

2.2.1 普通個體尋優中多種交叉策略的設計

表1 QOA-SAC擬采用的交叉策略

2.2.2 目標位置的確定方法

關于目標位置的確定，令當前個體某個量子比特在Bloch球面上的對應點為P0，Bloch坐標為(x0,y0,z0)，應用交叉策略確定的目標位置的橫坐標為x。過點(x,0,0)作與x軸垂直的圓周C，記平面XOP0與圓周C的交點為P和M，且點P的坐標(x,y,z)與P0的坐標(x0,y0,z0)同號。對于圓周C上的任意一點P1，由于平面XOP0垂直于圓周C，顯然有路徑P0P的長度小于路徑P0P1的長度，所以，點P即為P0希望逼近的目標位置，目標位置P的縱坐標y和豎坐標z可按公式(7)計算。

至此，普通個體尋優中當前個體的目標位置得以完全確定。

2.2.3 旋轉角度的確定方法

δij=arccos(xx0+yy0+zz0)(1+randn/3)

(8)

這種確定旋轉角度的方法，是先使|φij〉從P0旋轉到P，然后再從P點開始旋轉一個服從N(0,arccos(xx0+yy0+zz0)/3)分布的隨機轉角。

2.2.4 旋轉軸的確定方法

根據量子計算原理，使量子比特|φij〉在Bloch球面上繞一個沿單位矢量n=[nx,ny,nz]的軸轉動δ弧度的旋轉矩陣如公式(9)所示。

(9)

式中，I為單位矩陣，σx、σy、σz為泡利矩陣。

根據此公式，即可導出將當前量子比特|φij〉從P0向著P旋轉的旋轉矩陣，如公式(10)所示。

(10)

2.3 基于自尋優和交叉尋優的量子遺傳算法

自尋優策略，就是個體不與種群中任何其他個體交互，完全根據自身特征更新自己，研究最優個體的量子衍生自尋優方法，可以最大限度地發揮最優個體的潛能。

交叉尋優策略則針對普通個體，隨機目標的選擇有利于增強種群中個體的多樣性，避免因過分依賴最優個體而早熟收斂。

將以上兩種尋優策略有機融合可構成一種全新的量子衍生優化模型，即基于自尋優和交叉尋優的量子優化算法(quantum optimization algorithms based on self-optimization and cross-optimization，QOA-SAC)。

設種群規模為N1，最優解自尋優時生成新個體數為N2，優化空間為D維。首先實施種群編碼，解碼，計算目標函數值，記錄當前最優解。記最優解的量子比特描述為[|φb1〉,|φb2〉,…,|φbD〉]，Bloch橫坐標為[xb1,xb2,…,xbD]，最優目標函數值為Fbest。在每一步迭代中，首先進行最優個體的自尋優。具體為：通過將[|φb1〉,|φb2〉,…,|φbD〉]的所有量子比特繞坐標軸旋轉，生成N2個新個體，對這些新個體解碼，計算目標函數值，采用貪婪策略更新[|φb1〉,|φb2〉,…,|φbD〉]。然后進行普通個體的交叉尋優。所有N1個個體全部執行交叉尋優之后，完成一步迭代。循環上述過程直到滿足終止條件。QOA-SAC的基本流程如圖2所示。

圖2 基于自尋優和交叉尋優的量子優化模型

3 實驗仿真與實驗結果

3.1 仿真實驗環境

該仿真測試環境：操作系統為Windows10，CPU為Intel(R) Core(TM) i7-8550U，主頻1.80 GHz，內存為16 GB，仿真軟件為Matlab2020b。

3.2 測試函數

為驗證算法的有效性，選擇8個標準測試函數進行實驗分析，具體為：

[-100,100]n,f2(X*)=0

X∈[-32,32]n,f3(X*)=0

[-100,100]n,f6(X*)=0

其中，(1)是連續的、平滑多峰函數,當自變量趨近于無窮大時，函數會形成大量局部極值區域[15]。(2)是一個偶次多項式，當自變量為正無窮或負無窮時，函數值極限值等于無窮。(3)是Ackley函數，是指數函數疊加上適度放大的余弦而得到的連續型實驗函數，其特征是一個幾乎平坦的區域由余弦波調制形成一個個孔或峰，從而使曲面起伏不平[16]。(4)是Griewank函數，是智能算法領域經典的測試的函數，有許多分布廣泛的局部極小值，而這些極小值是有規律分布的。(5)是球形函數。(6)是步長函數。(7)的自變量具有上位性，因此其梯度方向不會沿著軸線方向變化，具有較高的尋優難度。(8)是Rastrigin函數，其特點是高度多峰。

3.3 實驗結果

許多量子優化算法[17-18]實驗時均使用低維測試函數，所以為驗證算法的有效性，先設置維數n=2,分別將本算法與SQGA和ASFA進行比較，對于測試函數(1)～(8),當優化函數小于0.05時，認為算法收斂。

三種算法，種群大小均取40，設置最大迭代步數MaxGen=1 000，算法進行函數優化時，若算法收斂，則退出，否則迭代到最大步數后退出，三種算法各自獨立執行30次，分別記錄執行總時間、目標函數的平均調用次數、均值以及未收斂次數，實驗結果如表2所示。

表2 低維函數優化結果對比(30次優化)

再設置維數n=30,分別將本算法與CGA和ASFA進行比較，由于SQGA對高維函數的優化效果過差，在此不進行比較，對于測試函數(1)～(8),當優化函數小于0.05時，認為算法收斂。

三種算法，種群大小均取100，設置最大迭代步數MaxGen=5 000，各自獨立運行10次，記錄運行總時長、均值、收斂次數和最優值，實驗結果如表3所示。

表3 高維函數優化結果對比(10次優化)

3.4 實驗分析

由表2可知，對于低維函數，相較于ASFA和SQGA，QOA-SAC有優化時間短、目標函數調用次數少等特點，同時，從收斂次數來看，QOA-SAC表現出極強的穩定性。

由表3可知，對于高維函數，就優化時間、優化效果和收斂次數而言，在函數(1)～(5)以及函數(7)～(8)上，QOA-SAC各方面都表現的最好也最穩定，僅僅在優化函數(6)時均值和收斂次數相較于CGA略有不如，但考慮到優化時間僅為CGA的三分之一，所以綜上，三種算法中，QOA-SAC最優，而ASFA和CGA互有優劣。QOA-SAC在函數(7)上優化結果較差，因為(7)的自變量具有上位性，因此其梯度方向不會沿著軸線方向變化，具有較高的尋優難度，如需更好的優化結果，需要設定更大的迭代步數。

QOA-SAC產生優勢的具體原因為：

(1)QOA-SAC基于Bloch球面坐標編碼，將優化問題簡化為在Bloch球面上的搜索問題，有效增強了解空間的遍歷性，最優解也可以被投射到Bloch球面上的一個圓周上，從而極大地擴充了全局最優解的數量，該圓周上任意一點被檢索到，都等價于找到了最優解，提升了算法的搜索能力；

(2)QOA-SAC的自尋優的核心策略考慮到種群中最優個體本身的優勢，在計算旋轉角時采用中心為0標準差逐代縮小的高斯分布隨機產生，實現了在算法執行的開始階段，尋優偏重于全局探索，旋轉角度較大，而在后期階段則偏重于局部開發，旋轉角度較小，達到探索和開發兩階段間的平衡，易于跳出局部極值；

(3)QOA-SAC的普通個體交叉尋優的核心策略通過多種交叉策略的設計以及基于目標點位的隨機轉角，保證了種群能持續進化而不失去多樣性，多種交叉策略的同時使用，也蘊含了集成學習策略的思想，有助于實現各種交叉策略的優勢互補，從而提升算法的搜索能力。

而相較于CGA、SQGA和ASFA這些經典算法，QOA-SAC的計算復雜度更高，這是由于QOA-SAC在自尋優和交叉尋優時都需要計算旋轉軸和旋轉角度，并且對于新生成個體要進行貪婪搜索決定的，這也是QOA-SAC的缺點，然而該算法正是以此為代價開提升搜索能力的。

4 結束語

針對許多量子優化算法存在的缺點及對高維函數尋優困難等問題，提出了基于自尋優和交叉尋優的量子優化算法。QOA-SAC首先將種群劃分為最優個體和普通個體，提出了不同的尋優策略。對于最優個體，隨著迭代過程的進行，搜索范圍收束，近距離探索次數增加，能夠較好地實現探索與開發兩階段之間的平衡，進而有效避免早熟收斂。其次，對于普通個體采取交叉尋優策略，保證了種群能持續進化而不失去多樣性。最后，通過8個標準測試函數對各個算法的性能進行檢測，仿真結果證明無論在高維還是低維，QOA-SAC都具有較好的尋優性能。