基本信息

Narayanan等人與1996年首次將量子理論與進(jìn)化算法想結(jié)合，提出了量子遺傳算法（QIGA）的概念；2000年，Han等人提出了一種遺傳量子算法（GQA）,然后又?jǐn)U展為量子進(jìn)化算法（QEA），實(shí)現(xiàn)了組合優(yōu)化問題的求解。

QEA采用量子比特編碼，一個(gè)量子比特表示為|ψ>=α|0+β|1>,α和β為復(fù)數(shù)，在第t代的染色體種群為

其中n為種群大??；t為進(jìn)化代數(shù)，

為染色體，即

式中：m表示染色體長度，滿足

。算法流程描述如下：

Begin

1）

,初始化種群Q(0),所有

中的

都被初始化為(1/√2, 1/√2)。

2）對初始種群中的各個(gè)體實(shí)施測量，得到一組狀態(tài)

.

是長度為m的串，每一位

為0或1，是根據(jù)量子比特的概率

或

測量得到的。測量過稱為：隨機(jī)產(chǎn)生一個(gè)數(shù)r,。若r屬于[0,1],則測量結(jié)果

；否則，取0。

3）對各狀態(tài)

進(jìn)行適應(yīng)度評價(jià)。

4）記錄下最佳個(gè)體狀態(tài)

及其適應(yīng)度值f(

)。

5）While非結(jié)束狀態(tài)do

Begin

1

;

2.對種群Q(t-1)實(shí)施測量，得到一組狀態(tài)P(t);

3.對各狀態(tài)

適應(yīng)度評價(jià)；

4.利用量子門U(t)更新Q(t);

5.保存B(t-1)和P(t)中的最佳解到B(t);

6.記錄下B(t) 中最佳個(gè)體狀態(tài)b

End

End

主要研究成果

QEA算法具有種群分散性好、全局搜索能力強(qiáng)、收斂速度快且易于與其他算法融合等優(yōu)點(diǎn)。近幾年，國內(nèi)外許多重要文獻(xiàn)對QEA算法進(jìn)行了更近一步的研究，主要體現(xiàn)在以下幾方面。

算法機(jī)理及性能研究

這類研究大多從分析QEA算法的運(yùn)行機(jī)理入手，類比分析QEA與其他經(jīng)典進(jìn)化算法的區(qū)別和相似性。具有代表性的有Ming等人從概率角度分析QEA，從量子的“波粒二象性”分析量子在進(jìn)化過程中的特點(diǎn)，將傳統(tǒng)遺傳算法（GA）和QEA借助“波粒二象性”特征進(jìn)行了類比，如表1所示:

QEA,GA波粒二象性類比

從表1可以看出：QEA的進(jìn)化與GA的進(jìn)化在本質(zhì)上具有相似性，QEA的種群是由量子組成的概率系統(tǒng)，其個(gè)體適應(yīng)度評價(jià)為量子的能量，進(jìn)化過程是量子的熵和能量的一種競爭，最終求得最優(yōu)解時(shí)量子熵降低，種群趨于聚集，進(jìn)化過程是種群從一種不平衡狀態(tài)到平衡狀態(tài)的轉(zhuǎn)變。QEA進(jìn)化的本質(zhì)是種群的量子處于不確定狀態(tài)到最終確定狀態(tài)的過程，量子檢測到為0或者1的概率趨于確定，其熵值也趨于最小。另外，文獻(xiàn)[3] ? 利用量子的糾纏態(tài)理論解釋說明了遺傳算法的本質(zhì)，認(rèn)為遺傳算法計(jì)算在本質(zhì)上是一種量子并行計(jì)算。Michael和Zhou等人都從分布式估計(jì)算法（EDA）的角度分析了量子進(jìn)化算法，認(rèn)為兩種算法共同特征是利用概率模型進(jìn)行演算，并從概率模型、抽樣選擇、學(xué)習(xí)替換和種群結(jié)構(gòu)等方面進(jìn)行了類比，得出了QEA的實(shí)質(zhì)是一種EDA的結(jié)論。

