改 進 進 化 方 向 的 量 子 遺 傳 算 法

安 秀 芳

(徐州工業(yè)職業(yè)技術(shù)學院 信息與電氣工程學院,江蘇 徐州 221400)

0 引 言

隨著計算機技術(shù)的發(fā)展，利用計算機強大計算能力的全局尋優(yōu)算法，如遺傳算法、粒子群算法均得到了大量應用，取得了良好效果。近年來，隨著量子理論的應用，全局搜索算法的尋優(yōu)能力得到進一步提升。量子遺傳算法(Quantum Genetic Algorithm，QGA)是一種基于量子計算與遺傳算法的概率優(yōu)化算法，比傳統(tǒng)的遺傳算法具有更強的搜索能力和更快的搜索速度[1-2]。

QGA在運算過程中，主要利用量子比特的角度改變來實現(xiàn)進化，轉(zhuǎn)角的變化方式直接關(guān)系到算法的尋優(yōu)能力和收斂速度。通過研究，得出當轉(zhuǎn)角步長在0.005π～0.1π之間變動時，具有良好的搜索效果[3]。依據(jù)根據(jù)進化的代數(shù)調(diào)整轉(zhuǎn)角步長，提高了QGA的算法全局尋優(yōu)能力[4]；根據(jù)種群的規(guī)模和個體的信息對進化步長進行調(diào)整，確保了搜索效果[5]。上述方法均提高了QGA的全局搜索能力，但在算法執(zhí)行過程中，對進化方向的選擇仍具有一定的隨意性和模糊性，降低了算法的運算速度。

針對上述問題，本文提出改進進化方向的量子遺傳算法(QGAIED)。該算法依據(jù)當前全局最優(yōu)解選擇進化方向，根據(jù)兩個進化方向共同調(diào)整轉(zhuǎn)角步長，實現(xiàn)了算法進化步長的自動調(diào)整，在提高搜索能力的同時加速了進化速度。

1 量子遺傳算法

1.1 優(yōu)化算法的量子編碼

QGA采用量子比特來表達每一個個體，一個量子比特表示如下[6-9]：

|φi〉=α|0〉+β|1〉

(1)

式中:α和β分別表示|0〉和|1〉的量子概率幅，滿足歸一化條件：

(2)

因此，在實際運用中可將α和β的范圍設置為[-1,1]。

對于優(yōu)化問題：

(3)

式中，aj和bj為決策向量X=(x1，x2，…，xn)T∈Rn的分量xj的上限和下限。直接應用概率幅對QGA中的個體進行編碼，結(jié)合式(3)可知，在種群的第t代，每一個個體需要n個量子比特進行編碼，其量子編碼形式為：

(4)

式中:θij為角度，θij=2π×rnd，rnd表示[-1，1]之間數(shù)值;i=1，2，…，m表示種群規(guī)模；j=1，2，…，n表示每一個個體中的量子比特總數(shù)。cos2θij+sin2θij=1，符合量子概率幅的歸一化條件?？芍琾i屬于n維量子空間In=[-1，1]n。

如果式(3)的優(yōu)化問題在實數(shù)空間有M個全局最優(yōu)解，利用式(4)進行編碼之后，n維量子空間In=[-1，1]n中可以搜索到2n+1M個解[5]。換言之，將實數(shù)空間轉(zhuǎn)換到量子空間，全局最優(yōu)解以指數(shù)級增長，極大的提高了算法的搜索速度和搜索能力。

1.2 量子門

QGA在進化過程中，主要通過對每一個量子比特的角度進行變換以實現(xiàn)進化[10-14]，通常采用旋轉(zhuǎn)量子門更新量子比特相位：

(5)

(6)

式中:Δθ稱為量子門中的轉(zhuǎn)角步長，包含大小和方向，在QGA進化過程中，Δθ起著更新個體的作用。易知，Δθ的變化最終將表現(xiàn)為個體的變化，直接影響算法的收斂速度和尋優(yōu)能力。Δθ取值過小，算法轉(zhuǎn)角步長太小，無法跨出局部最優(yōu)解，難以尋找到全局最優(yōu)解；Δθ取值過大，算法步長太大，運算速度較快，但容易忽視目標的細節(jié)變化，降低了尋優(yōu)精度。

1.3 變異處理

在進化過程中，如果只采用轉(zhuǎn)角步長進行逐步進化，不利于全局搜索，因此在進化過程中還需要考慮個體的變異[15-17]，突破當前種群限制，采用量子非門對個體進行變異：

(7)

可以看出，量子非門對調(diào)了正弦和余弦的位置。由于sinθ=cos(π/2-θ)，cos(θ)=sin(π/2-θ)，從本質(zhì)上看，相當于量子比特在進化過程中改變了π/2-2θ，本質(zhì)上仍然為量子門旋轉(zhuǎn)。由于變化的角度較大，故變異操作有助于增加種群的多樣性，突破早熟收斂。

