(1.廣西大學 計算機與電子信息學院，廣西 南寧 530004；2.浙江海洋學院 數(shù)理與信息學院，浙江 舟山 316000)

　　摘要：標準的量子遺傳算法容易陷入局部最優(yōu)，且在定義域范圍較廣的函數(shù)尋優(yōu)中易出現(xiàn)優(yōu)化精度不高的情況。將量子交叉與模擬退火操作適當?shù)丶尤肓孔舆z傳算法中可以有效地避免算法陷入局部最優(yōu)解。根據(jù)第一次的優(yōu)化結果，縮小算法尋優(yōu)區(qū)域，以提高算法尋優(yōu)的精確度。最后對其用復雜二元函數(shù)進行測試，計算結果表明，通過該改進方式明顯提高了優(yōu)化算法的性能。

　　關鍵詞：量子遺傳算法；量子交叉；退火操作；尋優(yōu)區(qū)域

0引言

　　量子遺傳算法［1］（Quantum Genetic Algorithm，QGA）是將經典量子計算與傳統(tǒng)遺傳算法的操作方式相互融合產生的新的優(yōu)化算法。與傳統(tǒng)遺傳算法相比，量子遺傳算法具有種群多樣性好、全局搜索能力強和收斂速度快等特點［2］。

　　標準的量子遺傳算法在一些特別復雜的、病態(tài)的優(yōu)化函數(shù)中不能充分地發(fā)揮其優(yōu)越的性能。為了提高算法的優(yōu)化性能，本文將模擬退火操作與量子交叉操作引入標準量子遺傳算法中。該算法在量子個體上實施量子交叉操作，增強種群中染色體的結構信息交流，引入退火思想盡量避免算法在早期時陷入局部極值［3］。在實施第一輪尋優(yōu)計算操作后，求出相應的最優(yōu)解，再在最優(yōu)解附近的小范圍內進行第二輪尋優(yōu)計算，提高算法的尋優(yōu)精確度。

　　針對改進后的量子遺傳算法，本文用幾個復雜二元函數(shù)進行測試，結果表明，改進后的算法具有較強全局搜索［4］的特點。

1量子遺傳算法

　　1.1量子編碼

　　量子遺傳算法的編碼方式是量子編碼。量子編碼中，信息的存儲單元是量子比特［5］。采用|0>和|1>的單量子比特的疊加態(tài)來表示遺傳信息。

　　在量子遺傳算法中的量子位可以是|0>到|1>中的任意值，所以一個量子位的狀態(tài)的表達式可以為［6］：

　　|ρ>=λ|0>+μ|1>(1)

　　其中量子態(tài)的概率幅λ與μ是一對平方和為1的復數(shù)。對優(yōu)化種群進行一次測量操作，|ρ>可能會以|λ|2的概率坍縮到| 0>狀態(tài)，或者會以|μ|2的概率坍縮到|1>的狀態(tài)，并且它們滿足下面的表達式條件：

　　|α|2+|β|2=1(2)

　　在式(2)中，|α|2表示|0>的概率，|β|2表示|1>的概率，量子態(tài)坍縮是為了結合適應度值來優(yōu)選種源。因此，如果一個系統(tǒng)有m個量子位，則該系統(tǒng)可同時描述2m個狀態(tài)。然而，對于量子態(tài)［4］的每一次觀察，該量子位都只會坍縮到一個確定的狀態(tài)。

　　1.2染色體表示方法

　　在量子遺傳算法中，基因采用量子比特來表示［5］。該基因可以是“0”態(tài)或“1”態(tài)，也可以是它們之間的任意疊加態(tài)，即每一個基因位代表的不再是某一確定的遺傳信息，而是包含該優(yōu)化函數(shù)所需要的所有的優(yōu)化解集信息。因此，對于任意基因位的任一操作都可能會使種群中所有的優(yōu)化解集信息產生變化。本文使用一對平方和為1的復數(shù)對(α,β)來表示染色體中的一個量子比特，則 c個j位基因構成的一個染色體可以表示為：

　　式中，i是染色體的編號，n是染色體當前進化的代數(shù)，c是基因位的個數(shù)，第n代第i個個體的染色體用qni描述；j是每個用二進制表示的優(yōu)化解中含有的量子比特數(shù)。

