求解TSP量子蟻群算法

求解旅行商問題的混合量子蟻群算法摘要：針對蟻群算法求解旅行商問題時易陷入局部最優(yōu)和收斂速度慢的問題，提出一種新的求解旅行商問題的混合量子蟻群算法。該算法采用量子比特的概率幅對各路徑上的信息素進行編碼，量子旋轉(zhuǎn)門及螞蟻走過的路徑對信息素進行更新，加快算法收斂速度；為了避免搜索陷入局部最優(yōu)，設(shè)計一種新的變換鄰域準(zhǔn)則，以提高求解效率。TSPLIB中部分實例仿真結(jié)果表明該算法比傳統(tǒng)蟻群算法具有更快的收斂速度和求解精度。關(guān)鍵詞：量子蟻群算法；變換鄰域準(zhǔn)則；旅行商問題HybridQuantumAntColonyAlgorithmfor

TravelingSalesmanProblemAbstract:AimingattheTravelingSalesmanProblembasedonantcolonyoptimizationwhichiseasytofallintolocaloptimumsandhasaslowconvergencerate,ahybridquantumantcolonyoptimizationalgorithmispresented.Inthisalgorithm,thepheromoneoneachpathisencodedbyagroupofquantumbits,thequantumrotationgateandant’stourareusedtoupdatethepheromonesoastoaccelerateitsconvergencespeed;Toavoidthesearchfallingintolocaloptimum,thenewneighborhoodexchangestrategyisdesignedtoimprovesolutionefficiency.SomecasesfromtheTSPlibrary(TSPLIB)areusedtoexperiment,theresultsshowthatthealgorithmhasrapiderconvergencespeedandhigheraccuracythantheclassicalantcolonyalgorithm.Keywords:QuantumAntColonyAlgorithm;neighborhoodexchangestrategy;TravelingSalesmanProblem1引言蟻群算法是一種模擬進化算法，最早是意大利學(xué)者DorigoM于1991年提出①，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為，算法成功地用于TSP求解、工件排序、圖著色、車輛調(diào)度等多目標(biāo)組合優(yōu)化問題b頊。然而，迭代次數(shù)多、收斂速度慢、易于陷入局部最優(yōu)解仍是制約ACO算法廣泛應(yīng)用的主要瓶頸。量子計算岡的研究開始于二十世紀(jì)八十年代，Benioff和Feynman提出了量子計算的概念。量子計算利用量子理論中有關(guān)量子態(tài)的疊加、糾纏和干涉等特性，用來解決經(jīng)典計算中的許多難題，并以其獨特的計算性能引起科技界的廣泛關(guān)注。1985年Deutsch指出，利用量子態(tài)的相干疊加性可以實現(xiàn)并行的量子計算。1994年Shor提出大數(shù)因子分解的量子算法，此算法可在量子計算機上以多項式時間實現(xiàn)，它使NP問題變成P問題。2002年，Kuk-HyunHan等提出量子進化算法(Quantum-InspiredEvolutionaryAlgorithm,QEA)，它是一種基于量子計算原理的概率優(yōu)化方法。它以量子計算的一些概念和理論為基礎(chǔ)，用量子位編碼來表示染色體，用量子門作用和量子門更新來完成進化搜索，具有種群規(guī)模小而不影響算法性能、同時兼有“勘探”和“開采”的能力、收斂速度快和全局尋優(yōu)能力強的特點回。量子蟻群算法(QuantumAntColonyAlgorithm，QACA)則將量子計算和蟻群算法相結(jié)合，把量子計算中的態(tài)矢量和量子旋轉(zhuǎn)門引入到蟻群算法中，加快了算法的收斂速度。量子蟻群算法已成功地求解許多組合優(yōu)化問題，文獻［10］使用量子蟻群算法對0-1背包問題(0/1knapsackproblem)進行求解，并用數(shù)值試驗說明了算法的有效性。文獻［11］利用量子計算的并行性，將量子蟻群算法用于求解多任務(wù)聯(lián)盟問題，并取得了較好的結(jié)果。文獻［12］中分析了量子蟻群算法的優(yōu)缺點，提出一種新的量子蟻群算法用于求解小規(guī)模旅行商問題(TravelingSalesmanProblem，TSP)，但對于求解較大規(guī)模問題時，該算法易陷入局部最優(yōu)和停滯狀態(tài)。針對量子蟻群算法求解TSP問題的不足，本文提出一種混合量子蟻群算法(HybridQuantumAntColonyAlgorithm，HQACA)，該算法設(shè)計了一種新的變換鄰域準(zhǔn)則來對求得的解進行優(yōu)化，擴大解的搜索空間，改善種群信息結(jié)構(gòu)，避免搜索陷入局部最優(yōu)。對國際通用的TSPLIB中部分實例進行了實驗，并將該算法與目前比較常用的一些算法進行了比較，仿真結(jié)果表明該算法具有更好的收斂速度和求解精度。2TSP簡述直觀地說，TSP問題就是指一位商人，從自己的家鄉(xiāng)出發(fā)，希望能找到一條最短路徑，途徑給定的城市集合中的所有城市，最后返回家鄉(xiāng)，并且每個城市都被訪問且僅訪問一次。形式上，TSP問題可以用一個帶權(quán)完全圖G=(N,A)來描述，其中N是城市的結(jié)點集合，A是所有邊的集合。每一條邊(，,j)eA都分配一個權(quán)值d「,它代表城市i與j之間的距離大小，其中i,jeN。在非對稱TSP中，一對結(jié)點i,j之間的距離與該邊的方向有關(guān)，也就是說，至少存在一條邊(i,j)，有d.豐dj。在對稱TSP中，集合A中所有的邊都必須滿足dj=d,。TSP的目標(biāo)就是尋找圖中的一條苴有最小成本值的哈密爾頓回路，這里的哈密爾頓回路是指一條訪問圖G中的每一個結(jié)點一次且僅一次的閉合路徑。這樣，TSP的一個最優(yōu)解就對應(yīng)于結(jié)點標(biāo)號為｛1,2,...,乃｝的一個排列兀，并且使得長度f(兀)最小。f(兀)的定義為：f(兀)=Z1d +d (1)兀(i)兀(i+1) 兀(n)兀(1)i=1求解TSP問題最直接同時也是最精確的方法就是窮舉搜索，將n個城市的任意排列看作一個有序表，它決定了所訪問的城市的順序，旅行商從某個城市出發(fā)，然后歷經(jīng)所有城市直至到出發(fā)城市，每個有序表都對應(yīng)一個路徑長度總耗費，由于每一條路徑可能用2n種不同表示方法，而n個城市排列數(shù)為n!，因此搜索空問大小為|S|=n!2n=(n-1)!..；2。窮舉搜索算法就是計算(n-1)!.：'2個不同的有序表的耗費，其中最小耗費對應(yīng)的旅行路經(jīng)就是TSP的解，隨著城市數(shù)目的不斷增加，求解空間將呈指數(shù)級增長，通過窮舉法根本無法求解，因此用優(yōu)化算法解決TSP就十分必要。目前，求解TSP問題的算法較多，最常用的方法主要有神經(jīng)網(wǎng)絡(luò)算法、蟻群算法、啟發(fā)式搜索法、遺傳算法、模擬退火算法和量子算法等。這些算法在求解TSP時有各自的優(yōu)點和缺陷，有的運算快但易于收斂到局部最優(yōu)解，有的求解精度高但收斂速度較慢，有的求解城市規(guī)模較小等，針對以上算法的不足，本文使用一種混合量子蟻群算法來求解TSP。3混合量子蟻群算法(HQACA)3.1量子信息編碼在經(jīng)典計算中，采用0和1二進制表示信息，稱為比特。在量子信息論中，信息的基本存儲單元是量子比特，或稱量子位。一個簡單的量子比特是一個雙態(tài)系統(tǒng)，它的兩個極化狀態(tài)對應(yīng)經(jīng)典信息的二進制存儲單元狀態(tài)的0和1。區(qū)別于經(jīng)典比特，一個量子比特除了可以處于0態(tài)和1態(tài)之外，還可以處于它們的疊加態(tài)。

