趙莉+董玉民

摘要：量子蟻群算法將量子理論與傳統(tǒng)的蟻群算法結合，是一種高效的生物進化算法，已經(jīng)廣泛應用到諸多領域，但算法在尋優(yōu)過程中仍然普遍存在陷入局部最優(yōu)解的問題。針對量子蟻群算法的不足，通過引入粒子群的學習模式來改進算法，使得種群在進化過程中有更多的可能性，避免算法早熟收斂。將提出的新型改進量子蟻群算法應用于傳統(tǒng)TSP實驗，實驗結果表明改進算法對問題求解效果較好，對量子蟻群算法的性能有一定的提高。

關鍵詞：量子技術；蟻群算法；粒子群；TSP；智能優(yōu)化

中圖分類號：TP18 文獻標識碼：A 文章編號：1009-3044（2017）35-0214-03

New Improved Quantum Ant Colony Algorithm and Its Application in TSP

ZHAO Li 1，2，DONG Yu-min2

（1. Qingdao Hiser Medical Group， Qingdao 266034， China； 2. Qingdao Technological University， Qingdao 266033， China）

Abstract： Quantum ant colony algorithm combines quantum theory with traditional ant colony algorithm， which is an efficient biological evolutionary algorithm. It has been widely used in many fields， but the algorithm still has the problem of falling into the local optimal solution in the process of optimization. In view of the deficiency of the quantum ant colony algorithm， the particle swarm learning model is introduced to improve the algorithm， so that the population has more possibilities in the evolutionary process， and avoid premature convergence. The new improved quantum ant colony algorithm is applied to the traditional TSP experiment. The experimental results show that the improved algorithm has better effect on the problem， and the performance of the quantum ant colony algorithm is improved.

Key words： Quantum technology； Ant Colony Algorithm； Particle swarm； TSP； Intelligent optimization

人工蟻群算法最早由M.Dorigo等人提出，是一種受自然界螞蟻群體覓食行為啟發(fā)而提出的模擬優(yōu)化算法[1-2] 。該算法在被提出后即受到諸多關注，隨即被廣泛應用于求解旅行商問題、調(diào)度問題、指派問題等，并取得了較好的結果。但由于算法中存在著極易陷入局部最優(yōu)值、收斂速度慢等不足，因此與量子計算相融合的量子蟻群算法被研究者們發(fā)現(xiàn)并提出。量子蟻群算法提出后，迅速引起了各界的關注與研究并很快地投入到相關領域當中，成功解答了0-1背包問題、多任務聯(lián)盟問題等[3-4]。量子蟻群算法中使用量子計算所特有的二態(tài)量子比特來表示信息單元，利用量子比特的疊加性增加信息單位的可能性，從而提高算法的求解能力。傳統(tǒng)的量子蟻群優(yōu)化算法正是發(fā)揮了量子計算與蟻群算法各自的優(yōu)勢，使得算法能以較小的規(guī)模、較好的速度收斂于問題的解，但陷入局部最優(yōu)的弊端并沒有很好的避免。本文提出一種新型的改進量子蟻群算法，將量子蟻群與粒子群相配合，充分利用量子蟻群的群體性及粒子群的自學習能力，避免局部最優(yōu)的發(fā)生，使得算法快速收斂于問題的全局最優(yōu)。在文章最后，將提出的改進算法用于解決TSP問題，通過與傳統(tǒng)算法求解的對比，發(fā)現(xiàn)改進的算法能夠更好地滿足求解需求。

1 改進的量子蟻群算法

1.1 蟻群算法

螞蟻覓食的個體行為雖然簡單，但由多個個體組成的全體覓食行為卻給我們的研究帶來了思路。以自然界蟻群為模型，研究者深入分析了螞蟻個體及群體的行為方式，構造出了一種具有群體智能的人工蟻群系統(tǒng)。蟻群算法是一種隨機搜索算法，通過群體的進化逐步搜索到求解的最優(yōu)。算法中的螞蟻個體在移動過程中，會釋放一種名為外激素的物質(zhì)以便與同伴傳遞信息，在此我們稱之為信息素。同樣，在個體行進時也會參考路徑上殘留的信息素濃度以概率方式確定移動的方向，以表示第k只螞蟻從i→j的概率，則：

其中，allowedk表示第k只螞蟻下一步允許去往的位置，分別表示信息素濃度和啟發(fā)因子。

1.2 粒子群算法

