用量子蟻群算法求解大規模旅行商問題

李 煜， 馬 良

（1.上海理工大學管理學院，上海 200093；2.河南大學管理科學與工程研究所，開封 475004）

蟻群算法是一種來自生物界的隨機搜索尋優方法，由意大利學者Colorni等［1－2］于20世紀90年代初期通過模擬自然界中螞蟻的尋徑行為，而提出的一種基于種群的啟發式仿生進化算法，并得到了廣泛的應用［3－4］.但蟻群算法在較大規模問題中計算時間偏長、運算精度低.本文將在基本的蟻群算法中融入量子計算理論，以進一步提高搜索效率和搜索精度.

量子優化是由量子計算和量子信息論發展而來的，20世紀80年代初Benioff和Feynman提出了量子計算的概念，隨后Shor于1994年提出基于量子Fourier變換的大數質因子分解算法，大數質因子求解問題是公認的NP（non－deterministicpolynomial）問題，Shor算法將大數質因子求解轉換為P（polynomial）問題.Grover于1996年提出無序數據庫的量子搜索算法，該算法則提供了經典算法的根方加速，從此，量子計算以其獨特的計算性能引起了廣泛的矚目，并迅速成為研究的熱點［5－7］.世界首臺通用編程量子計算機已經于美國面世［8］，其可在進一步改進后應用于密碼破譯等方面.將量子計算技術應用于優化理論中，稱為量子優化算法，可以解決經典方法難以解決或無法解決的許多問題.量子蟻群算法是一種基于量子優化原理的新的優化方法，其將量子優化和蟻群尋優相結合，提高了旅行商問題（TSP）的運算精度.本文首先結合TSP給出量子蟻群算法的原理，然后用數值實驗說明其有效性.

1 量子蟻群算法

1.1 TSP的一般描述

TSP是一個典型的優化組合問題，已被證明屬于NP完全問題.對于TSP的求解，一直以來都是學術界研究的熱點，精確算法主要有線性規劃算法、動態規劃算法和分支定界算法，但這些精確算法是指數級的，所能求解的問題規模非常有限，對n個城市而言，可能的路徑總數為n！／2n，隨著n數的增加，路徑數將急劇增長.由于現實中這些問題在許多領域都有著廣泛的應用，因而尋找其實際而有效的算法就顯得頗為重要.盡管有指數級的算法可作精確求解，但隨著它們在大規模問題上的失效（組合爆炸），人們退而求其次，轉向尋找近似算法或啟發式算法.經過幾十年的努力，取得了很大的進展［9－12］.

TSP在圖論意義下又常常被稱為最小哈密頓圈問題，這里用數學的語言來進行描述.

記G＝（V，E）為賦權圖，V＝｛1，2，…，n｝為頂點集，E為邊集，各頂點間的距離cij已知，cij＞0，cij＝∞，i，j∈V.設

則經典TSP的數學模型為

式中，Z為目標函數值；｜S｜為集合S中所含圖G的頂點數.

約束（1）和（2）意味著對每個點來說，僅有一條邊進和一條邊出；約束（3）則保證了沒有任何子回路解的產生.于是，滿足約束（1）～（3）的解構成了一條哈密頓回路.

為簡便起見，本文中假定所考慮的都是歐氏意義下的完全圖；否則，可通過求任意兩點間的最短路轉化為等價的完全圖形式.

1.2 量子算法

量子算法是一種新發展起來的概率進化算法，它基于量子計算原理，利用量子計算的一些概念和理論，如量子位、量子疊加態等.量子比特是量子計算中保存信息的最小單元，一個量子比特可能處于，也可能處于，還可以是兩種狀態的線性疊加［7，13］.因此，一個量子位可表示為

一個具有m個量子比特位的系統同時表示2m種狀態，可以描述為

1.3 蟻群算法

蟻群算法（ant colony algorithm）是一種新穎的仿生算法，它抽象了自然界螞蟻的群體行為，吸收了昆蟲王國中螞蟻群體的行為特性，用螞蟻群在搜索食物源的過程中所體現出來的尋優能力來解決一些離散系統優化中的困難問題.該方法目前已經成功地應用于很多NP完備的組合優化問題.

蟻群算法的轉移概率是一個非常重要的因素，它體現了人工螞蟻在移動時的尋優特性，應用在算法中主要體現在兩個方面，即信息素軌跡強度和距離，它們分別以一定的權重影響著轉移概率的值.

