求解TSP的改進(jìn)蟻群算法

摘 要:針對蟻群算法存在的搜索時(shí)間長、易限于局部最優(yōu)解等缺陷，提出了一種改進(jìn)的蟻群算法。通過在初始化信息素矩陣中采用候選城市列表減少劣質(zhì)解，在局部搜索中采用聚類進(jìn)行二次搜索，縮小了算法的搜索范圍、改善了解空間的質(zhì)量，提高了搜索速度。仿真結(jié)果表明，改進(jìn)后的蟻群算法在TSP的求解中，收斂速度和全局尋優(yōu)能力均得到較大的提高。

關(guān)鍵詞:蟻群算法(ACA); 旅行商問題; 候選城市列表; 聚類; 蟻群系統(tǒng)(ACS)

中圖分類號:TP301.6文獻(xiàn)標(biāo)志碼:A

文章編號:1001-3695(2010)06-2087-03

doi:10.3969/j.issn.1001-3695.2010.06.026

Improved ant colony algorithm for solving TSP

HOU Wen-jing， MA Yong-jie， ZHANG Yan， SHI Yu-jun

(School of Physics Electronic Engineering， Northwest Normal University， Lanzhou 730070， China)

Abstract:Aimed at the shortcomings， which needing much time and easier to fall in local optimal solution in the ant colony algorithm， this paper proposed an improved algorithm. Through employing the list of candidate cities in the initial pheromone matrix to decrease inferior solutions and using cluster to do the second search in the local search， it could narrow the searching range of algorithm， could improve the quality of the solution space and raise the searching speed. The simulations result for TSP shows that the algorithm is improved greatly in convergence rate and ability of global optimization.

Key words:ant colony algorithm(ACA); TSP; list of candidate cities; clustering; ant colony system(ACS)

蟻群算法又稱做螞蟻算法，是一種用來在圖中尋找優(yōu)化路徑的幾率型算法，利用生物信息激素作為螞蟻選擇后續(xù)行為的依據(jù)。每只螞蟻會對一定范圍內(nèi)其他螞蟻散布的生物信息激素作出反應(yīng)，依據(jù)生物信息激素的強(qiáng)度在每一個(gè)道口對多條路徑選擇作出概率上的判斷并執(zhí)行選擇，由此觀察并影響它們以后的行為。它由意大利學(xué)者Dorigo等人[1]于20世紀(jì)90年代提出，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。目前已經(jīng)應(yīng)用于求解旅行商、二次指派、車輛調(diào)度等經(jīng)典的理論問題，并迅速地推廣到實(shí)際問題領(lǐng)域，成為解決組合優(yōu)化問題最有效的算法之一。

然而，該算法的收斂性和連續(xù)空間尋優(yōu)[2]仍是制約算法廣泛應(yīng)用的主要瓶頸。圍繞這個(gè)問題，眾多學(xué)者發(fā)表了大量有價(jià)值的學(xué)術(shù)文獻(xiàn)。文獻(xiàn)[3]研究了一種與真實(shí)螞蟻系統(tǒng)更加貼近的信息素?cái)U(kuò)散算法，進(jìn)一步真實(shí)地體現(xiàn)了螞蟻信息系統(tǒng);文獻(xiàn)[4]在信息素的局部更新規(guī)則和全局更新規(guī)則中增加了參數(shù)控制;文獻(xiàn)[5]加入了多種蟻群及與之相應(yīng)的信息素調(diào)節(jié)機(jī)制;文獻(xiàn)[6]提出RAACS算法，隨機(jī)選擇部分城市來計(jì)算狀態(tài)轉(zhuǎn)移概率;文獻(xiàn)[7]采用了三種局部優(yōu)化算子來交換搜索路徑中城市的位置;文獻(xiàn)[8]對TSP中的城市進(jìn)行聚類，將其分解成若干小規(guī)模的子城市集合，然后分別進(jìn)行求解，最后將各個(gè)子城市的解組合成完整的待求解;文獻(xiàn)[9]采用了新信息素更新策略——內(nèi)部更新系統(tǒng);文獻(xiàn)[10]提出的KCC-Ants 和 ELU-Ants算法，利用了新的局部信息素更新規(guī)則。上述算法都是單獨(dú)針對信息素或單獨(dú)針對路徑構(gòu)建和局部搜索的改進(jìn)，而本文對蟻群算法的改進(jìn)不僅僅是對信息素的修改，而是與路徑構(gòu)建和局部搜索相結(jié)合，使得新的算法既可以提高收斂速度和全局尋優(yōu)能力，又可以提高解的質(zhì)量。