1.4 解空間變換

在量子編碼中每個個體包含n個量子比特，需要將這n個比特從量子空間轉(zhuǎn)換到實數(shù)空間，才能夠得出式(3)的優(yōu)化解。由于一個量子比特包含兩個概率幅，故從量子空間變換到實數(shù)空間也存在兩個解。

根據(jù)α、β解得相應解空間中決策向量X的第j位為：

Xic,j=0.5[bi(1+αij)+ai(1-αij)]

(8)

(2) 根據(jù)β解得相應解空間中決策向量X的第j位為：

Xis,j=0.5[bi(1+βij)+ai(1-βij)]

(9)

Xic,j由量子態(tài)|0〉的概率αij求出，Xis,j由量子態(tài)|1〉的概率幅βij求出，每個量子位對應待求解問題在該位置的兩個解。因此，QGA必然具有更多的優(yōu)化解，在量子空間更容易找到全局極值。

2 基于進化方向的繁殖策略

2.1 進化方向

進化算法的最終目標就是尋找到目標的最優(yōu)解，因此其結(jié)果與目前搜索到的全局最優(yōu)解的變化密切相關(guān)。每一個個體和目前的全局最優(yōu)解都在進化，但兩者之間仍可以形成一個進化方向，用于指導個體的進化。對于當前種群P(t)中的任意個體ai(t)，定義其進化方向為：

D(Pi(t))=C(g(t),Pi(t))

(10)

Pi(t)∈P(t)

式中:C(g(t),Pi(t))用于計算g(t)和ai(t)的相似度，方向從Pi(t)指向g(t)，t代表當前種群代數(shù)，g(t)為進化到第t代時的全局最優(yōu)解，當前種群中個體Pi(t)的進化方向是由Pi(t)和當前全局最優(yōu)解g(t)來共同決定的。由上述的定義可知，D(Pi(t))值越大，則個體與當前全局最優(yōu)解的差距越小;反之亦然。

2.2 優(yōu)化方向

進化中能提高種群中個體適應度的進化方向即為優(yōu)秀的進化方向。利用當前個體與當前全局最優(yōu)解之間的相似度來確定進化方向，仍具有模糊性和隨機性。有必要對個體進化方向的加以判別和約束，從而使進化過程朝更優(yōu)秀的方向進行。

進化方向用于指導群體進化，需要通過一系列特定的操作，從當前種群P(t)的個體進化方向中選擇出優(yōu)化方向，提高進化速度，即

(11)

式中:Θs表示對進化方向的選擇操作;Φ表示確定優(yōu)化方向時的準則;and表示“且”;where表示約束條件。式(11)表示，在t代和t-1代之間進行比較，選擇進化后適應度更大的個體，然后依據(jù)選擇出的個體進一步確定優(yōu)化方向。由于沿選擇出的方向進化后能提高個體的適應度，故本文根據(jù)種群個體的適應度進行選擇，選擇出的方向為基于個體適應度的優(yōu)化方向。

2.3 基于優(yōu)化方向的繁殖策略

當前種群中的最優(yōu)個體通常被認為是適應度最大的個體，而當前種群中個體的優(yōu)化進化方向通常被認為能速度提高個體適應度方向，如果讓當前的種群個體沿著當前優(yōu)化進化方向進化，則其子代個體可能會具有更優(yōu)的性能，但如果所有的個體都向一個優(yōu)化方向進化，易導致局部最優(yōu)解，因此需要進一步加以改進。

記Op={Pp,1(t),…,Pp,k(t),…,Pp,m1(t)}為到t代為止全局搜索到的適應度最大的前m1個個體，記Dopt={Dopt,1,Dopt,2,…,Dopt,m2}為當前種群中個體進化方向中前m2個優(yōu)化方向，讓這m1個個體沿著當前種群的m2個優(yōu)化方向進化，形成具有m1+m1×m2個個體的新群體。為保證種群規(guī)模，假設初始種群規(guī)模為m，當m1+m1×m2≥m，則去除適應度低的個體。如果m1+m1×m2

優(yōu)化方向最終的執(zhí)行要體現(xiàn)在轉(zhuǎn)角的變化上，因此在接一下來的內(nèi)容中，將利用優(yōu)化方向?qū)D(zhuǎn)角步長進行自適應調(diào)整。

3 自適應轉(zhuǎn)角步長算子

設一個量子個體由n個量子比特代表，Pi(t-1)變?yōu)镻i(t)的轉(zhuǎn)角步長為{Δθi1,Δθi2,…,Δθin}，每個Δθij代表一個量子比特的轉(zhuǎn)角步長。為保證運算的精度。為兼顧精度和速度，需要使得轉(zhuǎn)角步長自適應變化。