粒子群優(yōu)化算法起源于對自然界鳥群的捕食行為研究，是Kennedy和Eberhart共同提出的一種社會系統(tǒng)的模擬[5]。每一只飛鳥看作待優(yōu)化問題的一個解，鳥群覓食的整體行為即為待優(yōu)化問題逐步尋優(yōu)的過程。若鳥群中的M只飛鳥表示為，第只飛鳥的位置和速度可以分別用向量表示為：

鳥群學習自己與群體的經(jīng)驗進行更新，采用交叉、變異的形式重新確立自身及全局最優(yōu)，更新公式可以表示為：endprint

粒子群算法被應用于眾多科學研究和工程應用，以及函數(shù)優(yōu)化、圖像處理等其他領域，正是由于PSO算法的簡單易實現(xiàn)[6-7]。與其他進化算法類似，粒子群在優(yōu)化進行過程中遵循優(yōu)勝劣汰的規(guī)律，但鳥群尋優(yōu)不采用交叉變異等行為，僅通過個體的記憶能力進行彼此之間相互合作與競爭，同時利用自身的學習能力使得優(yōu)化任務得以完成。但過早的收斂會使優(yōu)化結果不夠精確，對于精確求解的復雜性問題不足以很好地完成優(yōu)化。

1.3 量子編碼

與傳統(tǒng)的二進制編碼不同，量子態(tài)不僅可以表示0狀態(tài)和1狀態(tài)，還可以表示二者的任意疊加狀態(tài)：，其中，滿足歸一化條件：。若量子位表示為，則具有n個基因位的個體為：

在改進的量子蟻群算法中，用量子態(tài)表示螞蟻所經(jīng)過路徑上的信息素。第k只螞蟻的信息素矩陣可以描述為：

其中，表示該螞蟻在路徑i→j上產(chǎn)生的信息素濃度。

1.4 信息素更新

螞蟻在經(jīng)過某條路徑時，會在該路徑上留下信息素以幫助群體的其他同伴能順利找到合適的路徑，信息素會因螞蟻的增加而增多，也會隨時間而流失。在初始時刻，所有路徑上殘留的信息素濃度都相等，設為。用表示信息素濃度隨時間的消逝，當螞蟻完成一次路徑探索后，所有路徑上的信息素濃度隨之改變，具體可以描述為：

其中，是第k只螞蟻在經(jīng)過路徑i→j時留下的信息素，表示為：

是則表示路徑i→j上增加的所有信息素的累計值，是k螞蟻所走過路徑的長度之和。種群中的螞蟻會根據(jù)信息素濃度的多少，選擇合適的路徑走向終點，完成路徑尋優(yōu)任務。

2 算法流程

旅行商問題是經(jīng)典的組合優(yōu)化問題，將商人要訪問的M個城市進行路徑規(guī)劃，使得每個城市都被訪問且只訪問一次 [8-9]。TSP問題中，商人可以選擇的路徑組合相當龐大，對于M個城市而言，可選擇的路徑為M！/2M，在這眾多的路徑當中求解出的距離最短路徑，即為TSP問題的最優(yōu)解，也是智能優(yōu)化算法的目的所在。

本文以TSP的優(yōu)化為例，描述改進的新型量子蟻群算法如下：

1） 初始化算法參數(shù)，確定待規(guī)劃城市的位置信息、種群規(guī)模、最大迭代次數(shù)、信息素揮發(fā)因子、初始溫度、冷卻系數(shù)等。初始化信息素矩陣中每個量子位的概率幅為。

2） 統(tǒng)計個體已經(jīng)走過的城市作為旅行禁忌，推算出個體允許旅行的城市列表。計算個體從一個城市轉(zhuǎn)移到另一個城市的概率，采用輪盤賭法選擇個體將要去到的下一個城市，并記錄個體走過的路徑與相應路徑的長度。

3） 更新路徑上信息素的濃度，使用量子旋轉(zhuǎn)門與量子變異算子，增加群體的多樣性，其中旋轉(zhuǎn)角度與變異因子動態(tài)自調(diào)整，隨迭代次數(shù)的增加而自適應變化。同時計算新的路徑規(guī)劃與路徑距離，利用模擬退火的思路以一定的概率接受新路徑。

4） 利用粒子群的自學習和社會學習行為，對種群尋優(yōu)的結果進行深度優(yōu)化，并判斷新路徑是否被采用，避免種群過早陷入局部最優(yōu)。

5） 逐步迭代，得到TSP問題的最優(yōu)解。

3 實驗

