量子遺傳算法的變尺度混沌優化策略研究
2009-01-01 00:00:00滕皓邵闊義曹愛增楊炳儒
計算機應用研究 2009年2期
(1.北京科技大學 信息工程學院， 北京 100083；2.濟南大學 信息科學與工程學院， 濟南 250022；3.北京銀聯商務有限公司， 北京 100048)
摘 要：針對量子遺傳算法（QGA）易陷入局部極值、具有早熟收斂等問題，分析了QGA的流程，從全局搜索和局部搜索兩個層面探討了QGA的改進策略，提出了一種新的算法。該算法利用混沌運動的遍歷性和隨機性進行全局搜索，同時利用梯度信息對QGA的量子更新過程環節進行優化。典型函數測試分析表明，該方法的綜合性能明顯優于量子遺傳算法及遺傳算法。
關鍵詞：量子遺傳算法；混沌優化；變尺度
中圖分類號：TP18 文獻標志碼：A
文章編號：10013695(2009)02054303
Study on mutative scale chaos optimization strategy of quantum genetic algorithm
TENG Hao1，2，SHAO Kuoyi3，CAO Aizeng2，YANG Bingru1
(1.School of Information Engineering， University of Science Technology Beijing， Beijng 100083， China;2.School of Information Science Engineering， University of Jinan， Jinan 250022， China;3.Beijing Unionpay Merchant Services Co.， Ltd， Beijing 100048， China)
Abstract:Aiming at the trouble of easy getting into local minimum and premature convergency existed in quantum genetic algorithm， this paper analysed the flow of QGA， improved the strategy in two sides of global searching and local searching， and presented a new algorithm. This algorithm executed global search using the chaos movement’s ergodicity and randomness， in the same time optimized the renovation process of quantum with the gradient information. The test of typical function shows that the performance of this kind of method is better than quantum genetic algorithm and genetic algorithm.
Key words:quantum genetic algorithm(QGA); chaos optimization; mutative scale
遺傳算法（genetic algorithm，GA）中存在過早收斂和染色體丟失問題。文獻[1~3]分別提出了量子遺傳算法（QGA）、遺傳量子算法（GQA）和并行量子遺傳算法，并用來求解組合優化問題。結果表明，QGA的性能大大優于傳統遺傳算法，一定程度上解決了遺傳算法GA中存在的過早收斂和染色體丟失問題。但QGA的旋轉角查找計算復雜度較高，對于多參數復雜函數優化容易早熟收斂。QGA易陷入局部極值，仍然具有早熟收斂的不足，需要引入一種遍歷性好的全局優化技術來解決這一問題。
混沌運動能在一定范圍內按其自身的規律不重復地遍歷所有狀態，因此，利用混沌變量進行優化搜索，無疑會比隨機搜索更具優越性[4]。
文獻[5]提出了一種將混沌與量子遺傳算法相結合的混沌量子遺傳算法（CQGA），利用載波的方法將混沌狀態引入優化變量，既可以提高搜索效率，同時又可以避免丟失最優解。從效率上比較，混沌優化方法尋優效率明顯優于其他隨機搜索算法，如模擬退火、遺傳算法。從應用方面考慮，混沌的遍歷性是進行混沌全局優化算法的保證，該方法對于搜索空間小時效果顯著，但當搜索空間大時卻不能令人滿意。文獻[6]對混沌優化方法進行了改進，提出了變尺度混沌優化方法，并證明了改進算法的有效性。這就為文獻[5]算法的改進提供了一種方法。此外，在量子門更新的過程中，旋轉角的大小直接影響優化的結果和進化的速度。旋轉變異角一般取的固定值，如果其幅度太小，會影響收斂速度；如果其幅度太大，會導致早熟。實際上，如果距最優解較遠時，變化幅度可以大一些，距最優解很近時，如果變化幅度不夠小就會丟失最優解。不過，距離最優解的遠近很難精確定義。
針對QGA易陷入局部極值的問題，考慮利用變尺度混沌優化方法，對QGA找出的較優點進行混沌搜索，完成全局尋優，這樣在不改變QGA搜索機制的同時，根據搜索進程，不斷縮小優化變量的搜索空間及調節系數，引導種群進行新一輪進化。同時，在局部搜索時，利用梯度的概念實現旋轉變異角的模糊控制，動態調整旋轉角的大小。將以上方法結合構成一種新的量子遺傳算法 (NFQGA)，它能快速產生更優的最優個體，從而改善了QGA的性能，有效地克服了QGA存在的問題。典型函數測試分析表明，該方法用于優化計算方面的綜合性能明顯優于QGA及GA，也優于文獻[5]的算法。
1 變尺度混沌優化方法
若連續對象待尋優問題的目標函數可以表示為
f*=f(x*i)=min f(xi)；i=1， 2，…，n；xi∈[ai，bi](1)
其中：x是決策變量，是一個矢量，其維數等于決策問題的參量個數；f(x)是決策問題的數學模型，也是決策問題的目標函數。混沌優化算法是解決此類問題的一種常用方法。
混沌優化算法中，通常選擇logistic映射進行描述[4]：
xn+1=μxn (1-xn)(2)
其中：μ是控制參量，不能大于4，取μ=4。
設0≤x0≤1，n=0，1，2，…。當μ=4時，上述系統完全處于混沌狀態。設優化對象由式(1)描述，變量維數為m。通常，混沌優化算法的基本步驟如下：
a）算法初始化。對式(2)中的x0分別賦予m個具有微小差異的初值（注意避免取幾個特殊的值0， 0.25， 0.5， 0.75， 1），則將得到m個軌跡不同的混沌變量，經過n次迭代獲得m個數值xi，n（i=1， 2， …，m）。
b)令k=0，xi(0)=ci+dixi，n。其中：ci，di是常數，分別相當于平移和伸縮系數，確保將混沌變量的變化范圍伸縮到式(1)中相應的優化變量的取值范圍內。代入式(1)計算性能指標f(x(0))（下面簡記為f(0)，余同），然后令x*i= xi(0)，f*=f(0)。
c)k:=k+1。通過下式用載波的方法將選定的m個混沌變量xi，n+k分別引入到式(1)中的m個優化變量，使其變成混沌變量xi(k)：
xi(k)=ci+dixi，n+k(3)
其中：ci，di含義同b)。
d)用混沌變量進行迭代搜索。將xi(k)代入式(1)中計算性能指標f(k)。
if f(k)≥f* thenf*=f(k)，x*i=xi(k)
else if f(k) 若經過若干步搜索f*都保持不變，則重新利用a)再次計算獲得m個混沌變量xi，n，令k′=0，然后轉e)；否則轉c)。 e)利用下式進行二次載波: xi(k′)=x*i+αi(xi，n+k-0.5)(4) 其中：xi(k′)是相對于優化問題式(1)的可行域較小的遍歷區間內的混沌變量；αi為調節常數；x*i是粗搜階段的最優解。 f）將xi(k′)代入式(2)繼續迭代進行搜索，計算相應的性能指標f(k′)。 if f(k′)≥f* then f*=f(k′)，x*i=xi(k′) else if f(k′) k′:=k′+1 g)如果滿足終止條件，則停止搜索，輸出最優解x*i，f*；否則，轉e)。 針對式(1)表述的問題，變尺度混沌優化方法的基本步驟如下[6]： (a)算法初始化：設k=1，k′=1，xi(k)=xi(0)，x*i=xi(0)， f*=f(0)，ai(k′)=ai，bi(k′)=bi。 (b)將混沌變量xi(k)映射到優化變量的取值區間，按普通混沌優化方法進行搜索；令k=k+1，xi(k)=4xi(k)(1-xi(k))，直到一定步數內f*保持不變。 (c)改變混沌變量的搜索尺度（其中，調節系數C∈(0，0.5)，mx*i為當前最優解）。 ai(k′+1)=mx*i-C(bi(k′)-ai(k′)) bi(k′+1)=mx*i+C(bi(k′)-ai(k′)) (d)還原優化變量： x*i=mx*i-ai(k′+1)bi(k′+1)-ai(k′+1) 用新的混沌變量yi(k)=(1-A)x*i+Axi(k)（A為較小數），重復b)~d)進行混沌搜索；令k′=k′+1，直到一定步數內f*保持不變； (5)重復c)和d)若干次后結束，此時mx*i為算法得到的最優變量，f*為算法得到的最優解。 2 旋轉變異角的模糊控制方法 在QGA中，染色體不是用確定性的值表示，而是用量子位表示，或者說是用隨機概率方式表示。在QGA中，一個量子位可能處于|1>或|0>，或者處于|1>和|0>之間的中間態，即|1>和|0>的不同的疊加態。因此一個量子位狀態可表示為 |ψ>=α|0>+β|1>(5) 其中：α和β可以是復數，表示相應狀態的概率幅。 與傳統GA采用交叉、變異等遺傳操作來保持種群的多樣性相比，QGA采用量子門作用于量子位概率幅度來保持種群的多樣性，因此量子門更新的方式是QGA的關鍵。量子門主要采用量子旋轉門，即 U=cos θ-sin θ sin θcos θ(6) 其中：θ為旋轉角。 量子位的更新是通過量子門來完成的。其過程如下： αiβi=cos(Δθ)-sin(Δθ) sin(Δθ)cos(Δθ)αiβi(7) 在更新過程中，Δθ的大小和符號起關鍵作用。旋轉變異角Δθ的幅度影響收斂速度，但是如果幅度太大，會導致早熟。據上所述，當出現相同情況時Δθ是不變的。但是在實際過程中，如果當前值離最優值遠，希望增大Δθ，以加快其收斂速度；當前值離最優值近時，希望減少Δθ，以避免早熟。在一些函數求極值的問題中，為了求函數的極小(即下山)，往往不但要選擇函數值小的搜索點，而且還必須保證該搜索點的函數值變化率足夠大。為此提出的策略是：綜合考慮函數在搜索點的函數值及其變化率，重點考慮評價函數在搜索點(單個染色體)處的變化趨勢，并將該信息加入到轉角步長函數的設計中[7，8]。對于可微函數而言，就是利用其梯度，提出如下轉角步長函數： θ=θ0×(λ‖fitmax-fitmin‖/ ‖fit(X)-fitmin‖)+(1-λ)×‖Δfitmax- Δfitmin‖/‖Δfit(X)- Δfitmin‖ 其中：θ0為迭代初值；權值λ∈[0，1]，稱為控制因子，用于體現評價函數值和函數值變化率對欲解問題的重要程度；fitmax和fitmin分別表示當前代群體中評價函數的最小值和最大值(群體中個體數>1)；Δfit(X)為評價函數fit在點X的梯度。Δfitmax和Δfitmin分別定義為 Δfitmax=[max{ fit(X1)/ X11，…， fit(Xm)/ X1m，…，max{ fit(X1)/ Xn1，…， fit(Xm)/ Xnm}] Δfitmin=[min{ fit(X1)/ X11，…， fit(Xm)/ X1m}，…，min{ fit(X1)/ Xn1，…， fit(Xm)/ Xnm}] 對于離散情況，Δfit(X)為評價函數fit在點X處的差分。 為了實現上述過程，只需在一般的二進制編碼的遺傳算法中，在計算評價函數值時增加如下步驟： 對所有染色體計算函數的梯度，計算群體中fitmax、fitmin、Δfitmax和Δfitmin即可。 3一種新的量子遺傳算法(NFQGA) 利用變尺度混沌優化策略改進量子遺傳算法分為以下四個步驟： a)初始化種群； b)按標準遺傳算法完成一次遺傳操作，得到較優種群； c)按照上述變尺度混沌優化方法的各個步驟，對b)選出適應值較高的部分個體進行混沌搜索，引導種群快速進化； d)重復b)和c)，直至滿足終止條件，算法結束。 在這一過程中，變尺度混沌優化方法在步驟c)進行，模糊控制旋轉變異角在步驟b)的量子門更新過程進行，兩者可以完全并行。這就為建立一種新的算法，基于變尺度混沌優化與模糊控制邏輯的量子遺傳算法(NFQGA)提供了可行依據。 利用變尺度混沌優化策略和梯度的概念模糊控制量子更新的方法設計的新的量子遺傳算法分為以下四個步驟，如圖1所示。 a)初始化種群: 產生初始種群P(t)={pt1，pt2，…，ptn}。其中：n是種群的規模；ptj(j=1，2，…，n)為種群的第t代的一個個體ptj=[αt1，αt2，…，αtm，βt1，βt2，…，βtm]。m為量子位數目，即量子染色體的長度；在初始化時，α、β都取1/2，它代表等幾率的線性疊加。 b)按標準遺傳算法完成一次遺傳操作[9]，得到較優種群； （a）根據P(t)中概率幅的取值情況構造R(t)={at1，…，atn}，其中，atj是一個長度為m的二進制串。其產生方式為：產生一個[0，1]上隨機數r，若|ai|2>r，則取值為1，否則為0。 （b）評價R(t)各個體，保留最優個體。若終止條件滿足，則算法終止，否則繼續。 （c）判斷種群是否需要災變。若需要則進行災變并跳至步驟5，否則算法繼續。 （d）使用恰當的量子門進行更換，得到新的概率幅，其中變異角的控制按照上述的模糊方法進行。 （e）令t=t+1，并返回步驟（a）繼續進行。 c)按照上述變尺度混沌優化方法的各個步驟，依次進行將混沌變量映射到優化變量的取值區間，按普通混沌優化方法進行搜索；改變混沌變量的搜索尺度；還原優化變量繼續搜索等步驟，對b)選出適應值較高的部分個體進行混沌搜索，引導種群快速進化。 d)重復b)和c)，直至滿足終止條件，算法結束。 4 算例分析 利用本文提出的NFQGA對下面幾個測試函數進行優化計算，以檢驗該算法的性能，并在相同平臺上與QGA及GA進行比較，結果如表1~3所示。其中這些函數都只有一個全局最優解，但可能存在多個局部極小值。 測試結果表明，QA與QGA的效果明顯不如NFQGA。相對前兩者采用的群體搜索、按概率排除劣解跳出局部最優的策略，后者在全局范圍利用混沌運動的遍歷性，局部搜索利用改進的搜索策略，獲得了更好的求解效果。對于與文獻[5]中相同的測試函數，最優值精度高于文獻[5]一個以上量級，均值在不同迭代次數的結果也優于文獻[5]的結果。 5 結束語 通過對量子遺傳算法搜索過程的分析，在全局范圍利用混沌運動的遍歷性進行優化，同時在局部搜索中，通過結合梯度思想，在量子更新的模糊控制方法上進行改進。這樣，在不改變量子遺傳算法搜索機制的同時，將變尺度混沌優化方法和梯度思想引入QGA，加快了種群的進化速度，大大改善了QGA的性能。該算法搜索速度快、計算精度高、結構簡單、使用方便，仿真結果證明其綜合性能優于GA及QGA，說明該方法具有良好的應用前景。 參考文獻： ［1］ NARAYANAN A，MOORE M.Quantum inspired genetic algorithm[C]//Proc of IEEE International Conference on Evolutionary Computation.Piscataway:IEEE Press，1996:6166. [2]HAN K H，KIM J H.Genetic quantum algorithm and its application combinatorial optimization problems[C]//Proc of IEEE Conference on Evolutionary Computation.Piscataway:IEEE Press，2000:13541360. [3]HAN K H，PARK K H，LEE C H，et al.Parallel quantum inspired genetic algorith for combinatorial optimization problems[C]//Proc of IEEE Conference on Evolutionary Computation.Piscataway: IEEE Press， 2001:14421429. [3]李兵，蔣慰孫.混沌優化方法及其應用[J].控制理論與應用，1997，14(4): 613615. [4]郭海燕.基于混沌優化的量子遺傳算法[J].西南科技大學學報，2005，20(3): 14. [5]張彤， 王宏偉，王子才.變尺度混沌優化方法及應用[J].控制與決策，1999，14(3): 285288. [6]李盼池，李士勇.基于量子遺傳算法的正規模糊神經網絡控制器設計[J].系統仿真學報，2007，19(16):37103715. [7]何新貴，梁久禎.利用目標函數梯度的遺傳算法[J].軟件學報，2001，12(7):981986. [8]楊淑媛，焦李成，劉芳.量子進化算法[J].工程數學學報，2006，23(2):235246.