1 蟻群算法

1.1 基本蟻群算法的數(shù)學(xué)模型[1，2，11]

以求解平面上n個(gè)城市的TSP為例來說明蟻群系統(tǒng)的基本模型。給定n個(gè)城市集合C={c1，c2，…，cn}及城市之間路徑的長短dij(1≤i，j≤n，i≠j)，TSP就是找到一條只經(jīng)過每個(gè)城市一次且回到起點(diǎn)的、最短路徑的回路。設(shè)m表示蟻群中螞蟻的數(shù)目;n表示TSP規(guī)模;dij為城市i與j之間的距離;τij(t)為t時(shí)刻在路徑(i，j)連線上殘留的信息量。在初始時(shí)刻各條路徑上的信息量相等，并設(shè)τij(0)=const(const為常數(shù))。

螞蟻k(k=1，2，…，m)在運(yùn)動過程中，根據(jù)各條路徑上的信息量決定其轉(zhuǎn)移方向。禁忌表tabuk (k=1，2，…，m)記錄螞蟻k已走過的城市。Pkij(t)表示在t時(shí)刻螞蟻k由城市i轉(zhuǎn)移到城市j的狀態(tài)轉(zhuǎn)移概率，如式(1)所示。它表示螞蟻在選擇路徑時(shí)會盡量選擇離自己距離較近且信息素濃度較大的方向。

Pkij(t)=[τij(t)]α[ηij(t)]β∑sallowedk[τis(t)]α[ηis(t)]β j∈allowedk0否則(1)

其中:allowedk={C-tabuk}，表示在t時(shí)刻螞蟻k下一步允許選擇的城市;α為信息啟發(fā)式因子，反映了蟻群在運(yùn)動過程中所殘留的信息量的相對重要程度;β為期望啟發(fā)式因子，反映了期望值的相對重要程度;ηij為啟發(fā)函數(shù)，表示由城市i轉(zhuǎn)移到城市j的期望程度，其表達(dá)式如下:

ηij=1/dij(2)

隨著時(shí)間的推移，要對殘留在各條路徑上的信息素進(jìn)行更新處理。由此(t+n)時(shí)刻在路徑(i，j)上的信息量可按式(3)和(4)的規(guī)則進(jìn)行調(diào)整。

τij(t+n)=(1-ρ)τij(t)Δτij(t)(3)

Δτij(t)=∑mk=1Δτkij(t)(4)

其中:ρ(0≤ρ<1)表示信息素的揮發(fā)系數(shù)，1-ρ表示信息素的殘留因子;Δτij(t)表示本次循環(huán)中路徑(i，j)上的信息素增量，初始時(shí)刻Δτij(t)=0;Δτkij(t)表示第k只螞蟻在本次循環(huán)中留在路徑(i，j)上的信息量。

根據(jù)信息素更新策略的不同，Dorigo等人給出了三種不同的算法模型，分別為Ant-cycle、Ant-density和Ant-quantity，它們的區(qū)別在于Δτkij(t)求法不同。式(5)所示的為Ant-cycle模型。

Δτkij(t)=Q/Lk 第k只螞蟻在本次循環(huán)中經(jīng)過(i，j)0否則(5)

其中:Q表示信息素強(qiáng)度，它在一定程度上影響算法的收斂速度;Lk表示第k只螞蟻在本次循環(huán)中所走路徑的總長度。

Dorigo等人認(rèn)為在Ant-density和Ant-quantity算法中，螞蟻在構(gòu)建解的同時(shí)釋放信息素;而在Ant-cycle算法中，螞蟻在完整地構(gòu)造問題的解之后再釋放信息素，利用的是整體信息，效果要好于前兩種算法。因此通常采用式(5)作為蟻群算法的基本模型。

1.2 蟻群系統(tǒng)算法

蟻群系統(tǒng)(ant colony system，ACS)是在基本蟻群算法的基礎(chǔ)上使用了未出現(xiàn)的新的機(jī)制和策略，進(jìn)一步獲得較好的性能。

在蟻群系統(tǒng)中，其狀態(tài)轉(zhuǎn)移規(guī)則采用偽隨機(jī)比例規(guī)則，如式(6)所示:

j=arg maxs∈allowedk{[τis]α[ηis]β} 如果q≤q0式(1)否則(6)

