一種改進的雙鏈量子遺傳算法及其應用

摘 要:針對目前雙鏈量子遺傳算法中保持種群多樣性和改善優化效率問題提出了三種改進方法。通過在量子比特概率幅三角函數表達式中引入常數因子，使搜索過程在多個周期上同時進行，以改善算法的優化效率;提出了一種基于單比特量子Hadamard的變異策略，可提高保持種群多樣性的概率;改進了量子旋轉門轉角步長函數，能夠有效避免算法震蕩，增強算法的適應性。以多變量函數極值優化問題為例，仿真實驗結果表明上述三種改進措施是有效的。

關鍵詞:量子計算; 量子遺傳算法; 優化算法

中圖分類號:TP183文獻標志碼:A

文章編號:1001-3695(2010)06-2090-03

doi:10.3969/j.issn.1001-3695.2010.06.027

Improved quantum genetic algorithm with double chains and its application

XU Shao-hua， XU Chen， HAO Xing， WANG Ying， LI Pan-chi

(School of Computer Information Technology， Daqing Petroleum Institute， Daqing Heilongjiang 163318， China)

Abstract:Aiming at the problems that how to keep population diversity and improve optimization efficiency in double chains quantum genetic algorithm， this paper proposed three improvements. Firstly， by adding the constant factor to the trigonometric expressions of quantum bit probability amplitudes， performed the search in a number of trigonometric functions cycle at the same time， which enhanced the optimization efficiency of the proposed algorithm. Secondly， the mutation strategy applying the single bit quantum Hadamard gates enhanced the diversity of population. Thirdly， enhanced the adaptability of the proposed algorithm by redesigning the step function of rotation angle of quantum rotation gates， and this also avoided the oscillation effectively. Finally， with application of function extremum optimization with multi-variables， the simulation results show that the three improvements are efficient.

Key words:quantum computing; quantum genetic algorithm(QGA); optimization algorithm

量子計算是信息科學和量子力學相結合的新興交叉學科，自1994年Shor提出第一個求解大數質因子分解的量子算法[1]和1996年Grover提出隨機數據庫搜索的量子算法[2]之后，量子計算以其獨特的計算性能引起了廣泛關注，迅速成為國際上研究的熱點[3～5]。量子遺傳算法(QGA)是一種基于量子計算原理的概率優化算法，它以量子計算的一些概念和理論為基礎，用量子位編碼來表示染色體，用量子門更新染色體來完成進化搜索，具有種群規模小、收斂速度快、全局搜索能力強的優點。目前，量子計算與遺傳算法的融合已呈現出眾多模式。Narayanan等人[6]首先提出了量子衍生遺傳算法并成功求解了TSP， 雖然該方法仍屬傳統遺傳算法， 但激發了量子計算原理與遺傳算法相結合的研究;Han等人[7]采用量子位編碼和量子門更新染色體，提出了遺傳量子算法和并行量子遺傳算法， 并成功求解了組合優化問題;Yang Jun-an等人[8]在遺傳算法中引入多宇宙概念，提出了多宇宙并行量子遺傳算法;Wang Ling等人[9]將QGA與SGA融合，提出基于量子計算的混合量子遺傳算法;李士勇等人[10]將量子染色體中兩條概率幅鏈均看成描述最優解的基因鏈，提出了雙鏈量子遺傳算法(double chains quantum genetic algorithm，DCQGA)，借助量子位相位的周期性，該算法在一定程度上能提高優化性能。本文在文獻[10]研究工作的基礎上，通過改變量子位概率幅的周期、旋轉角度以及變異策略，提出了一種改進的雙鏈量子遺傳算法(improved DCQGA，IDCQGA)。該方法可使搜索過程在概率幅的多個三角函數周期上同時進行，改善了原算法的種群多樣性、適應性和穩定性，從而進一步提高了算法的搜索能力。

1 IDCQGA基本原理

1.1 連續優化問題描述

若將n維連續空間優化問題的解看做n維空間中的點或向量，則連續優化問題可表述為

min f(x)=f(x1，x2，…，xn)s.t. ai≤xi≤bi;i=1，2，…，n(1)

若將約束條件看做n維連續空間中的有界閉集Ω，將Ω中每個點都看做優化問題的近似解，可定義如下評價函數來反映近似解的優劣程度:

fit(x)=Cmax-f(x)(2)

其中，Cmax可以是一個合適的輸入值，或者是到目前為止優化過程中f(x)的最大值。

1.2 雙鏈量子遺傳算法

在量子計算中，最小的信息單位用量子位表示。量子位又稱量子比特，一個量子比特的狀態可表示為

