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

安 秀 芳

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

0 引 言

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

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

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

1 量子遺傳算法

1.1 優化算法的量子編碼

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

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

(1)

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

(2)

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

對于優化問題：

(3)

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

(4)

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

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

1.2 量子門

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

(5)

(6)

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

1.3 變異處理

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

(7)

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

1.4 解空間變換

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

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

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

(8)

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

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

(9)

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

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

2.1 進化方向

進化算法的最終目標就是尋找到目標的最優解，因此其結果與目前搜索到的全局最優解的變化密切相關。每一個個體和目前的全局最優解都在進化，但兩者之間仍可以形成一個進化方向，用于指導個體的進化。對于當前種群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代表當前種群代數，g(t)為進化到第t代時的全局最優解，當前種群中個體Pi(t)的進化方向是由Pi(t)和當前全局最優解g(t)來共同決定的。由上述的定義可知，D(Pi(t))值越大，則個體與當前全局最優解的差距越小;反之亦然。

2.2 優化方向

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

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

(11)

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

2.3 基于優化方向的繁殖策略

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

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

優化方向最終的執行要體現在轉角的變化上，因此在接一下來的內容中，將利用優化方向對轉角步長進行自適應調整。

3 自適應轉角步長算子

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

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

(12)

式中:

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

(13)

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

(14)

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

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

(15)

(16)

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

4 對比實驗分析

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

4.1 數學函數尋優

目標函數如下:

(17)

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

圖1 目標函數

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

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

表1 函數極值優化結果對比

4.2 工程參數尋優

將QGAIED用于優化神經網絡參數，并將神經網絡用于軸承運行狀態分類。在旋轉試驗臺上進行軸承試驗，在軸承的內圈和外圈分別用電火花加工出凹坑，用于模擬單點故障。外圈故障的實測轉速為1 800 r/min，內圈故障的實測轉速為1 700 r/min。

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

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

從表2可以看出，QGAIED優化后的神經網絡各方面表現突出，在3種方法中具有最低的分類錯誤率。此外，在尋優過程中，QGAIED也具有最快的速度。

表2 神經網絡優化結果對比

5 結 語

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

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

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

[9] 張培林, 陳彥龍, 王懷光, 等. 考慮信號特點的合成量子啟發結構元素[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] 陳漢武, 朱建鋒, 阮 越, 等. 帶交叉算子的量子粒子群優化算法[J]. 東南大學學報(自然科學版), 2016, 46(1): 23-29.

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

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