A『,、 山…一a ，—〃『，、，一，，，——，一個量子位可以使用概率幅r表示，那么有n個量子位的個體概率幅可表示為:P態(tài)。a2P2態(tài)。a2P2n-1其中，a,、pj滿足|aj+|p.（2）i=1,2,…,n，該量子個體可以表示任意量子疊加在HQACA中，使用量子比特表示各路徑上的信息素，第k只螞蟻在各路徑上的量子信息素編碼可表示為：0：J（aJl1J息素編碼可表示為：0：J（aJl1JQu=k(a)kJ(a)k2J(a))kJ(以」墮nJ(a\ijijJ（3）(a(aJpn1EJ(a)pnnWn刀(aJEJ(aJEJ2+|"=1；當(dāng)i=j時，aij其中，n為城市總數(shù)目表示城市i到城市j之間路徑上的信息素的概率幅，當(dāng)2=|pj2=0（1<i,j<n）。對于城市i和j，當(dāng)有螞蟻通過i到j(luò)的路徑，會使得該路徑上信息素概率幅&）?的值增大，信息素得以增強；反之，該路徑上的信息素會有所揮發(fā)，信息素更新規(guī)則見3.4節(jié)。ij3.2信息素更新規(guī)則按照TSP約束，當(dāng)所有螞蟻都構(gòu)建好路徑后，各邊上的信息素將會被更新。首先，所有邊上的信息素都會減少一個常量因子的大小，然后在螞蟻經(jīng)過的邊上增加信息素。信息素的蒸發(fā)根據(jù)下面的公式執(zhí)行u廠=（1—pX廠,V（i,j）gA （4）其中p是信息素的蒸發(fā)率，有0<P<1，參數(shù)P的作用是避免信息素的無限積累。在信息素的蒸發(fā)步驟之后，所有螞蟻都在它們經(jīng)過的邊上釋放信息素：（5）（6）u=u+并Atk,V（i,j）g（5）（6）k=1其中Atj「第\只螞蟻向它經(jīng)過的邊釋放的信息素量。Atj定義為Atk一WPG/Ck），如果邊（i,j）在第履螞蟻構(gòu)建的路徑八上"I 0否則

其中Pk表示第其中Pk表示第k只螞蟻在i到j(luò)的路徑上的量子信息素強度，以廠+Pkijij2=1；Ck表示第k只螞蟻建立的路徑Tk的長度，即在Tk中所有邊的長度之和；y表示量子信息素啟發(fā)因子，表示i到j(luò)路徑上量子態(tài)概率幅的相對重要性。設(shè)有m只螞蟻，nXn的矩陣R是n個城市TSP問題的一條解路徑，它滿足每行每列有且僅有一個元素為1，其余為0.R[i,j]=1表示路徑R中存在從城市i到城市j的邊，當(dāng)i=j時必有'cosIsin(6)cos(o)l'cosIsin(6)cos(o)llpjV 八ij式中，i,j=1,2,3，…,m,(at,p)為第t次迭代中城市i到城而之間路徑上的信息素的概率ijij(7)(at+i)(7)pj+i幅，6表示路徑倒j的量子位的旋轉(zhuǎn)角度，如表1皿中的A9司，其值通過查表所得到，用于控制算法的收斂速度。表1旋轉(zhuǎn)角策略R",j]R如上j]f(R)〉f(Rbe)A6js(a,p)ap>(0p<0a=0pi=000假0000000真0000001假0000001真0.05n-11±1010假0.01n-11±1010真0.025n1-10±111假0.005n1-10±111真0.025n1-10±1在表1中，f(x)為目標(biāo)函數(shù)，在本文中為螞蟻建立的路徑的長度；s(a,p.)表示旋轉(zhuǎn)角ij ij度的方向，用來保證算法的收斂性。3.3變換鄰域準(zhǔn)則所謂鄰域搜索是只針對解空間中某個特定的區(qū)域進行搜索，搜索過程可用以下三步說明：1.從解空間中找一個解并評估其質(zhì)量，將它定義為當(dāng)前解。按照變換鄰域準(zhǔn)則變換當(dāng)前解得到當(dāng)前解的一個鄰域，找出鄰域中的最好解，定義該解為新解。如果新解優(yōu)于當(dāng)前解，則將當(dāng)前解用新解替換，重復(fù)策步；否則，拋棄新解，停止

搜索。鄰域搜索中最關(guān)鍵最困難在于如何變換當(dāng)前解，得到當(dāng)前解的一個領(lǐng)域，針對量子蟻群算法求解TSP問題，本文設(shè)計一種新的變換鄰域準(zhǔn)則來對螞蟻求得的當(dāng)前解進行優(yōu)化，避免搜索陷入局部最優(yōu)。定義：S={bqq，…qqq}^n個城市的TSP問題的一條路徑，。表示該路123 n-1n1 i徑第i個位置的城市序號，候選解S的k-變換鄰域指的是從城市a到C經(jīng)過的n-1條邊中1n去除k條邊，將原路徑分成k+1個部分，對這k+1個部分重新排列而得到的解的集合。為了保證鄰域中解的初始城市和結(jié)束城市與原路徑相同，第一部分保持不變，后跟部分按排列的方式進行組合。1）k-變換局部尋優(yōu)對于路徑S，斷開其任意k條邊，保持第一部分不變，后面k部分按排列方式進行組合生成新的路徑，如果新生成的路徑優(yōu)于已知的最優(yōu)解，則用當(dāng)前路徑替換最優(yōu)路徑，重復(fù)此過程直到搜索完鄰域內(nèi)所有的路徑。如圖1為2-變換局部尋優(yōu)過程，圖2為3-變換局部尋優(yōu)過程。aaaaaaaaa123ii+1jj+1n1o--o—-o0—00—0—aaaaaaaaa*_23 V<i+1_jL+1n_1XXXX（丟棄）VXVX3132ai七+1132ai七+1ana1七1七圖12-變換局部尋優(yōu)aaaaaaaaaaaa_c-—二…-￡―土-~y二二二-o^d*ajaa〃l^ll^l叮a七frf^TOC\o"1-5"\h\zX 、\ X3 X4XXXX（丟棄）1234XXXX，取最優(yōu)解43，取最優(yōu)解XXXX24XXXX1342XXXX1423XXXX1432圖23-變換局部尋優(yōu)過程2）時間復(fù)雜性分析對于n個城市的TSP問題，2-變換局部尋優(yōu)的搜索空間大小是C2.（2!-1）=（n-1）（n-2V2，k-變換局部尋優(yōu)的搜索空間大小%「（婦-1）。一般而言當(dāng)K很小時，鄰域搜索會較快結(jié)束，但解的質(zhì)量不太高。相反，當(dāng)KB大時，鄰域中解的數(shù)目會隨K呈指數(shù)級增長，雖然解的質(zhì)量會有所提高，但搜索時間會很長，綜合考慮解的質(zhì)量和計

算時間在實際應(yīng)用K一變換局部尋優(yōu)算法時，K一般取2或3。3.4HQACA算法步驟步驟1初始化：設(shè)定各參數(shù)a,P,p,Y的值，螞蟻個數(shù)為m，最大迭代次數(shù)NMAX，當(dāng)前迭代次數(shù)t=0，信息素七（0）=1.為了使算法初始搜索時所有狀態(tài)以相同概率出現(xiàn)，螞蟻量子信息素編碼中所有的a〃B”取值均為1/J2。步驟2設(shè)城市總數(shù)為n，將m只螞蟻隨機的放在n個城市的其中一個上，每只螞蟻獨立的構(gòu)造一個解，按照式（8）選擇要訪問的城市，重復(fù)地應(yīng)用狀態(tài)轉(zhuǎn)移規(guī)則，直到螞蟻k訪問完所有的城市。fargmax問完所有的城市。fargmaxj=\JI [n讓如果0<qilil 0leNk'否則（8）上式確定了該算法中螞蟻k要訪問的下一個城市j，其中：七為邊（i,l）上的信息素濃度，匕=1/0〃，代表邊（i,l）的自啟發(fā)量，5是自啟發(fā)量的權(quán)重，N代表了位于城市i的螞蟻k可以直接到達(dá)的相鄰城市的集合，也就是指所有還沒有被螞蟻k訪問的城市的集合，J是根pk'ililleNkipk'ililleNki如果?eNki（9）a和P是兩個參數(shù)，分pk指位于城市i的螞蟻k選擇j作為下一個訪問城市的概率。ij別決定了信息素和啟發(fā)式信息的相對影響力。q是均勻分布在區(qū)間［0,1］中的一個隨機變量，q0（。＜q0＜1）是一個參數(shù)，指螞蟻選擇當(dāng)前可能的最優(yōu)移動方式的概率，這種最優(yōu)的移動方式是根據(jù)信息素的積累量和啟發(fā)式信息值求出的。同時，螞蟻以（1-q0）的概率有偏向性地探索各條邊。通過調(diào)整參數(shù)q0，我們可以調(diào)節(jié)算法對新路徑的探索度，從而決定算法是應(yīng)該集中搜索至今最優(yōu)路徑附近的區(qū)域，還是應(yīng)該探索其他區(qū)域。步驟3若m只螞蟻都構(gòu)造完成各自的解，則轉(zhuǎn)步驟4,否則轉(zhuǎn)步驟2。步驟4對m只螞蟻生成的解使用3-變換局部尋優(yōu)算法進行優(yōu)化，記錄m只螞蟻構(gòu)造出來的最優(yōu)解。步驟5根據(jù)當(dāng)前最優(yōu)解，應(yīng)用量子旋轉(zhuǎn)門規(guī)則［10更新螞蟻在各個路徑上的量子信息概率幅，按照式2進行全局信息素更新。步驟6若滿足結(jié)束條件，即下＞NMAX，輸出最優(yōu)解，否則t=t+1，轉(zhuǎn)步驟2。4仿真實驗和分析本文測試用例來自國際通用的TSP實例庫TSPLIB［14，選用att48、ch150、kroa100進行

實驗仿真，并將HQACA與ACS（基本蟻群算法）、SAS（排序蟻群算法）和MMAS（最大最小蟻群算法）進行對比實驗，以驗證所提算法的有效性和可行性。對每個實例分別用HQACA、ACS、SAS、MMAS做50次獨立的測試，城市間距離保留小數(shù)，并記錄下50次實驗中各算法找到的最好解、最差解、平均最好值。運行參數(shù)：螞蟻數(shù)n=50，a=1,0=5,p=0.9，量子啟發(fā)因子y=2~4，先驗知識q°=0.01。和$人$算法，實驗表明了HQACA算法比MMAS和SAS算法更穩(wěn)定求解精度都優(yōu)于MMAS具有較強的魯棒性。（a）att48對比實驗!?<*和$人$算法，實驗表明了HQACA算法比MMAS和SAS算法更穩(wěn)定求解精度都優(yōu)于MMAS具有較強的魯棒性。（a）att48對比實驗!?<*中8&，（b）kroa100對比實驗（c）ch150對比實驗表1：att48對比實驗結(jié)果算法已知最優(yōu)解最大進化代數(shù)平均進化代數(shù)所求最好解所求最差解平均值A(chǔ)CS335222000927.37337393511634614.32SAS2000839.8335223453333734.2MMAS50002449.15335223422833772.65HQACA1000447.75335223396633691.45表2：kroa100對比實驗結(jié)果算法已知最優(yōu)解最大進化代數(shù)平均進化代數(shù)所求最好解所求最差解平均值A(chǔ)CS2128230001791.63224542297022670.1SAS30001226.85214092233621594MMAS80003751212822229121589.8HQACA3000836.85212822167221453.4表3：ch150對比實驗結(jié)果算法已知最優(yōu)解最大進化代數(shù)平均進化代數(shù)所求最好解所求最差解平均值A(chǔ)CS652850003649.67672868116756.33SAS50001409.1657267996668.45MMAS100006929.2656966806609HQACA50001333.65652866256594.3從表1?表3中可以看出，當(dāng)問題規(guī)模較小時，SAS、MMAS、HQACA三種算法均能求出最優(yōu)解，本文提出的HQACA算法的收斂速度優(yōu)于SAS和MMAS算法，隨著問題規(guī)模的增大，SAS收斂速度優(yōu)于MMAS算法，MMAS求解精度優(yōu)于SAS算法，HQACA算法的收斂速度和圖3單次實驗中最優(yōu)解隨迭代次數(shù)變化曲線圖圖3（a）、（b）、（c）分別描繪了單次實驗中各算法得到的最優(yōu)解隨迭代次數(shù)的變化情況，為了便于觀察，我們?nèi)〉螖?shù)為1000,從圖中可以看出，傳統(tǒng)的ACS算法雖然收斂速度較快，但容易早熟，陷入局部最優(yōu)解，SAS和MMAS雖然求解精度高于ACS，但是收斂較慢，HQACA算法則彌補了傳統(tǒng)算法的不足，既能保證求解的精度，又能快速的收斂。實驗表明了對信息素進行量子比特編碼，能夠增加解的多樣性，有助于勘測和開采到更多更好的解，避免算法過早出現(xiàn)停滯現(xiàn)象；采用量子旋轉(zhuǎn)門作為進化策略，能夠加快算法收斂，提高全局搜索能力，針對有可能陷入局部最優(yōu)問題，對螞蟻每次求得的解進行鄰域變換，擴大搜索區(qū)域，尋求更好質(zhì)量的解。6結(jié)束語本文將量子蟻群算法與鄰域搜索相結(jié)合，提出了一種求解TSP問題的混合量子蟻群算法。算法采用量子比特對TSP問題中各路徑上的信息素進行編碼，并對螞蟻求得的解進行鄰域變換，擴大搜索空間，加速算法收斂。將HQACA算法與其他傳統(tǒng)算法進行仿真比較，結(jié)果證明了該算法求解TSP問題的有效性和可行性，在以后的研究中將進一步研究HQACA算法以解決更為實際的問題，擴大該算法的應(yīng)用領(lǐng)域。參考文獻ColorniA,DorigoM,ManiezzoV,etal.Distributedoptimizationbyantcolonies[C]//Proceedingsofthe1stEuropeanConferenceonArtificialLife.Paris,France:ElsevierPublishing,1991:134-142.申鉉京，劉陽陽,黃永平，徐鐵，何習(xí)文.求解TSP問題的快速蟻群算法[J].吉林大學(xué)學(xué)報，2013,43(1):147-151.張潔漲朋，劉國寶.基于兩階段蟻群算法的帶非等效并行機的作業(yè)車間調(diào)度[J].機械工程學(xué)報，2013,49(6):136-144.王欣盛，馬良.工件排序的改進蟻群算法優(yōu)化[J].上海理工大學(xué)學(xué)報，2011,33(4):362-366朱慶保，揚志軍.基于變異和動態(tài)信息素更新的蟻群優(yōu)化算法[J].軟件學(xué)報，2004,15(2):185-192陳英武，姚鋒，李菊芳，賀仁杰,邢立寧.求解多星任務(wù)規(guī)劃問題的演化學(xué)習(xí)型蟻群算法[J].系統(tǒng)工程理論與實踐，201