|φ〉=α|0〉+β|1〉(3)

其中α和β滿足下列歸一化條件:

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

把滿足式(3)(4)的一對復數α和β稱為一個量子比特的概率幅，因此量子比特也可以用概率幅表示為[α，β]T。

在DCQGA中，直接采用概率幅作為編碼。考慮到式(4)的約束性，編碼方案如下:

pi=cos(ti1)sin(ti1)cos(ti2)sin(ti2) …cos(tin)sin(tin)(5)

其中:tij=2π×rnd，rnd為(0，1)間的隨機數，i=1，2，…，m;j=1，2，…，n。m是種群規模，n是量子位數。在DCQGA中，將每一量子位的概率幅看做是上下兩個并列的基因，每條染色體包含兩條并列的基因鏈，而每條基因鏈代表一個優化解。因此，每次迭代兩個解同步更新，在種群規模不變的情況下能擴展對搜索空間的遍歷性，加速優化進程。

DCQGA使用量子旋轉門更新量子染色體的概率幅，其轉角步長公式為

Δθ=-sgn(A)×Δθ0×‖fit max-fit min‖‖fit(X)-fit min‖ (6)

其中:Δθ0為轉角步長初值;fit(X)為評價函數fit在點X的梯度;fti max和fit min分別定義為

fit max=[max{fit(X1)X11，…，

fit(Xm)X1m}，…，max{fit(X1)Xn1，…，fit(Xm)Xnm}](7)

fit min=[min{fit(X1)X11，…，fit(Xm)X1m}，…，

min{fit(X1)Xn1，…，fit(Xm)Xnm}](8)

DCQGA的變異策略為利用量子非門，兌換量子位的兩個概率幅，從而使雙鏈同時變異。

1.3 改進的雙鏈量子遺傳算法

本文針對上述DCQGA提出了三點改進策略。

1)量子染色體編碼方式的改進

在IDCQGA中，本文在量子位概率幅的三角函數描述中引入一個大于等于1的調整因子，將原來的2π周期改進為多周期描述方式。引進這一參數的直接目的是提高算法收斂的概率。改進后的編碼方式為

pi=cos(cti1)sin(cti1)cos(cti2)som(cti2) …cos(ctin)sin(ctin)(9)

其中c≥1。

這種編碼方式為每個量子位的相位附帶一個大于1的常數因子，從而拓展了概率幅函數的周期。該算法是對DCQGA的推廣，當c=1時，即還原為原來算法。假設在優化過程中最優解的某一變量對應的概率幅值為-0.5，以c=2為例，由圖1可知，原算法(c=1)有兩個相位解:q1=7π/6，q2=11π/6;新算法(c=2)有四個相位解:p1=7π/12，p2=11π/12，p3=19π/12，p4=23π/12。因此，提高了獲得最優解的概率。

2)量子旋轉門轉角步長函數的改進

式(6)存在如下不足:若fit(X)=fit min，則‖fit(X)-fit min‖=0，Δθ=∞，從而引起算法震蕩。鑒于此，本文提出如下轉角步長函數:

Δθ=-sgn(A)Δθ0 exp-f(X)-f minf max-f min(10)

上式既能保持與式(5)功能的一致性，也有效克服了原有的缺陷，提高了算法的適應性和穩定性。

3)基于量子非門的變異策略的改進

量子非門的作用是使量子位的兩個概率幅兌換，這種變異的本質是一種量子比特相位的旋轉。設某一量子位幅角為θ，則旋轉后的幅角為π/2-θ，幅角正向旋轉了π/2-2θ。經分析，實際上這種旋轉幅度中的π/2是沒有必要的，完全可以替換為其他角度。在IDCQGA中，本文提出了基于單比特量子Hadamard的變異策略，該門在單量子比特上的作用效果為

12111-1cos(θij)sin(θij)=

cos(π4-θij)sin(π4-θij)=cos(θij+π4-2θij)sin(θij+π4-2θij)(11)

其中:i∈{1，2，…，m}，j∈{1，2，…，n}。由式(11)可以看出，這種變異策略也是一種旋轉。對于第i條染色體上的第j個量子位，轉角大小為Δθij=π/4-2θij，增強了種群的多樣性。

2 對比實驗

為驗證IDCQGA中改進措施的有效性，考慮如下兩個典型函數的極值優化問題，并與DCQGA對比。

1)BR-Branin 函數

f(x，y)=x-5.14π2y2+5πy-62+101-18πcos y+10(12)

其中:x∈[0，15];y∈[-5，10]。