用Op結(jié)合進化方向Dp={Dp,1,…,Dp,l,…,Dp,m2}來計算自適應轉(zhuǎn)角步長。設Dp,l對應的個體為Pp,l(t)，一個優(yōu)化方向可能引起局部最優(yōu)解，不利于全局最優(yōu)解的搜索。為保證最優(yōu)解的搜索能力，結(jié)合優(yōu)化方向計算轉(zhuǎn)角步長時，采用Dp中的兩個方向來共同確定步長：

(12)

式中:

f(θp,kj(H)-θp,lj)=

(13)

f(θp,kj(L)-θp,lj)=

(14)

j=1，2，…，n，表示個體中的第j個量子比特;θp,kj表示當前全局最優(yōu)解集合Op中Pp,k(t)對應的第j個量子比特的相位;θp,lj表示優(yōu)化方向Dp,l對應的Pp,l(t)的第j個量子比特的相位;S，T為權(quán)值，S，T∈[0，1]，S+T=1。Dp中的兩個方向?qū)獌蓚€個體，H表示適應度更大的一個個體，L表示適應度更小的個體。FS表示適應度更大的一個個體的適應度值，F(xiàn)T表示適應度更小的一個個體的適應度值。

Dp中的兩個方向?qū)獌蓚€個體，對新一代個體旋轉(zhuǎn)步長產(chǎn)生的貢獻由權(quán)值S和T決定，考慮到搜索速度，具有更大適應值的Pp,l(H)所占的比重應當更大，才能更快的尋找到最優(yōu)解，同時Pp,l(L)應當對進化方向進行修正，以避免局部最優(yōu)解的出現(xiàn)。綜上，參數(shù)S和T的計算公式為：

(15)

(16)

可知，步長式(12)由兩個方向共同決定，且適應度更大的值所占權(quán)值重，起主導作用；適應度更小的值起修正作用。該步長計算方式一方面避免了局部最優(yōu)，又可以提高收斂速度?？梢园l(fā)現(xiàn)，進化時在適應值變化小的地方，轉(zhuǎn)角步長變大，加快進化速度；在適應值變化大的地方，轉(zhuǎn)角步長減小，不至于越過全局最優(yōu)解，同時兼顧了搜索能力和搜素速度。

4 對比實驗分析

QGAIED通過權(quán)值同時控制優(yōu)化方向，在保證全局搜索能力的同時也提高了搜索速度，因此可用于函數(shù)極值搜索和工程應用中的參數(shù)優(yōu)化。

4.1 數(shù)學函數(shù)尋優(yōu)

目標函數(shù)如下:

(17)

求其極大值點，函數(shù)圖形如圖1所示。

圖1 目標函數(shù)

該函數(shù)具有無限個局部極大值，全局最大值為1，且全局只有(0,0)位置為最優(yōu)解，最優(yōu)解具有唯一性。

采用QGAIED進行尋優(yōu)，設置總?cè)阂?guī)模m=20，量子比特數(shù)n=2，變異概率p=0.1，轉(zhuǎn)角的初始值為θ0=0.05π，最大進化代數(shù)tmax=300，適應度函數(shù)取-f(x,y)，全局尋優(yōu)結(jié)果對比見表1。表中數(shù)據(jù)為50次實驗平均值?？梢钥闯觯琎GAIED的全局搜索能力最強、全局搜索速度最快，其次是QGA。遺傳算法GA的尋優(yōu)效果最差，50次實驗均未找到全局最優(yōu)解。

表1 函數(shù)極值優(yōu)化結(jié)果對比

4.2 工程參數(shù)尋優(yōu)

將QGAIED用于優(yōu)化神經(jīng)網(wǎng)絡參數(shù)，并將神經(jīng)網(wǎng)絡用于軸承運行狀態(tài)分類。在旋轉(zhuǎn)試驗臺上進行軸承試驗，在軸承的內(nèi)圈和外圈分別用電火花加工出凹坑，用于模擬單點故障。外圈故障的實測轉(zhuǎn)速為1 800 r/min，內(nèi)圈故障的實測轉(zhuǎn)速為1 700 r/min。

軸承振動信號包括正常、外圈故障、內(nèi)圈故障3類，使用小波將每一個采樣振動信號分解到8個頻帶，統(tǒng)計每個頻帶的特征，并對特征進行歸一化處理，以降低故障強弱的影響。每種狀態(tài)采集30個振動信號，10個樣本用于訓練，20個樣本用于測試。

設置神經(jīng)網(wǎng)絡的網(wǎng)格層數(shù)c=3，輸入節(jié)點l1=10，隱層節(jié)點l2=10，輸出節(jié)點l3=10，種群規(guī)模m=20，變異概率p=0.01，轉(zhuǎn)角初值θ0=0.05π，最大進化代數(shù)lmax=500，適應度函數(shù)取分類正確率。優(yōu)化后神經(jīng)網(wǎng)絡的故障分類效果對比見表2，表中數(shù)據(jù)為40次實驗平均值。