其中:q是均勻分布在區(qū)間[0，1]中的一個(gè)隨機(jī)變量;q0是一個(gè)算法參數(shù)(0≤q0≤1)。在這種規(guī)則下，每當(dāng)螞蟻要選擇向哪一個(gè)城市轉(zhuǎn)移時(shí)，就產(chǎn)生一個(gè)在[0，1]內(nèi)的隨機(jī)數(shù)，根據(jù)這個(gè)隨機(jī)數(shù)的大小按式(6)確定用哪種方法產(chǎn)生螞蟻轉(zhuǎn)移的方向。

在蟻群系統(tǒng)中，其信息素更新規(guī)則采用全局更新規(guī)則和局部更新規(guī)則，如式(7)(8)所示:

τij←(1-ρ)τij+ρΔτbsij (i，j)∈Tbs(7)

其中:Tbs是最優(yōu)路徑，Cbs是Tbs的長度，Δτbsij=1/Cbs。在蟻群系統(tǒng)中信息素的蒸發(fā)和信息素的釋放都只在構(gòu)成Tbs的邊上執(zhí)行，這種方式可以降低算法的時(shí)間復(fù)雜度，從O(n2)降低到O(n)。

τij←(1-ε)τij+ετ0(8) 

其中:ε和τ0是兩個(gè)參數(shù)，ε滿足0<ε<1，τ0是信息素的初始值。局部更新的作用在于，螞蟻每經(jīng)過(i，j)，該邊的信息素τij將會減少，從而其他螞蟻選中該邊的概率相對減少，這將增加探索未使用過的邊的機(jī)會，使得算法不易陷入停滯狀態(tài)。

2 蟻群算法的改進(jìn)

由于蟻群中個(gè)體根據(jù)信息素濃度正反饋來產(chǎn)生新解，隨著正反饋的增強(qiáng)，降低了全局搜索能力，易陷入局部最優(yōu)，影響求解質(zhì)量;其次，由于蟻群中個(gè)體的運(yùn)動是隨機(jī)的，當(dāng)群體規(guī)模較大時(shí)，很難在較短的時(shí)間內(nèi)從大量雜亂無章的路徑中找出一條較好的路徑。為此提出以下改進(jìn)。

2.1 采用新的初始化信息素

在對TSP的研究中發(fā)現(xiàn)，在其解空間中，大部分解都是劣質(zhì)解，對優(yōu)質(zhì)解的尋找產(chǎn)生很大的阻力。如果能夠減少這些劣質(zhì)解、縮小解空間的搜索范圍，就能提高解空間的質(zhì)量，進(jìn)而能夠快速找到全局最優(yōu)解，提高算法性能。

在TSP的最優(yōu)解中絕對不含任何交叉線路的情況[11];對于每個(gè)城市而言，從離其最近的幾個(gè)城市中選擇一個(gè)作為近鄰城市，而不是從剩下城市中任選一個(gè)，也必然可以找到最優(yōu)解。它選擇的下一個(gè)城市應(yīng)該是離它最近的城市[5]。因此，在改進(jìn)算法中采取加入候選城市列表、加強(qiáng)城市間的相對位置對最優(yōu)解的作用，以相對城市之間的距離及其排列順序?yàn)橐罁?jù)，進(jìn)行初始化τij(0)的設(shè)置，即在給定城市坐標(biāo)的同時(shí)，其特征也已固定，不會隨著搜索的進(jìn)行而改變。在加入初始化公式后，使得搜索由于靜態(tài)特征的給定而更加具有目的性、指導(dǎo)性和確定性，能夠很快得到最優(yōu)的路徑。算法改進(jìn)的初始化信息素步驟如下:

a)計(jì)算城市之間的距離，并按照從小到大的順序排列。

b)計(jì)算每個(gè)城市的最近鄰列表，如果城市規(guī)模N<50，采用最近鄰城市數(shù)目q=6。

c)按照式(9)計(jì)算初始化信息素:

τij(0)=(q-l+1)×dijn×(dij)max 如果城市j在城市i的最近鄰列表中(dij)minn×(dij)max否則(9)

其中:(dij)max是以城市i為中心，離城市i最遠(yuǎn)的城市距離;(dij)min是以城市i為中心，離城市i最近的城市距離;q是最近鄰城市的數(shù)目;l是城市j在城市i的最近鄰列表中的排列次數(shù);n是城市的規(guī)模數(shù)。

