李 煜, 馬 良
(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ù)值實驗說明其有效性.
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)化為等價的完全圖形式.
量子算法是一種新發(fā)展起來的概率進化算法,它基于量子計算原理,利用量子計算的一些概念和理論,如量子位、量子疊加態(tài)等.量子比特是量子計算中保存信息的最小單元,一個量子比特可能處于,也可能處于,還可以是兩種狀態(tài)的線性疊加[7,13].因此,一個量子位可表示為
一個具有m個量子比特位的系統(tǒng)同時表示2m種狀態(tài),可以描述為
蟻群算法(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ù).
量子蟻群算法集量子計算和蟻群算法的優(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 輸出目前的最好解.
為驗證量子蟻群算法的有效性,采用網(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)化性能.
量子蟻群算法建立在量子的態(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.