李 煜， 馬 良

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

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

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

1 量子蟻群算法

1.1 TSP的一般描述

TSP是一個典型的優(yōu)化組合問題，已被證明屬于NP完全問題.對于TSP的求解，一直以來都是學(xué)術(shù)界研究的熱點，精確算法主要有線性規(guī)劃算法、動態(tài)規(guī)劃算法和分支定界算法，但這些精確算法是指數(shù)級的，所能求解的問題規(guī)模非常有限，對n個城市而言，可能的路徑總數(shù)為n?。?n，隨著n數(shù)的增加，路徑數(shù)將急劇增長.由于現(xiàn)實中這些問題在許多領(lǐng)域都有著廣泛的應(yīng)用，因而尋找其實際而有效的算法就顯得頗為重要.盡管有指數(shù)級的算法可作精確求解，但隨著它們在大規(guī)模問題上的失效（組合爆炸），人們退而求其次，轉(zhuǎn)向?qū)ふ医扑惴ɑ騿l(fā)式算法.經(jīng)過幾十年的努力，取得了很大的進展［9－12］.

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

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

則經(jīng)典TSP的數(shù)學(xué)模型為

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

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

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

1.2 量子算法

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

一個具有m個量子比特位的系統(tǒng)同時表示2m種狀態(tài)，可以描述為

1.3 蟻群算法

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

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

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

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

式中，ηij為邊?。╥，j）的能見度（visibility），即1／dij；τij為邊?。╥，j）的軌跡強度（intensity）；α為軌跡的相對重要性，α≥0；β為能見度的相對重要性，β≥0；bij為邊?。╥，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在邊?。╥，j）上留下的單位長度軌跡信息素數(shù)量，ρ為信息強度的揮發(fā)性，0≤ρ＜1.

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

1.4 量子蟻群算法

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

式中，θ為旋轉(zhuǎn)的角度.

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

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

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

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

步驟1 nc為迭代次數(shù)，nc←0；

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

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

步驟2 將各螞蟻的初始出發(fā)點置于當(dāng)前解集中；

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

將頂點j置于當(dāng)前解集中.

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

記錄當(dāng)前的最好解.

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

步驟5 按量子旋轉(zhuǎn)門來更新量子信息.

步驟6 對各邊?。╥，j），置Δτij←0；nc←nc＋1.

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

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

2 數(shù)值實驗

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

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

表1 計算結(jié)果Tab.1 Calculation results

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

螞蟻回路總長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，本算法求解的結(jié)果為

螞蟻回路總長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中的數(shù)據(jù)可以看出，量子蟻群算法在TSP求解過程中總體效果良好，部分算例的計算結(jié)果已達到公布的最優(yōu)解，算法結(jié)果與最好解的誤差率很小，說明該算法有較好的優(yōu)化性能.

3 結(jié)束語

量子蟻群算法建立在量子的態(tài)矢量表示的基礎(chǔ)之上，將量子比特的概率幅表示應(yīng)用于人工螞蟻的位置，并利用量子邏輯門實現(xiàn)量子比特的更新操作，從而實現(xiàn)了目標的優(yōu)化求解.根據(jù)旅行商問題的特點，利用量子比特的特點結(jié)合蟻群算法，給出了量子蟻群算法的描述，通過大量的數(shù)值測試探討了算法的求解性能，從數(shù)值模擬結(jié)果來看，本文給出的量子蟻群算法可以較快、較好地找到問題的最優(yōu)解或近似最優(yōu)解，是求解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］ 馬良，項培軍.螞蟻算法在組合優(yōu)化中的應(yīng)用［J］.管理科學(xué)學(xué)報，2004，4（2）：32－37.

［4］ 馬良，朱剛，寧愛兵.蟻群優(yōu)化算法［M］.北京：科學(xué)出版社，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］.計算機工程與應(yīng)用，2009，45（25）：38－40.

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

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

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

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