2.2 局部搜索中通過聚類進(jìn)行二次搜索

在對蟻群算法的研究中，經(jīng)過大量的數(shù)據(jù)測試發(fā)現(xiàn)，對于一個(gè)靜態(tài)的N規(guī)模的城市集合，在每次的搜索過程中，有某一部分或幾部分城市的順序是“已經(jīng)固定的”。所謂已經(jīng)固定的是指在一次搜索的迭代中，這些城市的順序以固定的模式多次出現(xiàn)。在這種情況下，可以將這些城市看做一個(gè)整體，進(jìn)而可以在此基礎(chǔ)上減小城市的整體規(guī)模，利用蟻群算法在低維空間具有較好的搜索特性降低算法的復(fù)雜性、提高算法的性能。因此，在改進(jìn)算法的局部搜索部分中:a)加入一個(gè)子程序f_search(d1，d2)，即尋找兩個(gè)迭代最優(yōu)解中相同的城市集合;b)將這些城市集合看成一個(gè)整體，用子程序Jiaoji重新進(jìn)行搜索，即檢測交集中是否有交叉的現(xiàn)象。將這些城市集合變成一個(gè)虛擬的新城市加入到原來的城市集合中，降低原城市規(guī)模。c)對降低城市規(guī)模后的新城市集合進(jìn)行“二次搜索”，進(jìn)而得到較好的解。通過聚類進(jìn)行二次搜索主要體現(xiàn)在較大城市規(guī)模的TSP上。實(shí)現(xiàn)步驟如下:

a)在第一次應(yīng)用蟻群算法的基礎(chǔ)上，從迭代最優(yōu)解中取出任意的兩條路徑d1、d2。

b)運(yùn)行子程序f_search(d1，d2)，并將交集結(jié)果保存到K中。

c)用子程序Jiaoji進(jìn)行二次搜索，并將結(jié)果還原成原來的城市規(guī)模。

d)判斷最終找到的最優(yōu)路徑和d1、d2，輸出經(jīng)過兩次搜索后的全局最優(yōu)解。

由此，改進(jìn)后的ACS算法流程可以描述如下:

a)初始化參數(shù)Q、C、NCmax(最大迭代次數(shù))、α、β、ρ、q0。

b)將m只螞蟻隨機(jī)地放在m個(gè)城市中，計(jì)算各個(gè)城市的距離矩陣及其最近鄰矩陣，按照式(10)初始化信息素矩陣，并將結(jié)果存放到τij(0)中。

c)設(shè)置迭代次數(shù)NCmax為0，隨機(jī)選擇螞蟻的初始位置，并將該位置放置到對應(yīng)的tabu表中。

d)按照式(6)計(jì)算每只螞蟻k將要轉(zhuǎn)移的下一個(gè)城市，若當(dāng)前城市為i，選擇的下一個(gè)城市為j，此時(shí)將j放入到對應(yīng)的tabuk中，直到每只螞蟻搜索完成一次路徑回路。

e)計(jì)算每只螞蟻的回路長度Lk，并記錄當(dāng)前最好的解。

f)若迭代次數(shù)達(dá)到NCmax，則跳到i)，否則跳到g)。

g)按照式(7)(8)更新全局信息素矩陣和局部信息素矩陣。

h)置空Δτij，置tabuk表為空，NC←NC+1，跳轉(zhuǎn)到c)。

i)輸出迭代最優(yōu)解。

j)以上面得出的迭代最優(yōu)解為基礎(chǔ)，任意取出其中的兩條回路d1、d2，調(diào)用子程序f_search(d1，d2)，尋找交集部分并將結(jié)果保存到矩陣K中。

k)調(diào)用子程序Jiaoji進(jìn)行二次搜索，并將結(jié)果k1還原成原來的城市集合的路徑。

l)將最后找到的最優(yōu)解與d1、d2進(jìn)行比較，輸出全局最優(yōu)解。

3 仿真結(jié)果及分析

仿真算例選用了TSP測試庫TSPLIB中的Oliver30和KroA100以及CTSP(中國31個(gè)省會城市的旅行商問題)， 并將改進(jìn)的算法與基本蟻群算法進(jìn)行比較。

實(shí)驗(yàn)中參數(shù)設(shè)置分別為:α=1，β=3，ρ=0.1，q0=0.6，Oliver30、CTSP，Q=100;KroA100，Q=1 000。實(shí)驗(yàn)結(jié)果如表1和圖1~4所示。