從表2可以看出，QGAIED優(yōu)化后的神經(jīng)網(wǎng)絡各方面表現(xiàn)突出，在3種方法中具有最低的分類錯誤率。此外，在尋優(yōu)過程中，QGAIED也具有最快的速度。

表2 神經(jīng)網(wǎng)絡優(yōu)化結(jié)果對比

5 結(jié) 語

通過選擇進化方向，本文對量子遺傳算法的進化步長進行了優(yōu)化，提出了改進進化方向的量子遺傳算法QGAIED。在進化過程中，QGAIED的步長根據(jù)兩個優(yōu)化方向自適應調(diào)整，在提高搜索速度的同時，有效避免了局部最優(yōu)。數(shù)學函數(shù)尋優(yōu)和工程參數(shù)尋優(yōu)均表明，QGAIED在保證搜索能力的同時，顯著縮短了搜索時長，在極值搜索和工程優(yōu)化中均有良好應用前景。

[1] Lü Fengmao, Yang Guowu, Yang Wenjing,etal. The convergence and termination criterion of quantum-inspired evolutionary neural networks[J]. Neurocomputing, 2017, 238(5): 157-167.

[2] 王瑞琪, 李 珂, 張承慧, 等. 基于RQGA和非支配排序的多目標混沌量子遺傳算法[J]. 電機與控制學報, 2012, 16(4): 91-99.

[3] Narayanan A, Moore M. Quantum-inspired genetic algorithm[C]∥Proc of IEEE Conf. on Evolutionary Computation. Piscataway: 1996:61-66.

[4] Qu Zhijian, Liu Xiaohong, Zhang Xianwei,etal. Hamming-distance-based adaptive quantum-inspired evolutionary algorithm for network coding resources optimization[J]. The Journal of China Universities of Posts and Telecommunications, 2015, 22(3): 92-99.

[5] Patvardhan C, Bansal S, Srivastav A. Solving the 0-1 quadratic knapsack problems with a competitive quantum inspired evolutinary algprithm[J]. Journal of Computional and Applied Mathematics, 2015, 285(8):86-99.

[6] 羅玉玲, 杜明輝. 基于量子Logistic映射的小波域圖像加密算法[J]. 華南理工大學學報(自然科學版), 2013, 4 (6): 53-62.

[7] 付曉薇, 丁明躍, 周成平, 等. 基于量子概率統(tǒng)計的醫(yī)學圖像增強算法研究[J]. 電子學報, 2010, 38(7): 1590-1596.

[8] 付曉薇, 丁明躍, 蔡 超, 等. 基于量子衍生參數(shù)估計的醫(yī)學超聲圖像去斑算法[J]. 電子學報, 2011, 39(4): 812-818.

[9] 張培林, 陳彥龍, 王懷光, 等. 考慮信號特點的合成量子啟發(fā)結(jié)構(gòu)元素[J]. 吉林大學學報(工學版):2015, 45(4):1181-1188.

[10] Luciano R, Ricardo T, Marley M. Quantum-inspired evolutionary algorithm for ordering problems[J]. Expert Systems with Application, 2017, 67(1):71-83.

[11] Chen Yanlong, Zhang Peilin, Wang Zhengjun,etal. Denoising algorithm for mechanical vibration signal using quantum Hadamard transformation [J]. Measurement, 2015, 66:168-175.

[12] Tsai J, Hsiao F Y, Li Y J,etal. A quantum search algorithm for future spacecraft attitude determination[J]. Acta Astronautica, 2011, 68(7): 1208-1218.

[13] Mangone F, He J, Tang J,etal. A PAPR reduction technique using Hadamard transform combined with clipping and filtering based on DCT/IDCT for IM/DD optical OFDM systems[J]. Optical Fiber Technology, 2014, 20(4): 384-390.

[14] Xu J, Zhu Z M, Liu C X,etal. The processing method of spectral data in Hadamard transforms spectral imager based on DMD[J]. Optics Communications, 2014, 325(30): 122-128.

[15] 陳漢武, 朱建鋒, 阮 越, 等. 帶交叉算子的量子粒子群優(yōu)化算法[J]. 東南大學學報(自然科學版), 2016, 46(1): 23-29.

[16] 張 磊, 方洋旺, 柴 棟, 等. 基于改進量子進化算法的巡航導彈航路規(guī)劃方法[J]. 兵工學報, 2014, 35(11): 1820-1827.

[17] 張宇獻, 李 松, 李 勇, 等. 基于量子位實數(shù)編碼的優(yōu)化算法及軋制規(guī)程多目標優(yōu)化[J]. 儀器儀表學報, 2014, 35(11): 2440-2447.