2量子遺傳算法的改進

　　2.1量子交叉

　　在標準的量子遺傳算法中，沒有量子交叉，種群中染色體都相互獨立，個體間的結構信息不能被充分利用。

　　參考文獻［7］采用一種叫做“全局干擾交叉”的交叉操作，在該交叉操作中所有的染色體都參與其中。表1簡單地描述了本文中量子交叉方式，即該種群的大小為3，染色體的個數(shù)為3，每個染色體的長度為5。

　　其中第二個染色體的第2個量子比特用B（2）來表示，用遞歸的方式來進行全局干擾操作。交叉后的染色體的基因位的確定方法是：交叉前的基因位以現(xiàn)在的基因位序號大小減1在種群中向下移動幾位，如果移動的位數(shù)超過種群染色體數(shù)則除以現(xiàn)在種群的大小，然后取得的余數(shù)減1就是該基因向下移動的位數(shù)。

　　表2所示是經過全局干擾交叉操作后的染色體組，如：B（1）—A（2）—C（3）—B（4）—A（5）。通過此類操作，優(yōu)化種群中每個染色體上的量子位信息將會被充分利用，在種群演化的后期能夠充分保證染色體的多樣性，提高了算法的性能。

　　2.2模擬退火操作

　　模擬退火操作是通過設置初始溫度的大小與現(xiàn)實降溫過程的速率來實現(xiàn)的。在溫度較高時，算法能夠以較高的概率接受差的優(yōu)化解，而溫度較低時能較好地接受好的優(yōu)化解，通過此操作使算法避免陷入局部極值。模擬退火的搜索模式提高了算法的搜索能力和效率。

　　模擬退火算法實際上是一種迭代求解的過程，算法反復執(zhí)行“產生新狀態(tài)計算目標函數(shù)判斷是否接受新狀態(tài)接受/舍棄”的過程。它的基本流程如下：

　　(1)初始化，初始溫度T，初始解S，每個T值的迭代次數(shù)。

　?。?）對種群完成步驟（3）~（6）。

　?。?）產生新的解S′。

　?。?）計算增量Δ=E(S′)－E(S),其中E(S)為目標函數(shù)。

　　（5）若Δ<0，則接受S′作為新的當前解，否則以概率exp(－Δ/T)接受S′為新的當前解。

　　（6）如果滿足終止條件則輸出當前解作為最優(yōu)解，結束循環(huán)。

　?。?）產生新的溫度T′=0.95×T，逐步降低T（溫度）。

　?。?）轉到步驟（2）。

　　在算法的執(zhí)行過程中，為了保證算法的收斂能力，要保證退火的初始溫度T盡可能的大，一般情況下T取值為100。

　　2.3二次尋優(yōu)計算

　　2.3.1粗格子點法

　　粗格子點法是先用少數(shù)的格子點進行粗糙計算，在求出相應的最優(yōu)解后，再在最優(yōu)解附近的小范圍內進一步細分，并求在細分格子點上的最優(yōu)解，如此繼續(xù)細分直到滿足要求為止。

　　2.3.2二次尋優(yōu)計算方式

　　二次尋優(yōu)計算方式與粗格子點法相似。二次尋優(yōu)計算是第一次尋優(yōu)計算后在得到的最優(yōu)解附近的小范圍內再利用量子遺傳算法進行尋優(yōu)計算操作。優(yōu)點在于優(yōu)化函數(shù)定義域縮小，最優(yōu)值所在的區(qū)域更加明顯，染色體解的精度更高。

　　2.3.3二次尋優(yōu)計算區(qū)域

　　二次尋優(yōu)計算區(qū)域為第一次尋優(yōu)計算時每代的最優(yōu)值解組成的連續(xù)區(qū)域集合。如下圖1所示，以第一次尋優(yōu)計算的全局最優(yōu)解A為中心點，以中心點到邊界點B的距離為長度，確定該方向上二次尋優(yōu)計算的區(qū)間。

　　在圖1中，如果a<b,則將該方向上二次尋優(yōu)計算區(qū)域的二分之一大小設置為a,否則，設置為b。同理確定各個方向上變量的二次尋優(yōu)計算的區(qū)域大小。該方式縮小了算法二次尋優(yōu)計算的區(qū)域，提高了算法尋優(yōu)精確度。

