基于災(zāi)變因子的量子遺傳算法研究?

張秋艷 王默玉 申曉留 武書舟 閆麗娜 曹柳青

（華北電力大學(xué)控制與計算機(jī)工程學(xué)院 北京 102206）

1 引言

在現(xiàn)實生活中，許多優(yōu)化問題要求人們不僅要計算出其極值，還要得出其最優(yōu)值。這類問題對傳統(tǒng)的算法造成的嚴(yán)峻的挑戰(zhàn)。在這種情況下，越來越多的群智能算法相繼的提出，遺傳算法是由美國密歇根大學(xué)的John Holland 教授和他的同事與學(xué)生最早開始研究和應(yīng)用的。是一種借鑒生物界自然選擇和進(jìn)化機(jī)制發(fā)展起來的高度并行、隨機(jī)、自適應(yīng)搜索算法［1］。簡而言之，它使用了群體搜索技術(shù)，將種群（population）代表一組問題解，通過對當(dāng)前種群施加選擇（selection）、交叉（crossover）和變異（mutation）等一系列遺傳算子（operator），從而產(chǎn)生新一代種群，并逐步使種群進(jìn)化到包含近似最優(yōu)解的狀態(tài)。由于其思想簡單、易于實現(xiàn)以及表現(xiàn)出來的健壯性，遺傳算法贏得了許多應(yīng)用領(lǐng)域，特別是近年來在問題求解、優(yōu)化和搜索、機(jī)器學(xué)習(xí)、智能控制、模式識別和人工生命等領(lǐng)域取得了許多令人鼓舞的成就。

2000 年，K.H，HAN 等在文獻(xiàn)中提出在遺傳編碼過程中加入量子的態(tài)矢量表達(dá)，首次創(chuàng)造性地提出了量子遺傳算法并在量子旋轉(zhuǎn)門的基礎(chǔ)上，實現(xiàn)了個體染色體的基因調(diào)整策略，大大提高了量子遺傳算法在量子計算機(jī)上運行的可能性。

2 量子遺傳算法理論與方法

在量子遺傳算法中，最重要的是量子編碼和量子門的引入。量子編碼是將染色體用量子的態(tài)矢量表示，使一條染色體表達(dá)為多個態(tài)的疊加，從而增加了種群多樣性，使算法能夠在較小的種群規(guī)模下求得最優(yōu)解；而量子門的引入使算法具備了開發(fā)能力和探索能力，可以保證算法收斂［14～15］。目前，量子遺傳算法被應(yīng)用到了多個領(lǐng)域，如電網(wǎng)規(guī)劃以及圖像處理等［2～4，13］。

2.1 量子編碼

在量子遺傳算法中，使用了一種新穎的基于量子比特的編碼方式，即用一對復(fù)數(shù)定義一個量子比特位，一個具有m 個量子比特位的系統(tǒng)可以描述為

其中，|αi|2+ |βi|2=1(i=1,2,…,m)。

量子比特位可以同時處于兩個量子態(tài)的疊加態(tài) φ =α0 +β1 中，如:其中 0 和 1 分別表示自旋向下態(tài)和自旋向上態(tài)，φ 為一種量子態(tài)的表示，式中 α 和 β 為復(fù)數(shù)，表示量子位狀態(tài)的概率幅，| α|2i可看成量子處于自旋向下態(tài)的概率，| β|2可看成量i子處于自旋向上態(tài)的概率。

若有一個具有三個量子比特位的量子編碼:

則該量子編碼可以轉(zhuǎn)換為如下形式的二進(jìn)制編碼。

即該量子編碼轉(zhuǎn)換為|000|、|001|、|100|、|101| 的概率分別為1/8、3/8、1/8、3/8。所以，該量子編碼具有四個二進(jìn)制編碼的信息，顯然這種編碼方式能夠使種群擁有更好的多樣性，且隨著 |α|2、| β|2ii趨于0 或1，染色體將收斂于一個單一態(tài)。因此，與遺傳算法相比，量子遺傳算法在較小的種群規(guī)模下就可以得到最優(yōu)解。

2.2 量子門

