張　晨，譚小球，楊林峰

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

?

改進(jìn)量子遺傳算法在函數(shù)尋優(yōu)中的應(yīng)用

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

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

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

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

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

0　引言

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

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

針對(duì)改進(jìn)后的量子遺傳算法，本文用幾個(gè)復(fù)雜二元函數(shù)進(jìn)行測(cè)試，結(jié)果表明，改進(jìn)后的算法具有較強(qiáng)全局搜索[4]的特點(diǎn)。

1　量子遺傳算法

1.1量子編碼

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

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

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

(1)

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

|α|2+|β|2=1

(2)

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

1.2染色體表示方法

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

(3)

2　量子遺傳算法的改進(jìn)

2.1量子交叉

在標(biāo)準(zhǔn)的量子遺傳算法中，沒(méi)有量子交叉，種群中染色體都相互獨(dú)立，個(gè)體間的結(jié)構(gòu)信息不能被充分利用。

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

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

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

表1 量子染色體結(jié)構(gòu)表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 交叉后量子染色體結(jié)構(gòu)表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模擬退火操作

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

模擬退火算法實(shí)際上是一種迭代求解的過(guò)程，算法反復(fù)執(zhí)行“產(chǎn)生新?tīng)顟B(tài)→計(jì)算目標(biāo)函數(shù)→判斷是否接受新?tīng)顟B(tài)→接受/舍棄”的過(guò)程。它的基本流程如下：

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

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

(3)產(chǎn)生新的解S′。

(4)計(jì)算增量Δ=E(S′)-E(S),其中E(S)為目標(biāo)函數(shù)。

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

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

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

(8)轉(zhuǎn)到步驟(2)。

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

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

2.3.1粗格子點(diǎn)法

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

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

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

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

二次尋優(yōu)計(jì)算區(qū)域?yàn)榈谝淮螌?yōu)計(jì)算時(shí)每代的最優(yōu)值解組成的連續(xù)區(qū)域集合。如下圖1所示，以第一次尋優(yōu)計(jì)算的全局最優(yōu)解A為中心點(diǎn)，以中心點(diǎn)到邊界點(diǎn)B的距離為長(zhǎng)度，確定該方向上二次尋優(yōu)計(jì)算的區(qū)間。

圖1　二次尋優(yōu)計(jì)算區(qū)域

在圖1中，如果a

2.4改進(jìn)算法選擇

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

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

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

(2)對(duì)初始種群中的每個(gè)個(gè)體進(jìn)行一次測(cè)量，得到對(duì)應(yīng)確定的解P(t0)。

(3)對(duì)各確定染色體優(yōu)化解P(t0)進(jìn)行適應(yīng)度評(píng)估操作，以此來(lái)得到每個(gè)解的適應(yīng)度值的大小，用來(lái)進(jìn)行下一步的遺傳淘汰選擇操作。

(4)記錄最優(yōu)個(gè)體和對(duì)應(yīng)的適應(yīng)度。

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

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

(7)對(duì)各確定解進(jìn)行適應(yīng)度評(píng)估。

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

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

(10)記錄最優(yōu)個(gè)體和對(duì)應(yīng)的適應(yīng)度。

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

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

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

3　算法性能測(cè)試

3.1典型測(cè)試函數(shù)

(1)多峰函數(shù)Shubert[8]

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

(2)Goldsten-Price函數(shù)[9]

此函數(shù)在其定義域內(nèi)只有一個(gè)極小值點(diǎn)f2(0,-1)=3。

(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ù)有多個(gè)相似極小值點(diǎn)，很難準(zhǔn)確地取得最小值點(diǎn)，其中(-0.089 8，0.712 6)和(0.089 8，-0.712 6)為全局最小點(diǎn)，最小值為f3(-0.089 8,0.712 6)=-1.031 628和f3(0.089 8,-0.712 6)=-1.031 628。

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

表3　仿真實(shí)驗(yàn)數(shù)據(jù)比較表

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

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

3.2二次尋優(yōu)計(jì)算測(cè)試

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

表4　二次尋優(yōu)計(jì)算性能比較表

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

4　結(jié)論

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

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

參考文獻(xiàn)

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

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

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

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

[5] 張濟(jì)濤，樊靜波，高亮．基于量子遺傳算法的拆除序列規(guī)劃[J]．現(xiàn)代制造工程，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ìn)的量子遺傳算法[J]．科學(xué)技術(shù)與工程，2012，12(12)：2835-2839.

[8] 席紅雷．自適應(yīng)梯度小環(huán)境混合優(yōu)化算法[J]．計(jì)算機(jī)與數(shù)字工程，2012,40(2):37-39.

[9] 李敏強(qiáng)，寇紀(jì)淞．遺傳算法的基本理論與應(yīng)用[M]．北京：科學(xué)出版社，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-)，男，碩士研究生，主要研究方向：計(jì)算機(jī)應(yīng)用技術(shù)。

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

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