按照TSP的約束，在螞蟻的周游完成以前只能訪問未曾到過的節點，設螞蟻的數量為m，系統初始時將m只螞蟻隨機放在n個節點上，并設置了每邊的初始信息素濃度.為此設定一個禁忌表t［m］［n］.其中，t［k］［f］表示螞蟻k在時刻t以前走過的點.螞蟻的一次周游構造了問題的一個可行解.當m只螞蟻都完成一次周游后，便在各自經過的路徑的每一條邊上留下信息素.若算法經過N次循環后停止，則基本蟻群算法的時間復雜度為Ο（N·m·n2）.在實驗中，m一般取值與n為同一數量級，因此，整個算法的復雜度為Ο（N ·n3）.

位于i處的螞蟻k移至其鄰域中結點j處的概率為

式中，ηij為邊弧（i，j）的能見度（visibility），即1／dij；τij為邊弧（i，j）的軌跡強度（intensity）；α為軌跡的相對重要性，α≥0；β為能見度的相對重要性，β≥0；bij為邊弧（i，j）量子信息強度.

給定城市元素的集合C＝｛c1，c2，…，cn｝，C中任意排列組合L＝｛（c1…，ci，…，cj，…，cn），ci∈C，i，j＝1，2，…，n｝，L為路徑（i，j）的長度.

信息素強度的更新方程為

式中，τi，j，t＋1，τij，t分別為第t＋1次和t次迭代的邊弧（i，j）的軌跡強度；Δτkij為螞蟻k在邊弧（i，j）上留下的單位長度軌跡信息素數量，ρ為信息強度的揮發性，0≤ρ＜1.

式中，Q為螞蟻所留下軌跡數量的一個常數.

1.4 量子蟻群算法

量子蟻群算法集量子計算和蟻群算法的優點于一身，對它們取長補短，同基本的蟻群算法相比具有更好的搜索性能.量子算法可以根據不同的問題設計不同的量子門使得算法搜索到最優解.量子門的設計有多種形式，但由于概率歸一化的要求，變換矩陣必須滿足酉正矩陣，酉性限制是對量子門的唯一限制.常用的有非門、受控非門、Hadamard門及量子旋轉門等.量子門是實現算法進化操作的執行機構，通過量子門算子使量子比特的概率幅發生變化，推動量子個體向最優解方向演化，本文設置的量子旋轉門為

式中，θ為旋轉的角度.

通過不斷地更新量子旋轉門U（θ）來更新量子比特qj，不斷地生成新的解X，比較解X的函數值，可以得到最好解b.量子旋轉門的調整方式可定義為

旋轉角的幅值直接影響算法的收斂速度和搜索能力.如果幅值過大，會導致早熟；如果幅值過小，會是收斂速度減慢.其值一般在0.001π～0.05π之間.其大小和方向根據關系式θi＝Δθis（αi，βi）來確定，s（αi，βi）是決定θi的旋轉方向的符號函數，Δθi是旋轉角度的大小.

由上述定義可知，量子蟻群算法的性能受到初始值的影響.在每一次迭代中，算法將會更新螞蟻的信息素，同時要進行量子門旋轉來更新量子比特，使得算法不斷地改進最優解.

量子蟻群算法主要步驟描述如下：

步驟1 nc為迭代次數，nc←0；

對τij和Δτij進行初始化；

將m個螞蟻置于n個頂點上.

步驟2 將各螞蟻的初始出發點置于當前解集中；

對每個螞蟻k（k＝1，2，…，m）按轉移概率pkij及其它要求移至下一頂點j；

將頂點j置于當前解集中.

步驟3 計算各螞蟻的目標函數值Zk，k＝1，2，…，m；

記錄當前的最好解.

步驟4 按更新方程修改軌跡信息素強度.

步驟5 按量子旋轉門來更新量子信息.

步驟6 對各邊弧（i，j），置Δτij←0；nc←nc＋1.

步驟7 若nc小于預定的迭代次數且無退化解（即找到的都是相同解），則轉步驟2.

步驟8 輸出目前的最好解.

2 數值實驗

為驗證量子蟻群算法的有效性，采用網上公布的標準問題庫TSPLIB中的實例（http：／／www.iwr.uniheidelberg. de／groups／comopt／software／TSPLIB95／tsp／）.在Windows XP下用Delphi 7.0編制程序進行了計算.各種參數的設定如下：螞蟻數目為50，α取值為1～2，β取值為1～3，ρ＝0.7，量子比特初始化為即所有的路徑被選擇的概率相等，并使用三邊交換算法（3－OPT）進行鄰域優化.

