許 波,彭志平,余建平,柯文德
(1.廣東石油化工學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系,廣東茂名525000;2.廣東高校石油化工過程裝備故障診斷與信息化控制工程技術(shù)開發(fā)中心,廣東茂名525000;3.湖南師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,長沙 410081)
量子遺傳算法(QGA)是近年發(fā)展起來的一種基于量子計(jì)算[1]原理的概率優(yōu)化算法,主要是在遺傳算法(GA)中引入量子計(jì)算的一些概念,使遺傳操作更有效,具有種群規(guī)模小但不影響算法性能,同時(shí)兼有全局尋優(yōu)能力強(qiáng)和收斂速度快的特點(diǎn)。Narayanan等[2]首次將量子計(jì)算理論與進(jìn)化算法相結(jié)合,提出了QGA的概念,Han K H等[3~5]將QGA用于典型組合優(yōu)化問題——背包問題,實(shí)現(xiàn)了組合優(yōu)化問題的求解,之后關(guān)于QGA的研究成果大量出現(xiàn)在各種學(xué)術(shù)會(huì)議與期刊中。張葛祥等[6]提出一種新量子遺傳算法(NQGA),其核心是采用自適應(yīng)調(diào)整搜索網(wǎng)格的策略與量子比特相位比較法更新量子門。李盼池[7]則利用實(shí)數(shù)變量和量子位構(gòu)成實(shí)數(shù)染色體,并設(shè)計(jì)了互補(bǔ)變異算子來進(jìn)化染色體。李士勇等[8,9]針對QGA不適于連續(xù)函數(shù)優(yōu)化的問題,提出改進(jìn)的QGA,直接將量子染色體與當(dāng)前最優(yōu)解相比較來確定旋轉(zhuǎn)門的旋轉(zhuǎn)角,種群中各個(gè)體以不同速率向最優(yōu)解進(jìn)化,以同時(shí)實(shí)現(xiàn)全局搜索與局部搜索,引入變異操作以防止算法早熟收斂。張亮等[10]提出一種基于球面解空間劃分的QGA,引入多區(qū)域并行搜索機(jī)制,制定了群間的染色體置換策略,設(shè)計(jì)了新的量子變異操作,并以種群退化的程度來確定變異的概率。目前國內(nèi)外各種QGA中有關(guān)量子旋轉(zhuǎn)門旋轉(zhuǎn)角的方向和大小幾乎都是基于查表法,涉及多路條件判斷,從而影響了算法的效率[11];變異概率大多采用給定的方式并且在進(jìn)化過程中不作調(diào)整[12]。
2003年,Eusuff等結(jié)合混合競爭進(jìn)化的思想在粒子群算法的基礎(chǔ)上提出了混合蛙跳算法(SFLA)[13,14]。SFLA是有限度隨機(jī)搜索與確定性競爭進(jìn)化策略的有機(jī)結(jié)合,是一種新型的仿生進(jìn)化算法。目前該算法已經(jīng)在一些經(jīng)典組合優(yōu)化問題上取得成功應(yīng)用。為此,本文提出一種基于蛙跳思想的量子編碼遺傳算法(QRGA),該算法采用自適應(yīng)的方式對量子旋轉(zhuǎn)門旋轉(zhuǎn)角進(jìn)行調(diào)整,并基于模糊邏輯將蛙跳的步長進(jìn)行量化以指導(dǎo)變異概率調(diào)整,保證進(jìn)化的方向性和提高算法效率。
在QRGA中,染色體采用量子位表示,一個(gè)量子位的狀態(tài)可表示為
一個(gè)量子位可能處于0或1,或者處于0和1之間的中間態(tài),即0和1的不同疊加態(tài),其中α和β是復(fù)數(shù),表示相應(yīng)狀態(tài)的概率幅,且滿足下列歸一化條件
式(2)中,|α|2表示 |0> 的概率,|β|2表示 |1> 的概率。定義隨機(jī)生成的量子染色體群P={P1,P2,…,PF},其中采用量子比特幅編碼的染色體結(jié)構(gòu)如下
式(3)中,m為染色體基因個(gè)數(shù)。
初始化時(shí),令所有個(gè)體基因位的概率幅(α1,β1)都為(),這意味著整個(gè)解空間中所有可能解的取值概率相同,可行解是通過對一個(gè)用概率幅編碼的量子染色體進(jìn)行“測量”來獲得的,某一位在某一次“測量”中取“0”還是取“1”的概率由其相應(yīng)概率幅大小決定。測量過程是對一個(gè)用概率幅編碼的染色體進(jìn)行測量獲得的一個(gè)確定的二進(jìn)制表示的解。把每個(gè)量子染色體看成一個(gè)青蛙,那么對于量子染色體群P={P1,P2,…,PF}可看成含有F個(gè)青蛙的群體,對于解為t維的問題,第i個(gè)青蛙的位置為Xi=[xi1,xi2,…,xit]。生成群體之后,計(jì)算每個(gè)青蛙位置的適應(yīng)度值f(Xi),將其從大到小進(jìn)行排序。將排序后的青蛙按式(4)平均分配到m個(gè)族群,每個(gè)族群有k個(gè)青蛙,因此有F=m×k
式(4)中,Mi為第i個(gè)族群,族群中適應(yīng)度函數(shù)值最小的青蛙位置用Xw表示。
量子門的構(gòu)造是QGA的關(guān)鍵問題。量子門的類型有很多,目前在QGA中主要采用的是量子旋轉(zhuǎn)門[10]
量子旋轉(zhuǎn)門的更新過程如下
式(5)和(6)中,Δθ為旋轉(zhuǎn)角,在更新的過程中,它的大小和符號起關(guān)鍵作用,太大可能使結(jié)果發(fā)散或早熟收斂到局部最優(yōu)解,太小又會(huì)影響收斂速度。
為更好地利用量子旋轉(zhuǎn)門,根據(jù)蛙跳的思想將Δθ的大小設(shè)置為動(dòng)態(tài)調(diào)整,大小與方向都不再使用傳統(tǒng)的查表方式,Δθ的具體計(jì)算方法如下
式(7)中,Xs為當(dāng)前族群適應(yīng)度最佳的青蛙位置;Xb為當(dāng)前整個(gè)群體適應(yīng)度最佳的青蛙位置;Xw為族群中適應(yīng)度函數(shù)值最小的青蛙位置;r1和r2為[0,1]內(nèi)的隨機(jī)數(shù)。利用式(7)自動(dòng)調(diào)整量子門旋轉(zhuǎn)角度的大小和方向。這樣做有兩個(gè)主要的優(yōu)點(diǎn):一是進(jìn)化方程具有記憶特性,不僅利用整個(gè)群體最優(yōu)狀態(tài)的信息,也利用當(dāng)前族群的局部最優(yōu)信息,從而更加合理地調(diào)整角度θ,具有更好跳出局部極值的能力;二是簡化了量子旋轉(zhuǎn)角更新過程,不涉及多路條件判斷。迭代更新后適應(yīng)度值為,如優(yōu)于原適應(yīng)度Xw,則用取代Xw;否則用式(8)代替
式(8)和(9)中,D為青蛙移動(dòng)步長;Dmax和Dmin分別為青蛙位置所允許移動(dòng)距離的最大值和最小值。
蛙跳算法中蛙跳的移動(dòng)步長大小直接影響著算法的全局收斂性。當(dāng)其較小時(shí),青蛙可在局部區(qū)域內(nèi)精細(xì)搜索,但容易陷入局部最優(yōu);當(dāng)其較大時(shí),有利于青蛙在全局范圍內(nèi)廣泛搜索,但有可能越過最優(yōu)解[15]。本文利用模糊邏輯的方法將D量化為3級,語言變量分別取為大、中、小。青蛙Pi變異概率pm調(diào)整策略需同時(shí)考慮青蛙Pi的D值、Pi當(dāng)前適應(yīng)度值f(Xi)、當(dāng)前整個(gè)群體適應(yīng)度最佳的青蛙適應(yīng)度值f(Xb)3個(gè)因素?,F(xiàn)定義規(guī)則如下。
1)若D為大且f(Xi)≥f(Xb),這表明當(dāng)前青蛙Pi優(yōu)于整個(gè)群體適應(yīng)度最佳的青蛙適應(yīng)度值,且當(dāng)前青蛙Pi有可能躍過最優(yōu)解,這不會(huì)影響到全局最優(yōu)解,因此變異概率pm不做調(diào)整。
2)若D為大且f(Xi)<f(Xb),這表明當(dāng)前青蛙Pi次于整個(gè)群體適應(yīng)度最佳的青蛙適應(yīng)度值,且當(dāng)前青蛙Pi有可能躍過最優(yōu)解,變異概率pm在原來的基礎(chǔ)上應(yīng)向增大的方向調(diào)整。
南通地處沿海,多次遭受外敵入侵,在家鄉(xiāng)面臨生死存亡的關(guān)鍵時(shí)刻,有許多普通的人物英勇地站了出來與敵人周旋,譜寫了許多可歌可泣的英雄壯舉。這些是今天學(xué)習(xí)先進(jìn)人物可以利用的資源,特別是學(xué)習(xí)英雄人物舍小家顧大家的高尚情懷,當(dāng)個(gè)人的訴求、利益與社會(huì)、國家的需要利益發(fā)生矛盾時(shí),能夠自覺以社會(huì)、國家的利益為重。
3)若D為中且f(Xi)≥f(Xb),這表明當(dāng)前青蛙Pi優(yōu)于整個(gè)群體適應(yīng)度最佳的青蛙適應(yīng)度值,且當(dāng)前青蛙Pi移動(dòng)步長的大小比較合適,變異概率pm不做調(diào)整。
4)若D為中且f(Xi)<f(Xb),這表明當(dāng)前青蛙Pi次于整個(gè)群體適應(yīng)度最佳的青蛙適應(yīng)度值,且當(dāng)前青蛙Pi移動(dòng)步長的大小比較合適,變異概率pm不做調(diào)整。
5)若D為小且f(Xi)≥f(Xb),這表明當(dāng)前青蛙Pi優(yōu)于整個(gè)群體適應(yīng)度最佳的青蛙適應(yīng)度值,且當(dāng)前青蛙Pi容易陷入局部最優(yōu),這會(huì)影響到局部搜索效果,變異概率pm在原來的基礎(chǔ)上向增大的方向調(diào)整。
6)若D為小且f(Xi)<f(Xb),這表明當(dāng)前青蛙Pi次于整個(gè)群體適應(yīng)度最佳的青蛙適應(yīng)度值,且當(dāng)前青蛙Pi容易陷入局部最優(yōu),這會(huì)影響到局部搜索效果,變異概率pm在原來的基礎(chǔ)上向增大的方向調(diào)整。具體變異概率選擇策略如表1所示。
表1 變異概率pm選擇策略Table 1 The selection strategy of mutation probability pm
為了充分考察和比較GA、文獻(xiàn)[10]的QGA、文獻(xiàn)[8]的雙鏈量子遺傳算法(DCQGA)和本文QRGA的性能,實(shí)驗(yàn)通過求解0/1背包問題與典型的數(shù)值優(yōu)化函數(shù)來對這4個(gè)算法進(jìn)行性能比較,以便于綜合比較算法在組合優(yōu)化以及數(shù)值優(yōu)化方面的收斂性及全局搜索能力。
針對傳統(tǒng)的典型組合優(yōu)化問題——0/1背包問題,本文對GA、QGA和QRGA進(jìn)行了對比實(shí)驗(yàn)。實(shí)驗(yàn)參數(shù)設(shè)置如下:GA種群規(guī)模設(shè)為50,交叉概率為0.95,變異概率為0.5;QGA種群規(guī)模設(shè)為50,量子變異概率為0.5,概率幅旋轉(zhuǎn)角度Δθ=0.001×pi;QRGA采用種群規(guī)模設(shè)為50,量子變異概率為0.5。圖1給出了3種算法迭代次數(shù)為500的某一次進(jìn)化曲線,圖2給出了3種算法迭代次數(shù)為300的某一次進(jìn)化曲線。
圖1 3種算法的進(jìn)化曲線對比(500次)Fig.1 The evolution curve comparison of the three algorithm s(500 statistics)
圖2 3種算法的進(jìn)化曲線對比(300次)Fig.2 The evolution curve comparison of the three algorithms(300 statistics)
在圖1和圖2中,QRGA、QGA、GA分別在150代、300代、500代附近找到其較優(yōu)解,且較優(yōu)解的值依次減小,這是因?yàn)镼RGA算法充分采用了旋轉(zhuǎn)角與變異概率的動(dòng)態(tài)調(diào)整策略,收斂速度最快,在150代已得到較優(yōu)解,且較優(yōu)解值要優(yōu)于QGA和GA,這充分體現(xiàn)了QRGA收斂速度快和全局搜索能力強(qiáng)的特點(diǎn)。
針對數(shù)值優(yōu)化問題,本文采用DCQGA和QRGA同時(shí)求解標(biāo)準(zhǔn)數(shù)值優(yōu)化問題,以測試本文算法在數(shù)值優(yōu)化方面的性能。選取的兩個(gè)典型的測試函數(shù)均來自于參考文獻(xiàn),為了更好地體現(xiàn)對比的可信性,測試函數(shù)F2選取文獻(xiàn)[8]中的測試函數(shù)。
測試函數(shù)2:F2(x,y)=0.5
此函數(shù)有無限個(gè)局部極大點(diǎn),其中只有(0,0)為全局最大,自變量取值范圍為(-100,100),對比實(shí)驗(yàn)結(jié)果如圖4和表2所示。
圖3 F1函數(shù)DCQGA和QRGA對比圖Fig.3 DCQGA and QRGA comparison chart of the F1 function
圖4 F2函數(shù)DCQGA和QRGA對比圖Fig.4 DCQGA and QRGA comparison chart of F2 function
表2 函數(shù)優(yōu)化結(jié)果對比(100次統(tǒng)計(jì)結(jié)果)Table 2 Results contrast of function optimization(100 statistical results)
圖3、圖4描繪了兩種算法在最優(yōu)值隨迭代數(shù)變化的情況,其中點(diǎn)畫線代表本文算法,表2給出了兩種算法在函數(shù)優(yōu)化的100次統(tǒng)計(jì)結(jié)果對比。從圖3、圖4以及表2可以看出,對于F1和F2,在進(jìn)化初期QRGA的收斂速度明顯優(yōu)于DCQGA,并且在整個(gè)進(jìn)化過程中QRGA始終保持較快的收斂速度,同時(shí)QRGA的求解質(zhì)量也優(yōu)于DCQGA。
綜上所述,本文的算法充分采用了旋轉(zhuǎn)角以及變異概率的動(dòng)態(tài)調(diào)整策略,使量子態(tài)的干涉性和糾纏性等優(yōu)勢特性得到更好的體現(xiàn),具有運(yùn)行時(shí)間短、收斂速度快、全局尋優(yōu)能力強(qiáng)等優(yōu)點(diǎn),能較好地適用組合優(yōu)化與數(shù)值優(yōu)化問題的要求。
本文提出一種基于蛙跳思想的QRGA,采用自適應(yīng)的方式對量子旋轉(zhuǎn)門旋轉(zhuǎn)角與變異概率進(jìn)行調(diào)整,保證了進(jìn)化的方向性和種群的多樣性,實(shí)驗(yàn)結(jié)果表明該算法能快速收斂到全局最優(yōu),在運(yùn)行時(shí)間以及解的質(zhì)量上取得了較好的效果。如何對算法的理論進(jìn)行分析以及拓寬算法在優(yōu)化問題中的應(yīng)用范圍將是下一步的研究方向。
[1] Tony H.Quantum computing:A ll Introductions[J].Computing&Control Engineering Journal,1996,l0(3):105-112.
[2] Narayanan A,Moore M.Quantum-Inspired Genetic A lgorithm[C]//Proceedings of IEEE International Conference on Evolutionary Computation.Piscataway,1996.
[3] Han K H,Park K H,Lee CH.Parallel quantum inspired genetic algorithm for combinatorial optimization problem[J].IEEE Transactions on Evolutionary Computation,2001,5(1):1422-1429.
[4] Guo J,Sun L,Wang R.An improved quantum genetic algorithm[J].Genetic and Evolutionary Computing,2009,10(1):14-18.
[5] Malossini A,Blanzieri E,Calarco T.Quantum genetic optimization[J].IEEE Transactions on Evolutionary Computation,2008,12(2):231-241.
[6] 張葛祥,李 娜,金煒東,等.一種新量子遺傳算法及其應(yīng)用[J].電子學(xué)報(bào),2004,32(3):476-479.
[7] 李盼池.基于量子位Bloch坐標(biāo)的量子遺傳算法及其應(yīng)用[J].控制理論與應(yīng)用,2008,25(6):985-989.
[8] 李士勇,李盼池.基于實(shí)數(shù)編碼和目標(biāo)函數(shù)梯度的量子遺傳算法[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào),2006,38(8):1216-1218,1223.
[9] 李士勇,李 浩.一種基于相位比較的量子遺傳算法[J].系統(tǒng)工程與電子技術(shù),2010,32(10):2219-2222.
[10] 張 亮,陸余良,楊國正,等.基于球面多區(qū)域劃分的并行量子遺傳算法[J].電子與信息學(xué)報(bào),2011,33(5):1035-1041.
[11] Zhao S,Xu G,Tao T.Real-coded chaotic quantum-inspired genetic algorithm for training of fuzzy neural networks[J].Computers and Mathematics with Applications,2009,57(11/12):2009-2015.
[12] Gu Jinwei,Gu Manzhan,Cao Cuiwen,et al.A novel competitive co-evolutionary quantum genetic algorithm for stochastic job shop scheduling problem[J].Computers and Operations Research,2010,37(5):927-937.
[13] 羅雪暉,楊 燁,李 霞.改進(jìn)混合蛙跳算法求解旅行商問題[J].通信學(xué)報(bào),2009,30(7):130-135.
[14] Sun X,Wang Z Q,Zhang D X.A web document classification method based on shuffled frog leaping algorithm[C]//Second International Conference on Genetic and Evolutionary Computing(WGEC 2003).Jingzhou,2008:205-208.
[15] 駱劍平,李 霞.求解TSP的改進(jìn)混合蛙跳算法[J].深圳大學(xué)學(xué)報(bào):理工版,2010,27(2):173-179.