量子門作為完成進(jìn)化的操作機(jī)構(gòu)，可以根據(jù)具體情況進(jìn)行選取，目前已有多種量子門，按照量子遺傳算法的特點，選擇量子旋轉(zhuǎn)門作為執(zhí)行機(jī)構(gòu)較為合適。

通過量子門變換矩陣可以實現(xiàn)種群的更新實際上量子門變換矩陣是一個可逆的歸一化矩陣，即需要滿足UU*=U*U=1。

常用的量子旋轉(zhuǎn)門為

其中[α ,β]T為染色體中的第i 個量子位，θ 旋轉(zhuǎn)iii角。

2.3 量子遺傳算法流程

量子遺傳算法首先取規(guī)模為N 的種群進(jìn)行初始化，一般情況，種群中全部染色體的所有基因都被初始化為(1/ 2,1/ 2)；然后對初始種群每個個體實時一次測量，得到一個狀態(tài)P（t），然后對這一組解進(jìn)行適應(yīng)度評估，記錄下最佳最適應(yīng)度個體作為下一步演化的目標(biāo)值［5］。并實時記錄最佳個體及其適應(yīng)度值。具體算法基本步驟如下:

t=0

對Q（t）初始化

通過觀察Q（t）的狀態(tài)確定P（t）

評價P（t）保存中的最優(yōu)個體

如果不滿足終止條件

Begin

t=t+1 ；

通過觀察Q（t）的狀態(tài)確定P（t）

評價P（t）保存中的最優(yōu)個體

用量子門U（t）更新Q（t）

保存P（t）中的最佳個體

直至滿足終止條件

圖1 量子遺傳算法流程

2.4 災(zāi)變因子

為了進(jìn)一步提高全局搜索性能，引入“災(zāi)變”概念到遺傳算法中。在生物進(jìn)化過程中，“災(zāi)變”就是外部環(huán)境的巨大變化，如冰河期、森林大火、大地震和瘟疫等，是對絕大多數(shù)生物的滅頂之災(zāi)，造成了大量物種或者個體的滅絕，只有個別適應(yīng)能力特別強(qiáng)的物種或者個體得以生存，在“災(zāi)變”過后重新繁衍后代。顯然“災(zāi)變”后幸存的物種或個體的生存能力更強(qiáng)［8～10］。

當(dāng)經(jīng)過若干代之后，算法中群體已經(jīng)獲得某個局部最優(yōu)解，而此時的群體隱含著大量與該局部最優(yōu)相關(guān)的信息，趨向于早熟收斂，依靠交叉和變異等遺傳操作跳出來的可能性較小，這時可以引入“災(zāi)變”，除了原最好解留下來，其他個體重新隨機(jī)產(chǎn)生，獲得一些全局性的有效信息，以較大的概率得到遠(yuǎn)離原局部最優(yōu)，使得在較小的群體規(guī)模下獲得較大的多樣性，則可以更有機(jī)會擺脫原先的局部最優(yōu)解，因為現(xiàn)在的候選解往往不再局限于以前的某個角落了［11～12］。

災(zāi)變因子引入思路簡示如下:

1）災(zāi)變次數(shù)初始化；

2）進(jìn)行某階段的遺傳進(jìn)化操作和適應(yīng)度評估；

3）災(zāi)變次數(shù)增加1；

4）如果達(dá)到預(yù)定值則輸出結(jié)果并結(jié)束，否則存當(dāng)前最好解并返回第2）步。

2.5 基于災(zāi)變因子的量子遺傳算法

當(dāng)種群中個體之間的差別很小的時候，認(rèn)為算法將要陷入不成熟收斂了，此時采用災(zāi)變算子來提高個體之間的多樣性，以保證算法能夠找到全局最優(yōu)解。

災(zāi)變的實施也有很多的方法:1）突然增大變異率；2）保留最好解，重新初始化其他的個體；3）對不同的個體實施不同規(guī)模的變異。本文采用的是第二種方法。

基于災(zāi)變因子的量子遺傳算法流程如圖2。

圖2 基于災(zāi)變因子的量子遺傳算法

