基于混合蛙跳的量子遺傳算法

董玉民，趙 莉

（1.青島理工大學(xué) 網(wǎng)絡(luò)中心，山東 青島266033；2.青島市海慈醫(yī)療集團，山東 青島266033）

0 引 言

量子遺傳算法將傳統(tǒng)的遺傳算法引入量子空間，在遺傳算法的優(yōu)勢上進一步提高算法性能。量子遺傳算法由Narayanan等人提出［1］，并引起了社會各界學(xué)者的廣泛關(guān)注。雖然量子編碼固有的疊加性使算法的收斂能力大幅提高，但出現(xiàn)早熟的可能仍然是其一個不可忽視的問題。為進一步提高量子遺傳算法的性能，對算法的改進研究一直在進行。

為提高算法的尋優(yōu)能力，在基本的量子遺傳算法的基礎(chǔ)上，引入混合蛙跳算法，結(jié)合模擬退火準(zhǔn)則及動態(tài)的參數(shù)調(diào)整，提出一種基于混合蛙跳的改進算法。將改進后的新算法與其它對比算法，分別用于測試函數(shù)的優(yōu)化，從實驗的結(jié)果中可以看出，新的改進算法有效提高了算法的求解能力，在符合問題精度要求的基礎(chǔ)上搜索出函數(shù)的滿意解。

1 基于量子的遺傳算法

量子遺傳算法將量子計算融合到傳統(tǒng)的遺傳算法，拋棄遺傳算法中復(fù)雜的操作算子，僅使用旋轉(zhuǎn)門策略更新種群。采用量子位編碼染色體，使得量子遺傳算法獲得更豐富的個體，利于全局問題的求解［2］。

1.1 量子計算

1.2 算法實現(xiàn)

這樣的編碼方式，可以用一個基因位同時表示任意多不同狀態(tài)，充分體現(xiàn)種群的多樣性。

種群中個體的更新，使用量子旋轉(zhuǎn)門來完成。量子旋轉(zhuǎn)門實際上就是改變了量子位的疊加態(tài)，相當(dāng)于變異操作。

1.3 算法流程

基本的量子遺傳算法的主要執(zhí)行步驟可以描述如下：

步驟1 初始化算法中的各項參數(shù)并進行種群Q（t）的初始化。

步驟2 對初始種群的所有個體進行坍塌測量，得到狀態(tài)值P（t）。

步驟3 對P（t）進行適應(yīng)度函數(shù)評價，記錄種群中最優(yōu)個體。

步驟4 當(dāng)未達到種群的最大迭代次數(shù)，循環(huán)執(zhí)行下述操作：

（1）增加種群的進化代數(shù)。

（2）對種群Q（t－1）進行坍塌測量，記錄狀態(tài)P（t）。

（3）對P（t）中的所有進行適應(yīng)度函數(shù)評價，記錄個體的適應(yīng)度值。

（4）用量子旋轉(zhuǎn)門更新個體。

（5）將全局最優(yōu)保存在P（t）中，并記錄個體信息。

2 基于量子的遺傳算法改進

隨著量子遺傳算法的發(fā)展，出現(xiàn)了大量對算法的優(yōu)化改進。文獻 ［3－8］中，研究者分別就染色體的編碼、種群構(gòu)造、旋轉(zhuǎn)門等方面，提出了對量子遺傳算法的各種改進，在一定程度上優(yōu)化了算法。本文針對算法容易出現(xiàn)過早收斂，無法快速收斂的缺陷，在基本量子遺傳算法中引入混合蛙跳，進一步改進算法的不足。

2.1 改進策略

2.1.1 分組尋優(yōu)

混合蛙跳算法由Eusuff和Lansey 在2003 年提出［9］，建立在模因算法與粒子群算法的基礎(chǔ)上，并結(jié)合了二者的優(yōu)點。混合蛙跳算法的核心特征，是協(xié)調(diào)并利用局部信息和全局信息。算法將種群分為不同的組，各組同時進行組內(nèi)的3次跳躍搜索，當(dāng)完成組內(nèi)尋優(yōu)之后，重新混合，進行新一輪的分組尋優(yōu)。

利用混合蛙跳的分組尋優(yōu)，可以減少算法的迭代次數(shù)，加快算法的收斂。經(jīng)典的混合蛙跳算法，個體移動步長的大小直接影響算法的優(yōu)化結(jié)果，若步長太大，個體很可能越過最優(yōu)解并逐漸遠離，若步長太小，個體有可能陷入局部極值。考慮將慣性調(diào)節(jié)參數(shù)引入，使個體的移動步長隨著組內(nèi)搜索同步調(diào)節(jié)。