通過圖1的比較可以看出：EDA通過個(gè)體分布建立概率模型，并利用該概率模型進(jìn)行樣本采樣以產(chǎn)生新種群；而在QEA中，則通過對量子比特的概率幅測量、坍縮的方法產(chǎn)生新種群，坍縮的方法與EDA樣本采樣相對應(yīng)，它能使種群向更高適應(yīng)度方向進(jìn)化。從實(shí)驗(yàn)分析得出，QEA相對EDA更具有優(yōu)勢，主要體現(xiàn)在以下兩方面：一是量子編碼樣本具有多樣性；二是其概率模型具有自適應(yīng)性調(diào)節(jié)能力。另外，KaiFan等人對QEA算法的特性進(jìn)行了分析，對比了QEA與經(jīng)典遺傳算法、粒子群算法在解決靜態(tài)、動態(tài)函數(shù)優(yōu)化問題的性能差別，并分別測試了二進(jìn)制、十進(jìn)制編碼情況下這幾種算法對低維、高維函數(shù)的優(yōu)化效果。結(jié)果表明：在靜態(tài)環(huán)境下，QEA求解結(jié)果和運(yùn)行時(shí)間都優(yōu)于其他幾種算法；在動態(tài)環(huán)境，QEA穩(wěn)定性更好，且運(yùn)行時(shí)間更少，改進(jìn)的QEA算法更適合動態(tài)環(huán)境下高維實(shí)空間問題。

QEA與EDA進(jìn)化方式比較

種群改進(jìn)

量子比特編碼能用較小的種群規(guī)模表示問題的多個(gè)解，所以種群的規(guī)模、結(jié)構(gòu)等對算法性能影響較大。此類研究主要可歸納為如下幾方面：

1)種群結(jié)構(gòu)的改進(jìn)。Najaran等人將QEA的種群結(jié)構(gòu)進(jìn)行了分類。按圖2所示可分為：環(huán)型、網(wǎng)格型、二叉樹型、簇型、方格型、

型、階梯型和交叉階梯型等。文獻(xiàn)[2] ? 利用測試函數(shù)尋優(yōu)對比分析了不同種群結(jié)構(gòu)算法的性能，結(jié)果表明網(wǎng)格型為QEA性能最好的種群結(jié)構(gòu)。Alba等人講網(wǎng)格型的種群結(jié)構(gòu)細(xì)分為正方形、長方形、長條形等，設(shè)計(jì)了根據(jù)個(gè)體適應(yīng)度值和群體的熵來動態(tài)調(diào)節(jié)群體結(jié)構(gòu)的QEA，這種算法能很好地兼顧勘探和開采能力。Ali Nodehi等人提出了基于網(wǎng)格結(jié)構(gòu)的QEA，在這種結(jié)構(gòu)中每個(gè)節(jié)點(diǎn)表示一個(gè)個(gè)體，這種結(jié)構(gòu)能保持種群的多樣性，可有效避免早熟和陷入局部極值。另外，Guo等人利用復(fù)雜網(wǎng)絡(luò)理論類比量子進(jìn)化中的各個(gè)個(gè)體間關(guān)系，復(fù)雜網(wǎng)絡(luò)中小世界原理為量子進(jìn)化個(gè)體間關(guān)系提供了一種借鑒，為達(dá)到這種種群弱鏈接，算法將種群分解為局部小群，各小群進(jìn)行局部進(jìn)化，這種種群結(jié)構(gòu)能有效避免算法早熟。

種群結(jié)構(gòu)分類

