基于蟻群算法的TSP問題研究

來學(xué)偉

（三門峽職業(yè)技術(shù)學(xué)院信息傳媒學(xué)院，河南三門峽472000）

基于蟻群算法的TSP問題研究

來學(xué)偉

（三門峽職業(yè)技術(shù)學(xué)院信息傳媒學(xué)院，河南三門峽472000）

闡述了蟻群算法的設(shè)計思想、基本原理及基本過程，利用蟻群算法對TSP問題進行求解，體現(xiàn)了進化計算的優(yōu)越性。

蟻群算法；TSP問題；算法

1 蟻群算法的設(shè)計思想

眾所周知，螞蟻是一種群居類動物，常常成群結(jié)隊地出現(xiàn)于人類的日常生活環(huán)境中?？茖W(xué)工作者發(fā)現(xiàn)，螞蟻的個體生活習(xí)性相當(dāng)簡便容易，相對來說，蟻群的生活行為就特別復(fù)雜，通過這種復(fù)雜的行為特征可以實現(xiàn)較為復(fù)雜的活動，而且蟻群能根據(jù)環(huán)境的變遷調(diào)整自己的行為特征。比如，蟻群在行進時，道路上的障礙物被螞蟻發(fā)現(xiàn)，它們可以快速地找到在當(dāng)時條件下最好的行進路徑。通過仔細觀察研究，我們發(fā)現(xiàn)螞蟻與螞蟻之間經(jīng)過信息素來實現(xiàn)信息的交流和傳遞，因而實現(xiàn)互相合作，表現(xiàn)出有序而復(fù)雜的行為習(xí)性［1］。蟻群的這種生活習(xí)性引起了一些學(xué)者的注意，20世界90年代，通過觀察和研究自然界蟻群覓食的規(guī)律和習(xí)性，意大利學(xué)者M.Dorigo得出了第一個蟻群算法，進而應(yīng)用在TSP問題的求解過程中。蟻群算法被提出之后，其應(yīng)用范圍逐漸廣泛，算法本身也不斷地被完善改進，形成了一系列的蟻群算法（ant colony optimization ACO）。

1.1 蟻群算法的基本原理

通過觀察和研究，螞蟻外出覓食和獲得食物后回巢穴的路徑中，會在每一處路過的地方留下一些信息素作為標(biāo)記，留下的信息素可以被和它是同一蟻群中比它后來的螞蟻感知出來，該信息素會被后來的螞蟻認為是一種信號，因而對后來的螞蟻產(chǎn)生巨大的影響。詳細地說，就是后來的螞蟻選擇走信息素比較強的路徑的可能性比選擇走信息素比較弱的路徑的可能性大很多，后來的螞蟻再經(jīng)過該路徑，會加強該路徑的信息素的強度。如此循環(huán)往復(fù)，該路徑經(jīng)過的螞蟻越多，信息素的強度就越大，信息素越強，經(jīng)過的螞蟻就越多，該循環(huán)會一直持續(xù)到幾乎絕大多數(shù)螞蟻都行走在最短的路徑為止，該行為就是信息正反饋的一種現(xiàn)象。經(jīng)過信息素的交流，螞蟻就會尋覓到蟻穴和食物之間的最短路徑。圖1是一個生物原型，我們可以通過該原型來了解蟻群算法的原理［2］。

假設(shè)有一群（數(shù)量比較大）螞蟻在尋找食物的過程中，隨意隨機地向不同方向去覓食，其中有一只螞蟻尋找到食物后，沿著來的時候的路徑回到巢穴，在它所經(jīng)過的路徑上會留下信息素，信息素會被蒸發(fā)擴散到四面八方，因而路徑上的信息素的濃度會越來越低。假設(shè)有兩只螞蟻都通過不同的路徑找到食物，而且都沿著來的時候的路徑回到巢穴，從巢穴到食物所在地可以選擇DEF路徑，也可以選擇DF，很明顯，DEF路徑長，而DF路徑短一些，假設(shè)有甲乙丙三只螞蟻去尋找食物，首先，讓甲乙先出發(fā)，它們會隨機選擇DEF和DF兩條路徑，選擇的幾率幾乎一樣，假設(shè)甲選擇的是DF，乙選擇DEF這條路徑，它們同時出發(fā)，當(dāng)甲尋找到食物后準(zhǔn)備返回時，此時因為乙選擇的路徑比較長，可能還在路上，由于DF路徑上已經(jīng)存在有甲尋找食物時留下的信息素，而DEF路徑上因為乙還沒有走完［3］，靠近食物這一端還沒有信息素，而螞蟻的生物特性是沿著信息素濃度強的路徑前進，因此螞蟻甲仍會沿著FD返回，當(dāng)甲返回至巢穴時，螞蟻丙開始出發(fā)，因為DF路徑上，螞蟻甲一去一回，信息素的濃度顯然比DEF強得多，因為乙此時還沒有返回，所以丙肯定會選擇DF路徑去尋找食物，如此循環(huán)往復(fù)，路徑DF上的信息素的濃度只會越來越強，大量的螞蟻個體會選擇DF路徑，這樣一來，絕大多數(shù)螞蟻選擇的都是最短路徑。