加入災(zāi)變因子后，當(dāng)最優(yōu)值保持一定次數(shù)后，則認(rèn)為進(jìn)化已經(jīng)進(jìn)入了不成熟的收斂階段，設(shè)定災(zāi)變因子disater_factor，當(dāng)最優(yōu)值持續(xù)一定程度后，保留最優(yōu)值并對種群進(jìn)行新的初始化，確保算法跳出局部最優(yōu)

3 實驗對比

本文采用三個標(biāo)準(zhǔn)函數(shù)針對量子遺傳算法與標(biāo)準(zhǔn)遺傳算法作對比:

這幾個典型的標(biāo)準(zhǔn)函數(shù)都具有全局極值點，并且有多峰值函數(shù)，有多個峰值陷阱，這樣一般優(yōu)化算法容易陷入局部收斂，用它們來比較各種算法的性能是合適的。在這里種群大小設(shè)置為40，最大遺傳代數(shù)基礎(chǔ)設(shè)置為100，分別測試標(biāo)準(zhǔn)遺傳算法SGA 以及基于災(zāi)變因子量子遺傳算法QGA 的尋優(yōu)效果，結(jié)果如圖4～6所示。

圖3 測試函數(shù)空間曲面圖

圖4 F1函數(shù)進(jìn)化代數(shù)與最優(yōu)解變化

圖5 F2函數(shù)進(jìn)化代數(shù)與最優(yōu)解變化

圖6 F3函數(shù)進(jìn)化代數(shù)與最優(yōu)解變化

上圖中，虛線表示標(biāo)準(zhǔn)遺傳算法的最優(yōu)解與進(jìn)化代數(shù)的關(guān)系，實線表示基于災(zāi)變因子量子遺傳算法的最優(yōu)解與進(jìn)化代數(shù)的關(guān)系。可以得出在多峰值函數(shù)尋優(yōu)過程中，基于災(zāi)變因子量子遺傳算法收斂速度快，尋優(yōu)結(jié)論相比較之下要比標(biāo)準(zhǔn)遺傳算法更加準(zhǔn)確。標(biāo)準(zhǔn)遺傳算法在多峰值情況下的尋優(yōu)會出現(xiàn)過早收斂，無法調(diào)出局部最優(yōu)的問題，尋優(yōu)結(jié)果不穩(wěn)定。相比較之下，基于災(zāi)變因子量子遺傳算法使用量子門對種群進(jìn)行更新，加入災(zāi)變因子，更快跳出局部最優(yōu)，有效阻止了局部最優(yōu)解的產(chǎn)生，由此可見，基于災(zāi)變因子的量子遺傳算法與標(biāo)準(zhǔn)遺傳算法相比，由于算法迅速地從某個局部區(qū)域中擺脫出來，并在新的解空間中進(jìn)行繼續(xù)的搜索，因而能大大改善了量子遺傳算法的收斂性。

4 結(jié)語

基于災(zāi)變因子量子遺傳算法是在遺傳算法的基礎(chǔ)上，將量子計算在計算方面的優(yōu)勢引入遺傳算法里，并且引入了災(zāi)變因子，彌補(bǔ)了傳統(tǒng)遺傳算法的缺陷，它仍屬于遺傳算法的范疇，但比遺傳算法的優(yōu)化性能高。

本文是通過把基于災(zāi)變因子的量子遺傳算法和遺傳算法分別應(yīng)用于三個測試函數(shù)進(jìn)行仿真測試，對測試結(jié)果進(jìn)行圖表分析，然后得出結(jié)論。所選的三個測試函數(shù)都是具有峰值的函數(shù)。從實驗的圖表中可以得出:

1）基于災(zāi)變因子的量子遺傳算法在對同一峰值函數(shù)進(jìn)行測試求解，所求得的最優(yōu)解的精確度會隨著其迭代次數(shù)的增大而提高。

2）基于災(zāi)變因子的量子遺傳算法對峰值函數(shù)進(jìn)行測試求解時，在相同的迭代次數(shù)下，用量子遺傳算法所求得的峰值函數(shù)的最大值的精確度要高于用遺傳算法所求得。

這表明了量子遺傳算法算法在連續(xù)空間優(yōu)化的可行性和有效性，同時也表明了量子遺傳算法算法具有良好的應(yīng)用前景。