2) 種群大小的改進(jìn)。Ali Nodehi等人利用函數(shù)動態(tài)改變QEA種群大小。當(dāng)種群增加時(shí)，隨機(jī)新加入的種群改善了種群的多樣性；當(dāng)種群減少時(shí)，去掉種群中比較差的個(gè)體，可以縮小搜索范圍，加快算法的收斂。Tayarani等人利用環(huán)形作為種群結(jié)構(gòu)，以保證每個(gè)個(gè)體只與2個(gè)鄰居相鄰，并在進(jìn)化過程中使用正旋函數(shù)改變種群大小，以保持種群多樣性。Imabeppu等人在粗粒度并行量子遺傳算法的基礎(chǔ)上，針對種群間個(gè)體遷移的方式，提出了一種成對交換的算法，該算法與局部、全局優(yōu)秀個(gè)體遷移不同，它在所有種群個(gè)體中只選擇

對個(gè)體進(jìn)行交換。對0-1問題的求解證明了所提出的算法具有局部搜索和全局搜索的優(yōu)勢。編碼擴(kuò)展

表2,圖3，圖4

QEA算法設(shè)計(jì)之初為量子比特編碼，在進(jìn)化中測量產(chǎn)生二進(jìn)制串，所以算法對多參數(shù)和高維問題的求解受到了限制。QEA編碼的擴(kuò)展成為研究的熱點(diǎn)，一些具有代表性的改進(jìn)可歸納如下：1) 概率實(shí)數(shù)編碼。Cruz等人定義了一種實(shí)數(shù)編碼方式的QEA，該思想是將個(gè)體中每個(gè)分量用

表示取值空間，它表示為一矩形區(qū)域，其中

表示變量取值的坐標(biāo)中心，

為矩形取值空間的寬度，矩形的高度為

,N為變量個(gè)數(shù)，個(gè)體表示為

。該編碼利用高度表示概率，例如表2表示的是兩個(gè)體q1，q2的初始值。圖3表示了表2中兩個(gè)體q1，q2和概率實(shí)數(shù)編碼。圖3中，個(gè)體q1由中心為-5，寬度為20的g11矩形框及中心為0，寬度為20的g12矩形框組成。圖4表示兩個(gè)體q1，q2和進(jìn)行交叉的結(jié)果。從圖4可以看出，當(dāng)2個(gè)個(gè)體進(jìn)行交叉時(shí)，是將q1，q2分別代表的矩形區(qū)域進(jìn)行疊加來產(chǎn)生新的個(gè)體，疊加后的矩形框高度表示在該區(qū)域取值的概率。用這種方式編碼的量子進(jìn)化算法，對高維函數(shù)優(yōu)化測試結(jié)果顯示具有更好的收斂速度和尋優(yōu)精度。覃朝勇等人在此基礎(chǔ)上引入了勢能的概念，并用于高維函數(shù)優(yōu)化，也取得了較好的性能。

2）三倍體編碼。Li等人提出了一種量子位Bloch球面坐標(biāo)編碼。圖5表示Bloch球中的一個(gè)點(diǎn)對應(yīng)一個(gè)量子比特，因此量子比特|ψ>可描述為

按照這種方式，將量子位的3個(gè)Bloch球面坐標(biāo)作為基因位，則可將量子比特編碼轉(zhuǎn)換為Bloch球面編碼，表示如下：

圖5 Bloch球面坐標(biāo)表示量子比特

這種編碼能夠避免因?qū)α孔游粶y量產(chǎn)生二進(jìn)制串所帶來的隨機(jī)性，可用于連續(xù)優(yōu)化問題，能夠擴(kuò)展全局最優(yōu)解的數(shù)量，提高獲得全局最優(yōu)解的概率。另外，高輝等人提出了一種三倍體實(shí)數(shù)編碼，即該編碼由自變量的一個(gè)分量與量子比特組成，算法設(shè)計(jì)了互補(bǔ)雙變異算子來進(jìn)化個(gè)體，這種算子融合了量子旋轉(zhuǎn)門和量子比特歸一化條件，實(shí)現(xiàn)了局部搜索與全局搜索的平衡。

(3) 混合二倍體編碼。Zhao等人采用改進(jìn)的二倍體編碼形式，即