圖1 生物原型

1.2 蟻群算法的基本過程

基于信息正反饋的原理，蟻群算法結(jié)合一種啟發(fā)式的算法，通過選擇、刷新及協(xié)和調(diào)整共三個過程來實現(xiàn)優(yōu)化，在進行選擇的流程中，選擇信息素高的路徑的概率比較大；而在刷新的流程中，隨著經(jīng)過該路徑上的螞蟻的數(shù)量越多，該路徑上的信息素的濃度也越大，當(dāng)然，同時根據(jù)時間的推移，揮發(fā)的也越多，信息素的濃度也會下降；在協(xié)和調(diào)整的流程中，通過信息素，螞蟻進行信息的溝通交流和互相協(xié)作。通過選擇和刷新的流程，最短路徑上的信息素的濃度變的越來越高，從而使下一只螞蟻通過較短路徑使算法收斂，與此同時信息素的不斷揮發(fā)又使得算法具有探索新的擴展解的多樣性，以免算法陷入局部的最優(yōu)解［4］。

2 應(yīng)用實例

有關(guān)TSP問題是指某個旅行家旅行要經(jīng)過m個城市，最后回到最早出發(fā)的城市，條件是經(jīng)過各個城市僅一次，同時使得走過的總路程最小。一旦經(jīng)過城市數(shù)量變大，TSP問題的可能解也會迅速地增長，例如，10個城市的TSP問題有大約180 000個可能解，20個城市的TSP問題大約6×106個可能解，50個城市的TSP問題有大約10 525 715 001 371 600個可能解。

下面以TSP問題為例說明蟻群算法的求解過程。假設(shè)蟻群中螞蟻的數(shù)量為m，城市i與城市j之間的距離為dij（i，j=1，2，…，n）；t時處于城市i的螞蟻個數(shù)為bi（t），則時刻在城市i和城市j之間殘留的信息量為τij（t），而且τij（0）=C（C為常數(shù)）。螞蟻k（k=1，2,…，m）在運動過程中，根據(jù)各條路徑上的信息量選擇路徑，且按概率進行選擇，即

其中，Lk表示第k只螞蟻在本次循環(huán)中所走路徑的總長度。

螞蟻由式（1）選擇構(gòu)造路徑，由式（2）更新路徑上的信息素，這兩個步驟重復(fù)迭代搜索整個空間，最終搜索到信息素較濃的路徑形成較短的最優(yōu)路徑。

3 結(jié)語

群體的智能的特別的實現(xiàn)案例——蟻群算法，經(jīng)過模擬生物尋優(yōu)能力來解決實際問題，受到學(xué)術(shù)界的廣泛關(guān)注。從本質(zhì)上講，蟻群算法是一種進化模擬算法，它的出現(xiàn)、產(chǎn)生及發(fā)展和進化算法的發(fā)展是分不開的。假如蟻群算法與群體搜索策略結(jié)合起來應(yīng)用，并且確保群體中的每一個個體之間的信息交流互換，那么蟻群算法就可以表現(xiàn)出進化計算的優(yōu)越性，也可以得到更廣泛的應(yīng)用［6］。

［1］黃席樾,胡小兵.蟻群算法在K-TSP問題中的應(yīng)用［J］.計算機仿真,2004,21（12）:162-164.

［2］曹庭珠.投入產(chǎn)出優(yōu)化模型的發(fā)展與創(chuàng)新機遇［J］.山西財經(jīng)大學(xué)學(xué)報,2005,27（2）:86-90.

［3］何武.基于蟻群優(yōu)化算法的無線傳感器網(wǎng)絡(luò)路由算法研究［D］.成都:西南交通大學(xué),2008．

［4］謝宏.蟻群算法解決TSP問題的研究［J］.農(nóng)業(yè)網(wǎng)絡(luò)信息,2007（3）:22-24.

［5］王冬梅.群集智能優(yōu)化算法的研究［D］.武漢:武漢科技大學(xué),2004.

［6］陳娟,馬曉慧.基于TSP的蟻群算法的研究［J］.現(xiàn)代計算機,2013（3）:8-11.

【責(zé)任編輯：王桂珍 foshanwgzh@163.com】

The application of greedy algorithm in TSP problem

LAI Xue-wei
（Institute of Information Media,Sanmenxia Polytechnic,Sanmenxia 472000,China）

The paper introduces the ant colony algorithm design idea and basic principle and basic process,and then use the ant colony algorithm to solve TSP problem,ant colony algorithm can reflect the evolutionary computation superiority.

ant colonyalgorithm;TSP algorithm;algorithm

TP31

A

1008-0171（2017）03-0072-03

2016-11-17

來學(xué)偉（1981-），男，河南靈寶人，三門峽職業(yè)技術(shù)學(xué)院講師。