來學(xué)偉

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

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

來學(xué)偉

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

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

蟻群算法；TSP問題；算法

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

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

1.1 蟻群算法的基本原理

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

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

圖1 生物原型

1.2 蟻群算法的基本過程

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

2 應(yīng)用實(shí)例

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

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

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

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

3 結(jié)語

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

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

［2］曹庭珠.投入產(chǎn)出優(yōu)化模型的發(fā)展與創(chuàng)新機(jī)遇［J］.山西財(cái)經(jīng)大學(xué)學(xué)報(bào),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)代計(jì)算機(jī),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é)院講師。