安 秀 芳

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

0 引 言

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

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

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

1 量子遺傳算法

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

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

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

(1)

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

(2)

因此，在實(shí)際運(yùn)用中可將α和β的范圍設(shè)置為[-1,1]。

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

(3)

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

(4)

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

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

1.2 量子門

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

(5)

(6)

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

1.3 變異處理

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

(7)

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

1.4 解空間變換

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

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

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

(8)

(2) 根據(jù)β解得相應(yīng)解空間中決策向量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求出，每個(gè)量子位對(duì)應(yīng)待求解問題在該位置的兩個(gè)解。因此，QGA必然具有更多的優(yōu)化解，在量子空間更容易找到全局極值。

2 基于進(jìn)化方向的繁殖策略

2.1 進(jìn)化方向

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

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

(10)

Pi(t)∈P(t)

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

2.2 優(yōu)化方向

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

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

(11)

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

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

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

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

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

3 自適應(yīng)轉(zhuǎn)角步長(zhǎng)算子

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

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

(12)

式中:

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

(13)

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

(14)

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

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

(15)

(16)

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

4 對(duì)比實(shí)驗(yàn)分析

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

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

目標(biāo)函數(shù)如下:

(17)

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

圖1 目標(biāo)函數(shù)

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

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

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

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

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

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

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

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

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

5 結(jié) 語

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

[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和非支配排序的多目標(biāo)混沌量子遺傳算法[J]. 電機(jī)與控制學(xué)報(bào), 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]. 華南理工大學(xué)學(xué)報(bào)(自然科學(xué)版), 2013, 4 (6): 53-62.

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

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

[9] 張培林, 陳彥龍, 王懷光, 等. 考慮信號(hào)特點(diǎn)的合成量子啟發(fā)結(jié)構(gòu)元素[J]. 吉林大學(xué)學(xué)報(bào)(工學(xué)版):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]. 東南大學(xué)學(xué)報(bào)(自然科學(xué)版), 2016, 46(1): 23-29.

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

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