量子遺傳算法在TSP中的應用

潘子宇 耿鵬

南京工程學院通信工程學院 江蘇 211167

0 引言

近年來，啟發式智能優化方法越來越引起人們的關注。如：模擬退火、遺傳算法、蟻群算法等，它們是解決NP問題的有效工具。

量子計算作為計算機科學界一個新興的研究領域，在過去的幾年里一直是人們研究和探索的熱點問題。由于量子計算的并行性可以大大地降低了算法的復雜度，所以被廣泛地用于解決需要大量計算空間的復雜問題。

1 量子遺傳算法

量子遺傳算法（QGA）建立在量子的態矢量表述的基礎上，將量子比特的幾率幅表示應用于染色體的編碼，使得一條染色體可以同時表達多個狀態的疊加，并利用量子旋轉門的調整和量子非門來實現染色體的更新操作，從而實現了目標的優化求解。

1.1 量子比特編碼

在量子計算機中，充當信息存儲單元的物理介質是一個雙態量子系統，我們稱之為量子比特。量子比特與經典位的不同之處就在于它可以同時處在兩個量子態的疊加態之中。

在量子遺傳算法中，采用量子比特的存儲和表達一個基因。該基因可以為一個“0”態或“1”態，或它們的任意疊加態。即該基因所表達的不再是某一確定的信息，而是包含所有可能的信息，對該基因的任一操作也會同時作用于所有可能的信息。

1.2 量子遺傳算法流程

量子遺傳算法的算法流程具體如下：

① 初始化種群Q（t0）；

② 對初始化種群中的各個體實施一次測量，得到一組狀態P（t0）；

③ 對各狀態進行適應度評估；

④ 記錄下最佳個體狀態及其適應度值；

⑤ while非結束狀態do

begin

t=t+1；

對種群Q（t）實施一次測量，得到一組狀態P（t）；

對各狀態進行適應度評估；

依據一定的調整策略，利用量子旋轉門U（t）和量子非門對種群進行更新，得到子代種群Q（t+1）；

記錄下最佳個體狀態及其適應度值。

End

1.3 量子旋轉門調整策略

作為演化操作的執行機構，量子門可根據具體問題進行選擇。目前已有的量子門有很多種，根據量子遺傳算法的計算特點，選擇量子旋轉門較為合適。量子旋轉門U（t）的調整操作如下式所示：

量子遺傳算法中，旋轉門是最終實現演化操作的執行機構。其調整策略如表1所示。

表1 旋轉角選擇策略

旋轉角的選擇可以通過靜態或動態的方法調整。在表1中，δ為每次調整的角步長。δ值的選擇對算法的效率也有著很大的影響，δ的值太大可能會使結果發散或早熟收斂到局部最優解。實驗結果表明：動態調整旋轉角策略的收斂速度優于固定旋轉角策略。

1.4 量子變異

變異的作用主要在于阻止未成熟收斂同時提供算法的局部搜索能力。變異的方法有許多種。具體操作方法如下：

（1）以一定的概率Pm從種群中隨機選取若干個個體；

（2）對選種的個體按照一定的概率隨機確定一個或多個變異位；

（3）對選中位的量子比特的幾率幅執行量子非門操作（“0”變“1”，“1”變“0”），即完成了該量子比特的變異操作。

量子變異操作實際上是改變了該量子比特態疊加的狀態，使得原來傾向于坍縮到狀態“0”的變為傾向于坍縮到狀態“1”，或者相反。顯然，這樣的變異操作對染色體的所有疊加態均同時有效。

2 算法實現與性能分析

2.1 旅行商問題的數學描述

旅行商問題的數學描述十分簡單，該問題的約束條件只有一個，就是路程。因此，我們的目標就是搜索整數子集（X中的元素表示對n個城市的編號）的一個排列使

2.2 基于量子遺傳算法的TSP問題求解

運用量子遺傳算法求解TSP問題的算法流程圖（如圖1）。

圖1 量子遺傳算法流程圖

2.3 仿真實驗與結果分析

（1）量子遺傳算法和遺傳算法求解TSP問題的比較

在實驗過程中，我們采用相同的編碼原則，相同的適應度函數，相同的交叉概率、變異概率。分別對5、7、9城市的運行結果作了比較，如表2所示。

表2 量子遺傳算法和遺傳算法的結果

從上表中我們可以看出，遺傳算法和量子遺傳算法均能收斂到最優解。但量子遺傳算法花費的迭代數目明顯小于常規遺傳算法。

（2）算法中靜、動態旋轉角調整的結果比較

對兩種方法分別進行了20、50、100次的循環迭代，其中在動態調整策略中，針對角步長δ的確定方案，我們在現有的指數函數調整策略的基礎上提出了基于正弦函數的調整策略，并比較了這兩種動態調整策略的性能。我們采用搜索成功率作為調整策略比較的標準。得到的結果如表3所示。

表3 靜、動態旋轉角調整的結果

由于δ的值太小將影響收斂速度；太大可能會使得結果發散，或早熟收斂到局部最優解。因此使用動態旋轉門調整可以得到更為理想的結果。此外在實驗中我們還發現，動態調整策略的收斂速度也比靜態調整策略來的快，其最終結果的收斂性也比靜態調整策略來的好，靜態策略的最終結果較為發散。從表中我們還可以看出，隨著疊代次數的增加，動態調整策略的優勢越來越明顯。

此外，我們還將現有的指數函數和我們提出的正弦函數兩種不同的動態調整策略作了比較，其中指數調整策略的函數為，正弦調整策略的函數為通過實驗，我們可以看出，以正弦函數作為δ的調整策略取得了比指數函數更好的效果。

3 總結與展望

本文提出了改進的量子遺傳算法，應用正弦函數動態調整量子旋轉門，有效地克服了現有量子旋轉門調整方案的不足，避免了算法過早陷入局部最優解。對目前組合優化問題中的代表性問題——旅行商問題（TSP）的仿真實驗表明，改進算法的優化質量和效率都優于遺傳算法和一般量子遺傳算法。

接下來，我們還將進一步研究算法的各個參數，以便提高算法的性能。我們還將設法把這一算法應用到其他組合優化問題中。

[1]楊俊安，莊鎮泉.量子遺傳算法研究現狀[J].計算機科學.2003.

[2]王凌，吳昊，唐芳.混合量子遺傳算法及其性能分析[J].控制與決策.2005.

[3]楊淑媛，劉芳，焦李成.一種基于量子染色體的遺傳算法[J].西安電子科技大學學報.2004.

[4]李英華，王宇平.有效地混合量子遺傳算法[J].系統工程理論與實踐.2006.