其中x屬于[a,b]為定義域區(qū)間，是實(shí)數(shù)。該文利用這種編碼提出了一種基于QEA的模糊神經(jīng)網(wǎng)絡(luò)模型。另外，申抒含等人提出一種多進(jìn)制概率角復(fù)合位編碼QEA，將量子位的概率幅表示法轉(zhuǎn)化為復(fù)合位的概率角表示法，采用隨機(jī)觀測方法得到觀測個(gè)體，采用概率角增減的方式對個(gè)體進(jìn)行更新。其編碼形式為其中

。該算法適用于采用任意進(jìn)制編碼問題。實(shí)驗(yàn)表明，算法在適用范圍、搜索能力和運(yùn)算速度上均具有較為明顯的優(yōu)勢。算子創(chuàng)新

基本QEA與一般進(jìn)化計(jì)算不同，沒有選擇、交叉、變異等算子，所以修改并提出新算子融入QEA中便成為研究方向，具有代表性的有：

1）粒子群算子。Wang和周殊等人采用粒子群優(yōu)化算子調(diào)節(jié)量子旋轉(zhuǎn)門，并根據(jù)QEA自身概率特性，引入了最優(yōu)解方差函數(shù)來評價(jià)該算法的穩(wěn)定性。

2）免疫算法。Hongjian 等人將免疫的概念引入QEA，免疫算子在保留原算法優(yōu)良特性的前提下，力圖有選擇、有目的地利用待求問題中的一些特征信息或先驗(yàn)知識，抑制或避免求解過程中的一些重復(fù)或無效的工作，以提高算法的整體性能。Haoteng等人提出了基于混沌理論的免疫QEA，該算法應(yīng)用混沌免疫理論并依據(jù)小生境機(jī)制將初始個(gè)體劃分為實(shí)數(shù)編碼染色體的子群，各子群應(yīng)用免疫算子的局域搜索能力找出優(yōu)化解。

3）克隆算子。李陽陽等人提出一種基于量子編碼的免疫克隆算法來求解SAT問題，算法中采用量子位的編碼方式表達(dá)種群中的抗體，采用量子旋轉(zhuǎn)門和動態(tài)調(diào)整旋轉(zhuǎn)角策略對抗體進(jìn)行演化，加速原有克隆算子的收斂，利用克隆算子的局部尋優(yōu)能力強(qiáng)的特點(diǎn)，在各個(gè)子群體間采用量子交叉操作來增強(qiáng)信息交流，以提高種群的多樣性，防止早熟。

4）模擬退火、模糊算子，王毅等人借鑒模擬退火方法，根據(jù)進(jìn)化代數(shù)及個(gè)體的適應(yīng)度值修正傳統(tǒng)QEA旋轉(zhuǎn)門函數(shù)的旋轉(zhuǎn)角度值，焦嵩鳴等人利用模糊推理的方法，自適應(yīng)地提高了算法的計(jì)算精度和收斂速度。

5）文化算子，Cruz等人在QEA中引入了文化算子，該思想借鑒了文化算法中規(guī)范知識的概念，用以描述當(dāng)代種群的有效搜索空間范圍，規(guī)范知識可以規(guī)避不在該范圍內(nèi)個(gè)人，引導(dǎo)個(gè)體進(jìn)入有效區(qū)域搜索，算法收斂速度和精度都得到了提高。

6）其他算子。AraujoM等人利用多目標(biāo)優(yōu)化對量子進(jìn)化中的旋轉(zhuǎn)角參數(shù)進(jìn)行計(jì)算，算法分2個(gè)層次，上層為求解多個(gè)測試函數(shù)的旋轉(zhuǎn)角和旋轉(zhuǎn)方向參數(shù)，將得到的參數(shù)用于底層的量子進(jìn)化優(yōu)化過程。Xing等人利用兩點(diǎn)交叉算子對量子旋轉(zhuǎn)門調(diào)整進(jìn)行改進(jìn)，其核心思想是確保在任何狀態(tài)下以較大的概率使當(dāng)前解收斂到一個(gè)具有更高適應(yīng)度的染色體。