　　2.4改進算法選擇

　　每個改進的量子遺傳算法都具有不同的尋優(yōu)計算特性。如果在第一次優(yōu)化計算函數(shù)時，發(fā)現(xiàn)全局最優(yōu)解的出現(xiàn)代數(shù)較小，且尋優(yōu)效果不佳，多數(shù)情況是由于算法的“早熟收斂”造成的。因此，在下次的尋優(yōu)計算時，可以將退火操作引入算法中，防止算法的“早熟收斂”。如果出現(xiàn)最優(yōu)解的迭代次數(shù)較晚，且尋優(yōu)效果較差，多數(shù)情況是由于各染色體過于孤立，染色體結構信息交流少，收斂速度慢造成的。因此，在下次尋優(yōu)計算時，將量子交叉操作引入優(yōu)化算法中，增加種群的多樣性，提高算法的尋優(yōu)性能。使用二次尋優(yōu)計算，可以有效地提高算法尋優(yōu)的精度。

　　2.5優(yōu)化算法流程

　　改進量子遺傳算法（IQGA）流程主要分為以下步驟：

　?。?）對初始種群Q（t0）進行函數(shù)優(yōu)化解集種群的初始化操作,初始溫度T，(αij,βij)描述的是所有優(yōu)化解集種群中每個染色體上的一個基因位，(2/2,2/2)是它們的初始大小。

　?。?）對初始種群中的每個個體進行一次測量，得到對應確定的解P(t0)。

　?。?）對各確定染色體優(yōu)化解P(t0)進行適應度評估操作，以此來得到每個解的適應度值的大小，用來進行下一步的遺傳淘汰選擇操作。

　?。?）記錄最優(yōu)個體和對應的適應度。

　?。?）判斷優(yōu)化算法是否可以結束優(yōu)化操作，如果現(xiàn)有的優(yōu)化解集滿足優(yōu)化結束的條件則執(zhí)行步驟（12），否則繼續(xù)執(zhí)行優(yōu)化操作。

　　（6）對優(yōu)化解集種群Q(t)中的每個個體即染色體優(yōu)化解進行一次染色體基因位大小的確定操作，通過此操作得到對應遺傳代數(shù)種群的函數(shù)優(yōu)化解集。

　　（7）對各確定解進行適應度評估。

　?。?）利用量子旋轉門U(t)對每個染色體個體進行一次遺傳演化操作，若當代全局適應度值與前代適應度值之差Δ小于零，則接受當代最優(yōu)個體作為新的當前解，以此得到新的優(yōu)化函數(shù)的最優(yōu)解集種群Q(t+1)，否則以概率exp(－Δ/T)接受新的當前解，以此得到新的優(yōu)化函數(shù)的最優(yōu)解集種群Q(t+1)。

　?。?）對量子染色體進行全干擾的量子交叉操作。

　?。?0）記錄最優(yōu)個體和對應的適應度。

　?。?1）將迭代次數(shù)t加1，返回步驟(5)。

　?。?2）確定二次優(yōu)化解集區(qū)域，并將算法迭代次數(shù)減半，修正退火系數(shù)。

　　（13）根據(jù)第一次優(yōu)化方法，執(zhí)行步驟（1）~（11）。

3算法性能測試

　　3.1典型測試函數(shù)

　　（1）多峰函數(shù)Shubert［8］

　　f1(x1,x2)=min∑5i=1icos［(i+1)x1+i］·

　　∑5i=1icos［(i+1)x2+i］

　　此函數(shù)具有760個局部極小值，其中全局最小值18個，理論上的全局最小解fmin(x1,x2)=－186.731。

　?。?）Goldsten-Price函數(shù)［9］

　　f2(x1,x2)=［1+(x1+x2+1)2(19－14x1+3x21－14x2+6x1x2+3x22)］*［30+(2x1－3x2)2(18－32x1+12x21+48x2-36x1x2+27x22)］，-2≤x1,x2≤2

　　此函數(shù)在其定義域內只有一個極小值點f2(0,－1)=3。

　?。?）Sixhump Camel Back函數(shù)

　　f3(x,y)=(4－2.1x2+x4/3)x2+xy+(－4+4y2)y2，-3≤x≤3，－2≤y≤2

