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

米蘭　魚佳欣　李東濤　謝瑞莎

摘 要：針對標(biāo)準(zhǔn)量子遺傳算法（QGA）在尋找多峰值最優(yōu)時存在局部尋優(yōu)能力較差和易早熟的缺陷，提出一種改進(jìn)量子遺傳算法（QQGA），運(yùn)用基于概率劃分的小生境協(xié)同進(jìn)化策略初始化量子種群，并采用動態(tài)量子旋轉(zhuǎn)角調(diào)整策略來加快收斂速度；加入量子移民和保優(yōu)選擇策略，提高規(guī)劃效率，避免陷入局部最優(yōu)。利用復(fù)雜二元函數(shù)測試改進(jìn)量子遺傳算法，結(jié)果比標(biāo)準(zhǔn)量子遺傳算法效率高。

關(guān)鍵詞：量子遺傳算法；多峰值函數(shù)；優(yōu)化

中圖分類號：TP301 文獻(xiàn)標(biāo)識碼：A

Abstract：According to has the poor local searching ability and precocity in search of multi peak optimization，so this paper proposed an improved quantum genetic algorithm （QQGA），which uses the probability of evolutionary strategy with niche to initiate the quantum population， and the dynamic quantum rotating angle adjustment strategy to speed up the convergence speed；and adds quantum immigration and elitist selection strategy to improve the planning efficiency and avoid falling into local optimal. Then the paper uses complex function of two variables to test the improved quantum genetic algorithm， and the result proves that the improved quantum genetic algorithm has higher efficiency.

Key words：quantum genetic algorithm； multipeak functions； optimization

1 引 言

量子遺傳算法（QGA）是量子計算與遺傳算法相結(jié)合產(chǎn)生的新的智能算法。利用量子態(tài)疊加性和量子旋轉(zhuǎn)門等操作實現(xiàn)染色體的更新，從而實現(xiàn)有效計算[1]。與遺傳算法相比，量子遺傳算法具有種群多樣性好、全局搜索能力強(qiáng)和收斂速度快等特點[2]。然而，文獻(xiàn)[3]～文獻(xiàn)[4]中也指出，量子遺傳算法適于求解組合優(yōu)化問題，甚至只適于求解背包問題，而不適于求解連續(xù)函數(shù)的優(yōu)化問題，特別是多峰函數(shù)的優(yōu)化問題。

因此，本文提出改進(jìn)量子遺傳算法求解多峰值函數(shù)最優(yōu)值，并進(jìn)行了仿真實驗，結(jié)果證明了該方法是有效可行的。

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

在量子遺傳算法中，最重要的是量子編碼和量子門的引入。量子編碼是將染色體用量子的態(tài)矢量表示，使一條染色體表達(dá)多個態(tài)的疊加，從而增加了種群多樣性，使算法能夠在較小的種群規(guī)模下求得最優(yōu)解； 而量子門的引入使算法具備了優(yōu)化能力，可以保證算法收斂[5]。

2.1 量子編碼

如圖2，各種群之間通過移民算子進(jìn)行聯(lián)系，實現(xiàn)多種群的協(xié)同進(jìn)化，本文的移民算子是在相鄰種群間移民，即用當(dāng)前種群中的最優(yōu)個體代替相鄰種群的最劣個體。加入人工選擇算子保存各種群每個進(jìn)化代中的最優(yōu)個體。每迭代一次進(jìn)行一次移民和人工選擇運(yùn)算，選出各種群的最優(yōu)值存到精華種群。精華種群和其他種群有很大不同，精華種群不進(jìn)行量子變更，保證進(jìn)化過程中各種群產(chǎn)生的最優(yōu)個體不被破壞和丟失。同時，精華種群也是判斷算法終止的依據(jù)，這里采用最大遺傳代數(shù)作為終止判據(jù)。最后從精華種群中獲得最優(yōu)個體。

4 結(jié)束語

本文針對標(biāo)準(zhǔn)量子遺傳算法收斂性差，易陷于局部最優(yōu)的缺點，進(jìn)行改進(jìn)運(yùn)用基于概率劃分的小生境協(xié)同進(jìn)化策略初始化量子種群，并采用動態(tài)的量子旋轉(zhuǎn)角調(diào)整策略來加快收斂速度；加入量子移民和保優(yōu)選擇策略，提高規(guī)劃效率，避免陷入局部最優(yōu)。并利用復(fù)雜二元函數(shù)測試改進(jìn)量子遺傳算法，顯示了優(yōu)良的特性。

參考文獻(xiàn)

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

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

[3] HAN KH， KIM JH. Parallel quantuminspired genetic algorithm for combinatorial optimization problems[C].Proc of IEEE Conference on Evolutionary Computation. Piscataway： IEEE Press， 2001：1422-1429.

[4] 張葛樣，李娜，金煒東.一種新量子遺傳算法及其應(yīng)用[J].電子學(xué)報，2004，32（3）：476-479.

[5] 張宗飛.一種改進(jìn)型量子遺傳算法[J].計算機(jī)工，201003，36（6）：181-183.

[6] 張小鋒， 睢貴芳， 鄭冉. 一種改進(jìn)的量子旋轉(zhuǎn)門量子遺傳算法[J] 計算機(jī)工程，201304，39（4）：234-238.