基于自尋優(yōu)和交叉尋優(yōu)的量子優(yōu)化算法

曹茂俊，尤文菁，盧玉瑩

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

0 引 言

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

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

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

1.1 量子個體編碼

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

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

(1)

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

1.2 解空間變換

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

(2)

2 算法設(shè)計與實現(xiàn)

2.1 最優(yōu)個體的自尋優(yōu)策略

對于最優(yōu)個體上的所有量子比特，分別確定旋轉(zhuǎn)軸、計算旋轉(zhuǎn)角度、實施旋轉(zhuǎn)操作，所有量子比特都被旋轉(zhuǎn)之后，即可生成一個新個體，重復(fù)上述操作，即可生成多個新個體。將這些新個體進(jìn)行解碼、計算目標(biāo)函數(shù)值之后，利用貪婪選擇策略即可實現(xiàn)當(dāng)代最優(yōu)個體的更新。

2.1.1 旋轉(zhuǎn)軸的確定方法

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

2.1.2 旋轉(zhuǎn)角度的確定方法

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

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

(3)

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

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

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

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

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

(4)

式中，σj(0)為標(biāo)準(zhǔn)差初值。利用(公式3、4)，即可獲得最優(yōu)個體量子比特的旋轉(zhuǎn)角度δj(t)。

2.1.3 最優(yōu)個體自尋優(yōu)策略的具體實現(xiàn)

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

(5)

(6)

2.2 普通個體的交叉尋優(yōu)策略

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

2.2.1 普通個體尋優(yōu)中多種交叉策略的設(shè)計

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

2.2.2 目標(biāo)位置的確定方法

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

至此，普通個體尋優(yōu)中當(dāng)前個體的目標(biāo)位置得以完全確定。

2.2.3 旋轉(zhuǎn)角度的確定方法

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

(8)

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

2.2.4 旋轉(zhuǎn)軸的確定方法

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

(9)

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

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

(10)

2.3 基于自尋優(yōu)和交叉尋優(yōu)的量子遺傳算法

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

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

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

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

圖2 基于自尋優(yōu)和交叉尋優(yōu)的量子優(yōu)化模型

3 實驗仿真與實驗結(jié)果

3.1 仿真實驗環(huán)境

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

3.2 測試函數(shù)

為驗證算法的有效性，選擇8個標(biāo)準(zhǔn)測試函數(shù)進(jìn)行實驗分析，具體為：

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

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

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

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

3.3 實驗結(jié)果

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

三種算法，種群大小均取40，設(shè)置最大迭代步數(shù)MaxGen=1 000，算法進(jìn)行函數(shù)優(yōu)化時，若算法收斂，則退出，否則迭代到最大步數(shù)后退出，三種算法各自獨立執(zhí)行30次，分別記錄執(zhí)行總時間、目標(biāo)函數(shù)的平均調(diào)用次數(shù)、均值以及未收斂次數(shù)，實驗結(jié)果如表2所示。

表2 低維函數(shù)優(yōu)化結(jié)果對比(30次優(yōu)化)

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

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

表3 高維函數(shù)優(yōu)化結(jié)果對比(10次優(yōu)化)

3.4 實驗分析

由表2可知，對于低維函數(shù)，相較于ASFA和SQGA，QOA-SAC有優(yōu)化時間短、目標(biāo)函數(shù)調(diào)用次數(shù)少等特點，同時，從收斂次數(shù)來看，QOA-SAC表現(xiàn)出極強的穩(wěn)定性。

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

QOA-SAC產(chǎn)生優(yōu)勢的具體原因為：

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

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

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

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

4 結(jié)束語

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