現介紹部分問題得到的結果.B1為本算法求得的最優解，B2為TSP庫中公布的最優解的值，同最好解的偏差率R＝（B1－B2）／B2，表1中問題名稱的數字為結點總個數，且從小到大顯示.這里給出本算法求解部分的詳細情況，其余只給出結果，如表1所示.

表1 計算結果Tab.1 Calculation results

實例1 文件名：St70，其中，結點個數N＝70，B2＝675，本算法求解的結果為

螞蟻回路總長B1＝675，等于公布的最好解.

螞蟻回路路徑P＝1 36 29 13 70 35 69 31 38 59 22 66 63 57 15 24 19 7 2 4 18 42 32 3 8 26 55 49 28 14 20 30 44 68 27 46 45 25 39 61 40 9 17 43 41 6 53 5 10 52 60 12 34 21 33 62 54 48 67 11 64 65 56 51 50 58 37 47 16 23.

實例2 文件名：Berlin52，其中，N＝52，B2＝7 542，本算法求解的結果為

螞蟻回路總長B1＝7 542，等于公布的最好解.

螞蟻回路路徑P＝1 22 31 18 3 17 21 42 7 2 30 23 20 50 29 16 46 44 34 35 36 39 40 37 38 48 24 5 15 6 4 25 12 28 27 26 47 13 14 52 11 51 33 43 10 9 8 41 19 45 32 49.

從表1中的數據可以看出，量子蟻群算法在TSP求解過程中總體效果良好，部分算例的計算結果已達到公布的最優解，算法結果與最好解的誤差率很小，說明該算法有較好的優化性能.

3 結束語

量子蟻群算法建立在量子的態矢量表示的基礎之上，將量子比特的概率幅表示應用于人工螞蟻的位置，并利用量子邏輯門實現量子比特的更新操作，從而實現了目標的優化求解.根據旅行商問題的特點，利用量子比特的特點結合蟻群算法，給出了量子蟻群算法的描述，通過大量的數值測試探討了算法的求解性能，從數值模擬結果來看，本文給出的量子蟻群算法可以較快、較好地找到問題的最優解或近似最優解，是求解TSP的一個新的可行手段.

［1］ Dorigo M，Maniezzo V，Ccolorni A.The ant system：Optimization by ant colony cooperating agents［J］.IEEE Transactions on Systems，Man，and Cybernetics，Part B，1996，26（1）：29－41.

［2］ Dorigo M，Gambardella L.Ant colony system：A cooperative learning approach to the traveling salesman problem［J］.IEEE Transanctions on Evolutionary Computation，1997，1（1）：53－66.

［3］ 馬良，項培軍.螞蟻算法在組合優化中的應用［J］.管理科學學報，2004，4（2）：32－37.

［4］ 馬良，朱剛，寧愛兵.蟻群優化算法［M］.北京：科學出版社，2008.

［5］ Hey T.Quantum computing：An introduction［J］.Computing ＆Control Engineering Journal，1999，10（3）：105－112.

［6］ Han K H，Kim J H.Genetic quantum algorithm and its application to combinatorial optimization problem［C］／／IEEE Proceedings of the 2000Congress on Evolutionary Computation.2001：1354－1360.

［7］ Han K H，Kim J H.Quantum－inspired evolutionary algorithms with a new termination criterion［J］.IEEE Transactions on Evolutionary Computation，2004，8（2）：156－169.

［8］ Hanneke D，Home J P，Jost J D，et al.Realization of a programmable two－qubit quantum processor［J］.Nature Physics，2010，6：13－16.

［9］ 孫聰，趙新超.旅行商問題研究及混合粒子群算法求解［J］.計算機工程與應用，2009，45（25）：38－40.

［10］ 馬良.求解最小比率TSP的一個算法［J］.系統工程，1998，16（4）：62－65.

［11］ 馬良，蔣馥.多目標旅行售貨員問題的螞蟻算法求解［J］.系統工程理論方法應用，1999，8（4）：23－27.

［12］ 王宇平，李英華.求解TSP的量子遺傳算法［J］.計算機學報，2007，30（5）：748－755.

［13］ Nielsen M A，Chuang I L.量子計算和量子信息（一）［M］.北京：清華大學出版社，2006.