改進后的個體第一次跳躍（局部最優(yōu)更新）的更新公式

改進后的個體第二次跳躍 （全局最優(yōu)更新）的更新公式

2.1.2 模擬退火準(zhǔn)則

模擬退火算法［10］，利用了物理中固體物質(zhì)的退火原理，溫度逐漸由高到低的同時，在解空間中搜索問題的全局最優(yōu)。

采用模擬退火算法中的這一概率性接收準(zhǔn)則，以最小值問題為例：

2.1.3 動態(tài)旋轉(zhuǎn)門量子遺傳算法中通常采用固定的旋轉(zhuǎn)門，在新算法中使用動態(tài)調(diào)整旋轉(zhuǎn)角的方式。動態(tài)自適應(yīng)旋轉(zhuǎn)角調(diào)節(jié)，可以在算法的尋優(yōu)過程中靈活控制，將旋轉(zhuǎn)角度由初始時的較大值逐漸減小到后期的較小值，使個體的搜索范圍由大變小。

2.2 基于混合蛙跳的量子遺傳算法

在基本的量子遺傳算法中，引入混合蛙跳的分組策略，提出一種新的改進量子遺傳算法，簡記為QSFLG，借鑒分組尋優(yōu)的方式將群體分組，并進行組內(nèi)的三次跳躍更新，在完成分組尋優(yōu)后重新混合，使用動態(tài)的量子旋轉(zhuǎn)門更新個體，并使用模擬退火準(zhǔn)則概率性接收新解，之后再利用量子非門進行群體的量子變異。

QSFLG 的基本流程描述如下：

（1）算法的初始化階段

步驟1 初始化算法參數(shù)，包括最大迭代次數(shù)MAXGEN，種群規(guī)模SIZEPOP，種群分組數(shù)目GROUPNUM，每個分組中個體數(shù)目GROUPIND，組內(nèi)最大迭代次數(shù)GROUPMAXGEN，初始溫度T0，冷卻系數(shù)α，冷卻系數(shù)Pi。

步驟2 量子位編碼染色體，種群初始化。

步驟3 對種群中的每一個個體進行坍塌操作，記錄狀態(tài)值。

步驟4 對狀態(tài)值進行適應(yīng)度函數(shù)評價，記錄最優(yōu)個體的適應(yīng)度值。

（2）分組尋優(yōu)階段

步驟5 將種群中所有個體按適應(yīng)度值升序排列，排序后第一個個體分配到1號子種群，第二個個體分配到2號子種群，……，第GROUPNUM 個個體分配到GROUPNUM 號子種群，第 （GROUPNUM＋1）個個體分配到1號子種群……直到種群中所有個體分配完。

步驟6 進行子種群的組內(nèi)尋優(yōu)。分別對各組內(nèi)的個體進行3次跳躍，當(dāng)組內(nèi)最差個體的第1次跳躍結(jié)果沒有優(yōu)化，則進行第2 次跳躍，當(dāng)?shù)? 次跳躍的結(jié)果沒有優(yōu)化，則進行第13次跳躍，隨機生成個體。

步驟7 當(dāng)組內(nèi)尋優(yōu)達到最大迭代次數(shù)，則進行步驟8，否則跳轉(zhuǎn)到步驟4。

（3）整體尋優(yōu)階段

步驟8 利用模擬退火準(zhǔn)則概率性接收新解。

步驟9 使用動態(tài)的量子旋轉(zhuǎn)門，更新群體中的個體。再次利用模擬退火準(zhǔn)則進行判斷，以概率接收劣質(zhì)解。

步驟10 使用量子非門，對種群中的個體進行量子變異操作。

步驟11 若達到算法的最大迭代次數(shù)，則輸出最優(yōu)解，算法結(jié)束，否則繼續(xù)執(zhí)行步驟4。

3 函數(shù)優(yōu)化

3.1 測試函數(shù)

為測試算法的性能，使用以下5個最小值測試函數(shù)進行仿真實驗。

（1）f1（x）＝x6－15x4＋27x2＋250 x∈ ［－100，100］。

函數(shù)f1（x）有3個局部極小值，理論全局最小值為7。

