新型改進(jìn)量子蟻群算法及其TSP應(yīng)用

趙莉+董玉民

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

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

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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] 。該算法在被提出后即受到諸多關(guān)注，隨即被廣泛應(yīng)用于求解旅行商問(wèn)題、調(diào)度問(wèn)題、指派問(wèn)題等，并取得了較好的結(jié)果。但由于算法中存在著極易陷入局部最優(yōu)值、收斂速度慢等不足，因此與量子計(jì)算相融合的量子蟻群算法被研究者們發(fā)現(xiàn)并提出。量子蟻群算法提出后，迅速引起了各界的關(guān)注與研究并很快地投入到相關(guān)領(lǐng)域當(dāng)中，成功解答了0-1背包問(wèn)題、多任務(wù)聯(lián)盟問(wèn)題等[3-4]。量子蟻群算法中使用量子計(jì)算所特有的二態(tài)量子比特來(lái)表示信息單元，利用量子比特的疊加性增加信息單位的可能性，從而提高算法的求解能力。傳統(tǒng)的量子蟻群優(yōu)化算法正是發(fā)揮了量子計(jì)算與蟻群算法各自的優(yōu)勢(shì)，使得算法能以較小的規(guī)模、較好的速度收斂于問(wèn)題的解，但陷入局部最優(yōu)的弊端并沒(méi)有很好的避免。本文提出一種新型的改進(jìn)量子蟻群算法，將量子蟻群與粒子群相配合，充分利用量子蟻群的群體性及粒子群的自學(xué)習(xí)能力，避免局部最優(yōu)的發(fā)生，使得算法快速收斂于問(wèn)題的全局最優(yōu)。在文章最后，將提出的改進(jìn)算法用于解決TSP問(wèn)題，通過(guò)與傳統(tǒng)算法求解的對(duì)比，發(fā)現(xiàn)改進(jìn)的算法能夠更好地滿足求解需求。

1 改進(jìn)的量子蟻群算法

1.1 蟻群算法

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

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

1.2 粒子群算法

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

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

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

1.3 量子編碼

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

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

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

1.4 信息素更新

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

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

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

2 算法流程

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

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

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

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

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

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

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

3 實(shí)驗(yàn)

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

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

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

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

[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] 張澎，王魯達(dá)，胡丹.基于量子遺傳算法的蟻群多目標(biāo)優(yōu)化研究[J].計(jì)算機(jī)仿真，2013，30（4）：322-325.

[4] 賈瑞玉，李亞龍.基于MapReduce的量子蟻群算法[J].計(jì)算機(jī)工程與應(yīng)用，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].計(jì)算機(jī)科學(xué)，2004，31（8）：13-15.

[7] 張廣帥，張煜東，吉根林.蟻群算法求解TSP綜述[J].南京師范大學(xué)學(xué)報(bào)：工程技術(shù)版，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] 萬(wàn)正宜，彭玉旭.求解旅行商問(wèn)題的改進(jìn)型量子蟻群算法[J].計(jì)算機(jī)工程與應(yīng)用，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] 張記會(huì)，高齊圣，徐心和.自適應(yīng)蟻群算法[J].控制理論與應(yīng)用，2000，17（1）：1-3.endprint