一種改進的量子演化算法及其在tsp問題上的應(yīng)用研究

1、 分類號： 密 級： 學(xué) 號： 2008T015 單位代碼： 10407 碩 士 學(xué) 位 論 文 論文題目: 一種 一種改進的 改進的量子演化 量子演化算法 算法 及其在 及其在 TSP 問題 問題上的應(yīng)用 應(yīng)用研究 研究 研 究 方 向 演化計算 演化計算 專 業(yè) 名 稱 計算機應(yīng)用技術(shù) 計算機應(yīng)用技術(shù) 研 究 生 姓 名 李佳林 李佳林 導(dǎo)師姓名、職稱 李康順 李康順 教授 教授 2012 年 3 月

2、1 日 I 摘 要 旅行商問題是數(shù)學(xué)組合優(yōu)化領(lǐng)域最著名的問題之一，是一個非常典型的易于描述卻難以大規(guī)模處理的 NP-hard 問題，如何有效地解決 TSP 問題，對組合優(yōu)化問題的研究有重要的理論意義以及對實際應(yīng)用有廣泛價值。因為，只要是可以抽象成為訪問帶權(quán)完全圖中全部結(jié)點一次且僅一次，求解最小費用 Hamilton 圈的問題，都可以當(dāng)作此問題來解決。 量子演化算法是量子計算和演化算法的有效融合，利用演化算法具有的操作簡單、不需要確定規(guī)

3、則、 采用概率化尋優(yōu)方法、 自動獲取和優(yōu)化搜索空間， 自適應(yīng)地調(diào)整搜索方向、隱并行性、全局尋優(yōu)能力、魯棒性強等性能，結(jié)合量子計算強大的并行計算能力以及可以有效的模擬量子行為的能力，以此來克服傳統(tǒng)演化算法在解決規(guī)模較大、比較復(fù)雜的問題時存在計算量和存儲量巨大、易陷入局部收斂等缺陷。量子演化算法融入了量子力學(xué)的許多基本特性，量子計算與演化算法的結(jié)合，將大大提高算法的效率。同時，本論文提出一種改進的量子演化算法進行 TSP 問題求解研究，并通

4、過實驗表明，該算法與傳統(tǒng)的演化算法相以及改進前的量子演化算法比具有較好的優(yōu)越性。主要工作和創(chuàng)新點如下： 1、在改進的量子演化算法中引入量子比特。使得算法染色體的編碼建立在量子態(tài)的矢量表述基礎(chǔ)上，采用量子比特和城市序號相結(jié)合的量子染色體編碼方式，使量子個體具有并行性和疊加性，有效的減小種群的規(guī)模，使編碼和譯碼方式簡單，易于編碼和譯碼的實現(xiàn)。 2、采用改進的量子旋轉(zhuǎn)門——動態(tài) Hε 量子門，進行自適應(yīng)動態(tài)量子更新。使用改進的量子旋轉(zhuǎn)門來更新

5、種群，算法在不同的演化狀態(tài)和階段自動調(diào)整量子旋轉(zhuǎn)角的大小，改變種群朝優(yōu)秀個體演化的速度，設(shè)定概率觸發(fā)器，利用量子非門進行量子變異操作，加快收斂速度而又使其不易陷入局部最優(yōu)解。 3、提出一種改進的量子演化算法在 TSP 問題上的求解方法。采用量子比特和城市序號相結(jié)合的幾率幅量子染色體編碼方式，使得算法的量子染色體的編碼，既建立在量子態(tài)的矢量表述基礎(chǔ)上又易于實現(xiàn)問題的編碼和譯碼； 利用改進的量子旋轉(zhuǎn)門——動態(tài) Hε 量子門進行動態(tài)自適應(yīng)的量