表1 Oliver30問題的不同算法結(jié)果比較

最短路徑迭代次數(shù)(本文算法)迭代次數(shù)(基本算法)文獻(xiàn)[5]算法

424.635 6266427

424.464 7288741

423.973 825136116

423.740 916179137

表1中最短路徑長度為最優(yōu)路徑的長度，迭代次數(shù)是取10次實(shí)驗(yàn)的平均而得到的。從表1中可以看出，本文改進(jìn)的蟻群算法平均16次迭代就能搜索到目前最好解(423.7409)，而用基本蟻群算法和文獻(xiàn)[5]中的算法分別要用179次和137次迭代才能夠搜索到。就次優(yōu)解而言，在取得相同結(jié)果的情況下，改進(jìn)后的算法所需要的迭代次數(shù)比基本算法和文獻(xiàn)[5]中的算法少得多。

圖1、2是Oliver30問題中運(yùn)用改進(jìn)算法所找到的最優(yōu)路徑和進(jìn)化曲線。從圖中可以看出，改進(jìn)后的蟻群算法不僅在求解能力上有明顯優(yōu)勢，而且算法的執(zhí)行效率也得到提高。

借鑒上述探討的結(jié)果，將該算法用于CTSP和KroA100問題，實(shí)驗(yàn)結(jié)果如圖3和4(圖中‘++’表示基本蟻群算法的進(jìn)化曲線;‘—’表示本文算法的進(jìn)化曲線)所示。從圖中可以看出，對于基本蟻群算法易限于局部最優(yōu)，而改進(jìn)后的算法能夠在較少的迭代次數(shù)中找到最優(yōu)解，較好地避免了局部最優(yōu)。

4 結(jié)束語

針對基本蟻群算法存在搜索時(shí)間長、易限于局部最優(yōu)的缺點(diǎn)，提出了將信息素管理與路徑構(gòu)建和局部搜索相結(jié)合的改進(jìn)蟻群算法。通過對TSP的算例進(jìn)行實(shí)驗(yàn)結(jié)果比較， 顯示了算法能夠克服基本蟻群算法的缺陷，每次求解均能找到最優(yōu)解，且求解速度優(yōu)于同期的研究結(jié)果。對其他多例TSP的求解均獲得了類似結(jié)果， 證明本文采取的改進(jìn)方法是有效和可行的。

參考文獻(xiàn):

[1]DORIGO M， MANIEZZO V， COLORNI A. The ant system:optimization by a colony of cooperating agents[J]. IEEE Trans on System， Man， and Cybernetics，1996，26(1):29-41.

[2]段海濱，王道波，朱家強(qiáng)，等.蟻群算法理論及應(yīng)用研究的進(jìn)展[J].控制與決策，2004，19(12):1321-1326.

[3]黃國銳，曹先彬，王煦法，基于信息素?cái)U(kuò)散的蟻群算法[J].電子學(xué)報(bào)，2004，32(5):865-868.

[4]李金漢，杜德生.一種改進(jìn)蟻群算法的仿真研究[J].自動化技術(shù)與應(yīng)用，2008，27(2):58-60.

[5]徐精明，曹先彬，王煦法.多態(tài)蟻群算法[J].中國科學(xué)技術(shù)大學(xué)學(xué)報(bào)，2005，35(1):59-65.

[6]QI Cheng-ming.An ant colony system hybridized with randomized algorithm for TSP[C]//Proc of the 8th ACIS International Conference on Software Engineering， Artificial Intelligence，Networking，and Para-llel/Distributed Computing.2007:461-465.

[7]龔本燦，李臘元，蔣廷耀，等.基于局部優(yōu)化策略求解TSP的蟻群算法[J].計(jì)算機(jī)應(yīng)用研究，2008，25(7):1974-1976.

[8]胡小兵，黃席樾.對一類帶聚類特征TSP問題的蟻群算法求解[J].系統(tǒng)仿真學(xué)報(bào)，2004，16(2):2683-2686.

[9]PINTEA C M， DUMITRESCU D. Improving ant systems using a local updating rule[C]//Proc of the 7th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing.2005:295-298.

[10]NAIMI HM， TAHERINEJAD N. New robust and efficient ant colony algorithms:using new interpretation of local updating process[J].Expert Systems with Applications，2009(36):481-488.

[11]段海濱.蟻群算法原理及其應(yīng)用[M].北京:科學(xué)出版社，2005.