優化目標為求取函數極小值，式(12)的全局極小值為0.3979，共有兩個全局極小值點(-3.142，12.276)和(3.142，2.275)，一個與全局極小值點很接近的局部極小值點為(9.425，2.425)，局部極小值為0.400 4，其空間分布特征如圖2所示。當優化結果誤差小于0.000 4時認為算法收斂。

2)RA-Rastrigin函數

f(x，y)=x2+y2-cos(18x)-cos(18y)(13)

其中:x，y∈[-1，1]。

優化目標為求取函數極小值，式(13)全局極小值點為(0，0)，全局極小值為-2.000，在可行域內大約有50個局部極小值點，其空間分布特征如圖3所示。當優化結果誤差小于0.005時認為算法收斂。

3)Generalized Rosenbrock’s 函數

f3(X)=∑29i=1[100(xi+1-x2i)2+(1-xi)2](14)

其中:xi∈[-30，30]。

優化目標為求取函數極小值，式(14)全局極小值點為(1，1，…，1)，全局極小值為0。當優化結果小于0.005時認為算法收斂。

對于上述函數，分別用IDCQGA和DCQGA優化50次，然后統計每種算法的最優結果、平均結果、收斂次數、平均步數、平均時間作為對比評價指標。三種算法的種群規模均取50，最大優化代數均取500，變異概率均取0.05，轉角步長初值均取0.01π。性能對比結果如表1所示。

表1 IDCQGA、DCQGA算法的性能對比

函數算法最好結果平均結果收斂次數平均步數平均時間/s

BR-BraninIDCQGADCQGA0.397 90.397 90.399 10.399 6494655.040 066.440 00.030 30.037 7

RA-RastriginIDCQGADCQGA-2.000 0-2.000 0-1.994 9-1.993 7484559.220 072.560 00.029 70.031 1

GeneralizedRosenbrockIDCQGADCQGA0.000 00.000 00.025 30.038 64339138.230 0163.870 00.058 60.059 9

對比實驗結果表明，IDCQGA的優化性能優于DCQGA，從而表明本文提出的改進策略是有效可行的。

3 結束語

量子遺傳算法是量子計算與遺傳算法相結合的產物，目前作為一個新興的研究方向，受到國內外學者廣泛關注。本文針對目前雙鏈量子遺傳算法存在的問題，通過實施三種改進策略建立了一種新型的雙鏈量子遺傳算法，有效克服了原算法存在的不足，進一步提高了算法的搜索能力。仿真實驗結果驗證了本文提出的改進算法的有效性。

參考文獻:

[1]SHOR P W. Algorithms for quantum computation: discrete logarithms and factoring[C]//Proc of the 35th Annual Symposium on Foundations of Computer Science.Washingtom DC:IEEE Computer Society，1994:124-134.

[2]GROVER L K. A fast quantum mechanical algorithm for database search[C]//Proc of the 28th Annual ACM Symposium on the Theory of Computing.New York:ACM Press，1996:212-219.

[3]OGRYZKO V V. A quantum-theoretical approach to the phenomenon of directed mutations in bacteria (hypothesis)[J]. Biosystems，1997，43(2):83-95.

[4]HOGG T. A framework for structured quantum search [J].Physica D，1998，120(1-2):102-116.

[5]LONG Gui-lu， LI Yan-song， LIN Wei，et al. Phase matching in quantum searching [J]. Physics Letters A，1999，262(1):27-34.

[6]NARAYANAN A， MOORE M. Quantum-inspired genetic algorithm[C]//Proc of IEEE International Conference on Evolutionary Computation. Piscataway:IEEE Press，1996:61-66.

[7]HAN Kuk-hyun， PARK Kui-hong， LEE Chi-lee，et al. Parallel quantum-inspired genetic algorithm for combinatorial optimization problems[C]//Proc of IEEE Congress on Evolutionary Computation. Piscata-way: IEEE Press，2001:1442-1429.

[8]YANG Jun-an，LI Bin，ZHUANG Zhen-quan.Multi-universe parallel quantum genetic algorithm its application to blind-source separation[C]//Proc of IEEE International Conference on Neural Networks Signal Processing.2003:393-398.

[9]WANG Ling， TANG Fang， WU Hao. Hybrid genetic algorithm based on quantum computing for numerical optimization and parameter estimation[J].Applied Mathematics and Computation，2005，171(2):1141-1156.

[10]李士勇，李盼池.基于實數編碼和目標函數梯度的量子遺傳算法[J].哈爾濱工業大學學報，2006，38(8):1216-1218，1223.