　　Sixhump Camel Back函數(shù)有多個相似極小值點，很難準確地取得最小值點，其中(-0.089 8，0.712 6)和(0.089 8，-0.712 6)為全局最小點，最小值為f3(－0.089 8,0.712 6)=－1.031 628和f3(0.089 8,－0.712 6)=－1.031 628。

　　本文采用的方法與現(xiàn)有方法的計算結果對比如表3所示，每個函數(shù)分別用改進后的算法計算20次。量子遺傳算法的種群大小設置為40，迭代次數(shù)設置為200，函數(shù)的每個變量的二進制長度設置為20，退火初始溫度設置為100℃，退火系數(shù)為0.95。算法的優(yōu)化性能從算法的效率與算法質量兩個方面進行評價。

　　注：QGA為基本量子遺傳算法；CQGA為含量子交叉的算法；SQGA為含退火操作的算法；SCQGA為基于量子交叉與退火操作的算法

　　根據(jù)表3數(shù)據(jù)可以看出，改進后的量子遺傳算法在性能上有了一定的提高。針對不同的優(yōu)化函數(shù)，改進算法都體現(xiàn)了其優(yōu)越的性能。含量子交叉與退火思想的量子遺傳算法對于不同特點的優(yōu)化函數(shù)都能保持較好的搜索能力。

　　3.2二次尋優(yōu)計算測試

　　為測試二次尋優(yōu)計算的性能，利用上文提及的3個典型函數(shù)進行性能測試。將最大遺傳代數(shù)設置為100，染色體長度為20，種群大小為40。計算結果和對照比較內容如表4所示。 

　　從表4可以看出，二次尋優(yōu)計算得到的全局最優(yōu)值比第一次得到的解更加接近理論最優(yōu)值，并且收斂速度更快。

　　4結論

　　本文通過在原有的量子遺傳中添加全干擾的量子交叉與退火操作，提高了量子遺傳算法的搜索尋優(yōu)能力，有效地避免傳統(tǒng)算法易陷入“早熟收斂”與局部極值的問題。本文使用的二次尋優(yōu)計算提高了算法的精確度。

　　但是，本文的研究還有很多需要改進的地方，比如，在二次優(yōu)化時優(yōu)化區(qū)域的確定過于單一，沒有加入權值，可以考慮在優(yōu)化時對每代的最優(yōu)值賦權值，根據(jù)權值來確定二次優(yōu)化的尋優(yōu)區(qū)域；可以將全局交叉設置為概率交叉，在不影響性能的情況下減少交叉次數(shù)；可以使用并行算法縮減含量子交叉操作的量子遺傳算法的運行時間。因此，本文的后續(xù)工作是在現(xiàn)有基礎上改進和完善優(yōu)化算法，使其能更好地進行函數(shù)尋優(yōu)。

參考文獻

　?。?］ 梁昌勇，柏樺，蔡美菊，等.量子遺傳算法研究進展［J］.計算機應用研究，2012,29（7）：24012405.［2］ 周傳華，錢鋒.改進量子遺傳算法及其應用［J］.計算機應用，2008,28(2)：286288.

　?。?］ 郭海燕，金煒東，李麗，等．分組量子遺傳算法及其應用［J］．西南科技大學學報，2004，19(1)：1821.

　?。?］ 何兵.基于改進量子遺傳算法的巡航導彈水平航跡規(guī)劃［J］.計算機仿真，2012,29(9):109112.

　　［5］ 張濟濤，樊靜波，高亮．基于量子遺傳算法的拆除序列規(guī)劃［J］．現(xiàn)代制造工程，2015(4)：110115.

　?。?］ HAN K H. Genetic quantum algorithm and its application to combinatorial optimization problem［C］. In: IEEE Proc. of the 2000 Congress on Evolutionary Computation, San Diego, USA, 2000:13541360.

　　［7］ 祁正萍，孫合鳴．一種改進的量子遺傳算法［J］．科學技術與工程，2012，12(12)：28352839.

　?。?］ 席紅雷．自適應梯度小環(huán)境混合優(yōu)化算法［J］．計算機與數(shù)字工程，2012,40(2):3739.

　　［9］ 李敏強，寇紀淞．遺傳算法的基本理論與應用［M］．北京：科學出版社，2002.