此函數(shù)為Shaffer函數(shù)的變形，由最大值問題變形為求最小值，變形后的理論最小值為－1。

f3（x，y）有6個局部極值，理論最小值為－1.031628。

Sphere函數(shù)是一個簡單的單峰函數(shù)，常被用于測試算法的性能，理論最小值為0。

Griewank函數(shù)是標(biāo)準(zhǔn)的多模態(tài)函數(shù)，具有很多局部極值，理論最小值為0。

3.2 實驗設(shè)計

將提出的基于混合蛙跳的量子遺傳算法 （QSFLG）、量子遺傳算法 （QGA）、混合蛙跳算法 （SFLA）和粒子群優(yōu)化算法 （PSO）分別作用于5 個測試函數(shù)，進行實驗的對比。

測試函數(shù)Sphere和Griewank取變量的維數(shù)為5。QSFLG 和QGA 采用量子位編碼的方式，編碼長度為20；QSFLG 的變異概率為0.01，初始溫度為100，冷卻系數(shù)為0.99。算法其它參數(shù)的設(shè)置見表1。

3.3 實驗結(jié)果與分析

3.3.1 實驗一

對于5個測試函數(shù)，每個算法分別進行50 次獨立實驗。算法的求解精度為10－3時，即算法的最優(yōu)解與測試函數(shù)的理論最優(yōu)值之差小于10－3時，記為算法求解成功。定義算法的函數(shù)優(yōu)化成功率：求解成功的次數(shù)與獨立運行的總數(shù)之比。

算法的仿真函數(shù)測試實驗，在MATLAB R2008 環(huán)境下進行，4種算法的實驗結(jié)果詳見表2。

表1 測試函數(shù)的參數(shù)設(shè)置

表2 測試函數(shù)的實驗結(jié)果

從表2的實驗結(jié)果中可以看出，改進的基于混合蛙跳的量子遺傳算法對5個測試函數(shù)的優(yōu)化能力較好。與其它3個算法相比，QSFLG 使用較小的種群規(guī)模和迭代次數(shù)，但求解出的函數(shù)最優(yōu)值比另外3 個函數(shù)更接近理論最優(yōu)值。進行50次獨立實驗，QSFLG 的求解成功率最高，每次求解都能找到滿足精度要求的全局最優(yōu)解。但QSFLG 仍然存在不足，表現(xiàn)為算法的運行時間略長。雖然QSFLG 的運行時間比PSO 長，但略微犧牲時間代價來換取更為準(zhǔn)確的全局最優(yōu)解，是可以接受的。

算法的收斂能力是另一個評價算法性能優(yōu)劣的關(guān)鍵。圖1～圖5分別給出了4種算法求解函數(shù)最優(yōu)解的進化收斂曲線圖。

圖1 測試函數(shù)f1 的收斂曲線

圖2 測試函數(shù)f2 的收斂曲線

圖3 測試函數(shù)f3 的收斂曲線

圖4 測試函數(shù)Sphere的收斂曲線

圖5 測試函數(shù)Griewank的收斂曲線

從函數(shù)的優(yōu)化曲線圖中可以看出QSFLG 對測試函數(shù)的求解表現(xiàn)出更好的收斂性能。雖然QSFLG 在求解前4個函數(shù)時，初始階段的收斂速度較為緩慢，不是4種算法中最好的，但隨著優(yōu)化的進行，QSFLG 的表現(xiàn)逐漸優(yōu)于其它3種算法，穩(wěn)定收斂。綜合看來，改進的基于混合蛙跳的量子遺傳算法QSFLG 能以較小的種群規(guī)模以及較小的迭代次數(shù)，快速且穩(wěn)定的收斂到一個很接近問題理論最值的滿意解。

3.3.2 實驗二

在實驗二中，提高算法的求解精度為10－6，每個算法獨立運行50次。表3中給出了4種算法對測試函數(shù)優(yōu)化的結(jié)果。

表3 算法的成功次數(shù)

從實驗結(jié)果看來，改進的基于混合蛙跳的量子遺傳算法QSFLG 有效提高了量子遺傳算法的性能。當(dāng)問題的求解精度定義較高時，QSFLG 相對于其它3種算法，仍然具有較高的求解成功率。實驗結(jié)果說明，改進的新算法能更好的求解出滿足用戶需要的全局最優(yōu)解，提高了量子遺傳算法的整體性能。

4 結(jié)束語

