改進量子遺傳算法在函數尋優中的應用

張　晨，譚小球，楊林峰

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

?

改進量子遺傳算法在函數尋優中的應用

張晨1，譚小球2，楊林峰1

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

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

量子遺傳算法；量子交叉；退火操作；尋優區域

引用格式：張晨，譚小球，楊林峰. 改進量子遺傳算法在函數尋優中的應用[J].微型機與應用，2016,35(11)：83-86.

0　引言

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

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

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

1　量子遺傳算法

1.1量子編碼

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

在量子遺傳算法中的量子位可以是|0>到|1>中的任意值，所以一個量子位的狀態的表達式可以為[6]：

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

(1)

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

|α|2+|β|2=1

(2)

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

1.2染色體表示方法

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

(3)

2　量子遺傳算法的改進

2.1量子交叉

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

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

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

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

表1 量子染色體結構表1A(1)A(2)A(3)A(4)A(5)2B(1)B(2)B(3)B(4)B(5)3C(1)C(2)C(3)C(4)C(5)表2 交叉后量子染色體結構表1A(1)C(2)B(3)A(4)C(5)2B(1)A(2)C(3)B(4)A(5)3C(1)B(2)A(3)C(4)B(5)

2.2模擬退火操作

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

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

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

(2)對種群完成步驟(3)～(6)。

(3)產生新的解S′。

(4)計算增量Δ=E(S′)-E(S),其中E(S)為目標函數。

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

(6)如果滿足終止條件則輸出當前解作為最優解，結束循環。

(7)產生新的溫度T′=0.95×T，逐步降低T(溫度)。

(8)轉到步驟(2)。

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

2.3二次尋優計算

2.3.1粗格子點法

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

2.3.2二次尋優計算方式

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

2.3.3二次尋優計算區域

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

圖1　二次尋優計算區域

在圖1中，如果a

2.4改進算法選擇

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

2.5優化算法流程

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

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

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

(4)記錄最優個體和對應的適應度。

(5)判斷優化算法是否可以結束優化操作，如果現有的優化解集滿足優化結束的條件則執行步驟(12)，否則繼續執行優化操作。

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

(7)對各確定解進行適應度評估。

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

(9)對量子染色體進行全干擾的量子交叉操作。

(10)記錄最優個體和對應的適應度。

(11)將迭代次數t加1，返回步驟(5)。

(12)確定二次優化解集區域，并將算法迭代次數減半，修正退火系數。

(13)根據第一次優化方法，執行步驟(1)～(11)。

3　算法性能測試

3.1典型測試函數

(1)多峰函數Shubert[8]

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

(2)Goldsten-Price函數[9]

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

(3)Six-hump Camel Back函數

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

Six-hump Camel Back函數有多個相似極小值點，很難準確地取得最小值點，其中(-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。

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

表3　仿真實驗數據比較表

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

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

3.2二次尋優計算測試

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

表4　二次尋優計算性能比較表

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

4　結論

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

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

參考文獻

[1] 梁昌勇，柏樺，蔡美菊，等.量子遺傳算法研究進展[J].計算機應用研究，2012,29(7)：2401-2405.

[2] 周傳華，錢鋒.改進量子遺傳算法及其應用[J].計算機應用，2008,28(2)：286-288.

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

[4] 何兵.基于改進量子遺傳算法的巡航導彈水平航跡規劃[J].計算機仿真，2012,29(9):109-112.

[5] 張濟濤，樊靜波，高亮．基于量子遺傳算法的拆除序列規劃[J]．現代制造工程，2015(4)：110-115.

[6] 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.

[8] 席紅雷．自適應梯度小環境混合優化算法[J]．計算機與數字工程，2012,40(2):37-39.

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

Application of improved quantum genetic algorithm in function optimization

Zhang Chen1，Tan Xiaoqiu2，Yang Linfeng1

(1.School of Computer, Electronics & Information, Guangxi University, Nanning 530004, China; 2.School of Mathematics, Physical and Information, Zhejiang Ocean University, Zhoushan 316000, China)

Ordinary quantum genetic algorithm has the tendency to fall into local optimum and has the disadvantage of accuracy is not high for a wide range of areas. Quantum genetic algorithm with the quantum crossover and annealing operation can efficiently avoid falling into local optimum. According to the optimization results of the first time, the algorithm optimization area is reduced, and the accuracy of the optimization algorithm is improved. Finally, the paper uses complex function of two variables to test the improved quantum genetic algorithm, the result proves that the improved quantum genetic algorithm has higher efficiency.

quantum genetic algorithm; quantum crossover; annealing operation; optimization area

TP319

A

10.19358/j.issn.1674- 7720.2016.11.025

2016-01-04)

張晨(1992-)，男，碩士研究生，主要研究方向：計算機應用技術。

譚小球(1974-)，男，博士，副教授，主要研究方向：智能優化及自然語言處理。

楊林峰(1979-)，男，博士，副教授，主要研究方向：并行計算最優化、混合整數規劃算法及其在電力系統中的應用。