考慮到對旅行商問題進行優(yōu)化測試，本文采用國際通用的TSP實例庫TSPLIB進行實驗[10]。選取chn31作為實驗數(shù)據(jù)，并將本文提出的新型改進的量子蟻群算法、傳統(tǒng)的量子蟻群算法與蟻群算法進行對比，對每個算法分別進行30次獨立實驗。算法參數(shù)的設置尚無明確的理論依據(jù)，但由經(jīng)驗可得當時，算法的效率較好[11]。本文取信息素相對重要程度因子，啟發(fā)信息相對重要程度因子，初始溫度為100，冷卻系數(shù)為0.99，種群規(guī)模為30，最大迭代次數(shù)為50，信息素矩陣初始化為，量子旋轉(zhuǎn)角度及量子變異概率根據(jù)迭代次數(shù)自適應調(diào)整。

如上圖所示，圖1為實驗采用的chn31問題的城市位置坐標圖，共有31個城市分布圖中。圖2-4分別為使用蟻群算法、量子蟻群算法和本文改進的新型量子蟻群算法求得的TSP問題的規(guī)劃路徑。圖4則為使用三種不同的智能優(yōu)化算法，分別對chn31進行30次獨立實驗得到的平均最優(yōu)路徑圖?？梢钥闯?，采用蟻群算法求得的路徑規(guī)劃圖中路線直接存在明顯的交叉重疊，顯然不是理想路線；量子蟻群算法得到的路徑規(guī)劃雖無較大的路徑交叉，但從得到的路徑長度來看并不十分理想；而采用本文算法最終得到的路徑規(guī)劃中，彼此線路沒有之間連接合理，最終路徑距離也符合最短的要求。

傳統(tǒng)的量子蟻群算法較蟻群算法能更加快速尋找到優(yōu)化解，但很難搜索到問題的全局最優(yōu)，只能停留在相對較為優(yōu)秀的位置；本文提出的算法在一定程度上克服了傳統(tǒng)量子蟻群算法的不足，能以較小的種群規(guī)模和迭代次數(shù)，快速的跳出局部收斂并尋找到較為優(yōu)秀的路徑規(guī)劃結果。

4 結束語

智能優(yōu)化算法的不斷更新與發(fā)展，為復雜的組合優(yōu)化等問題提供了可行的解決方案，并將逐步應用于實際生產(chǎn)生活的諸多領域中。本文在傳統(tǒng)的量子蟻群算法、粒子群算法的基礎上加以改進，提出了一種新型的改進算法，充分考慮到每個算法自身的優(yōu)缺點以此來提高算法的總體優(yōu)化求解水平，并將新的改進算法應用于TSP實驗當中，實驗結果表明改進算法具有一定的可用性，較傳統(tǒng)算法而言能更加快速準確地找到規(guī)劃路徑。但chn31屬于規(guī)模較小的旅行商問題，在今后希望能將提出的改進算法進一步應用到大規(guī)模問題的求解當中，并繼續(xù)擴展到其他實際應用當中。

參考文獻：

[1] Colomi A，Dorigo M and Maniezzo V.Distributed optimization by ant colonise[A].In：Proc.of 1st European Conf.Artificial Life[C].Pans，F(xiàn)rance：Elsevier，1991：134-142.

[2] Zhao H X，Huo B F，Liu R Y.Chromaticity of the complements of paths[J].J Math Study，2000，4：345-353.

[3] 張澎，王魯達，胡丹.基于量子遺傳算法的蟻群多目標優(yōu)化研究[J].計算機仿真，2013，30（4）：322-325.

[4] 賈瑞玉，李亞龍.基于MapReduce的量子蟻群算法[J].計算機工程與應用，2013，49（19）：246-270.

[5] Kennedy J，Eberhart R C.Particle Swarm Optimization[C].Proceedings of IEEE International Conference on Neutral Networks，Perth，Australia，1995：1942-1948.

[6] 高鷹，謝勝利.混沌粒子群優(yōu)化算法[J].計算機科學，2004，31（8）：13-15.

[7] 張廣帥，張煜東，吉根林.蟻群算法求解TSP綜述[J].南京師范大學學報：工程技術版，2014，14（4）：39-44.

[8] Escoffier B，Monnot J.A better differential approximation ratio for symmetric TSP[J].Theoretical Computer Science，2008，396，37（2）：83-84.

[9] 萬正宜，彭玉旭.求解旅行商問題的改進型量子蟻群算法[J].計算機工程與應用，2016，52（22）：59-63，122.

[10] Dong F M，Koh K M，Teo K L.Chromatic polynomials and chromaticity of graphs[M].[S.l.]：World Scientific Publishing Co Pte Ltd，2005.

[11] 張記會，高齊圣，徐心和.自適應蟻群算法[J].控制理論與應用，2000，17（1）：1-3.endprint