針對量子遺傳算法存在的不足，在傳統(tǒng)的量子遺傳算法的基礎(chǔ)上，提出一種新的改進算法。算法引入混合蛙跳的分組尋優(yōu)策略并優(yōu)化更新公式，同時考慮動態(tài)調(diào)整量子旋轉(zhuǎn)門和量子變異，再用模擬退火的概率接收準(zhǔn)則判斷是否接收產(chǎn)生的新解。將提出的新算法用于函數(shù)優(yōu)化，利用測試函數(shù)的優(yōu)化結(jié)果來評價算法的性能。實驗結(jié)果表明，改進的基于混合蛙跳的量子遺傳算法有效避免了算法的早熟收斂，能搜索到滿足問題精度的全局最優(yōu)，提高了算法求解能力。

［1］LIANG Changyong，BAI Hua.Advances in quantum genetic algorithm ［J］.Application Research of Computers，2012，29 （7）：2401－2405（in Chinese）.［梁昌勇，柏樺.量子遺傳算法研究進展［J］.計算機應(yīng)用研究，2012，29 （7）：2401－2405.］

［2］HUANG Liming，XU Ying，YU Ruiqin.Improved quantum genetic algorithm and its application ［J］.Computer Enginee－ring and Design，2009，30 （8）：1987－1990 （in Chinese）.［黃力明，徐瑩，于瑞琴.改進的量子遺傳算法及應(yīng)用 ［J］.計算機工程與設(shè)計，2009，30 （8）：1987－1990.］

［3］ZHOU Chuanhua，QIAN Feng.Improvement of quantum genetic algorithm and its application ［J］.Computer Applications，2008，28 （2）：286－288（in Chinese）.［周傳華，錢鋒.改進量子遺傳算法及其應(yīng)用［J］.計算機應(yīng)用，2008，28 （2）：286－288.］

［4］GAO Yinghui，SHEN Zhenkang.An angle－coding chromosome quantum genetic algorithm ［J］.Computer Engineering＆Science，2009，31 （3）：75－79 （in Chinese）.［高穎慧，沈振康.角度編碼染色體量子遺傳算法 ［J］.計算機工程與科學(xué)，2009，31 （3）：75－79.］

［5］LI Shiyong，LI Hao.Quantum genetic algorithm based on phase comparison ［J］.Systems Engineering and Electronics，2010，32 （10）：2219－2222 （in Chinese）.［李士勇，李浩.一種基于相位比較的量子遺傳算法 ［J］.系統(tǒng)工程與電子技術(shù)，2010，32 （10）：2219－2222.］

［6］XU Bo，PENG Zhiping，YU Jianping.Improved quantum genetic algorithm based on cloud model theory［J］.Application Research of Computers，2011，28 （10）：3684－3686 （in Chinese）. ［許 波，彭志平，余建平.一種基于云模型的改進型量子遺傳算法 ［J］.計算機應(yīng)用研究，2011，28 （10）：3684－3686.］

［7］SHA Linxiu，HE Yuyao，CHEN Yanwei.Variable step double chains quantum genetic algorithm ［J］.Computer Engineering and Applications，2012，48 （20）：59－63 （in Chinese）.［沙林秀，賀昱曜，陳延偉.一種變步長雙鏈量子遺傳算法［J］.計算機工程與應(yīng)用，2012，48 （20）：59－63.］

［8］LIU Weining，JIN Hongbing，LIU Bo.Cloud computing resource scheduling based on improved quantum genetic algorithm［J］.Journal of Computer Applications，2013，33 （8）：2151－2153 （in Chinese）. ［劉衛(wèi)寧，靳洪兵，劉波.基于改進量子遺傳算法的云計算資源調(diào)度 ［J］.計算機應(yīng)用，2013，33（8）：2151－2153.］

［9］CUI Wenhua，LIU Xiaobing.Survey on shuffled frog leaping algorithm ［J］.Control and Decision，2012，27 （4）：481－486（in Chinese）. ［崔文華，劉曉冰.混合蛙跳算法研究綜述［J］.控制與決策，2012，27 （4）：481－486.］

［10］WANG Yinnian，GE Hongwei.Improved simulated annealing genetic algorithm for solving TSP problem ［J］.Computer Engineering and Applications，2010，46 （5）：44－47 （in Chinese）.［王銀年，葛宏偉.求解TSP問題的改進模擬退火遺傳算法 ［J］.計算機工程與應(yīng)用，2010，46 （5）：44－47.］