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

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

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

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

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

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