聚類處理的蟻群算法在旅行商問題中的應(yīng)用

孟喜艷，傅文靈，馬 波，方 壯

(1．恩施職業(yè)技術(shù)學(xué)院 人文科學(xué)系，湖北 恩施445000;2．湖北民族學(xué)院 理學(xué)院，湖北 恩施445000)

旅行商問題(Traveling Saleman Problem，TSP)是指已知n個城市的兩兩距離，商人從自己所處的城市出發(fā)，確定一條訪遍各個城市顧客一次且僅一次的最短路徑問題．若將城市記為頂點集V={v1，v2，…，vn}，相連接頂點vi與vj組成的邊eij構(gòu)成集合記為邊集E，相連接頂點vi與vj之間的距離dij構(gòu)成的距離矩陣記為D，TSP 問題的圖論描述即為:在圖G=(v，e)中確定一條長度最短的Hamilton 回路．

TSP 是一個NP 完全難題，很多典型的組合優(yōu)化問題如芯片加工問題、電路板設(shè)計中的鉆孔問題、航跡規(guī)劃等，最終都可歸結(jié)為TSP 問題． 因此快速、有效地解決TSP 有著重要的理論價值和極高的實際應(yīng)用價值．相對于傳統(tǒng)算法，蟻群算法［1］自1991 年Dorigo 提出后，就成功應(yīng)用到TSP 問題，并吸引了很多學(xué)者對其進(jìn)行研究．黃翰等［2］分析了蟻群算法的收斂速度;徐紅梅等［3］分析了參數(shù)的初始設(shè)置對蟻群算法的影響;冀俊忠［4－5］、李成兵［6］、吳華峰［7］、梁志茂等［8］通過修正信息素更新方式，對蟻群算法進(jìn)行了改進(jìn);胡俊鵬［9］研究了雙向選擇相遇算法，提高了搜索速度;懷麗波等［10］討論了蟻群算法在其他優(yōu)化方面的應(yīng)用．春花等［11］研究了蟻群算法參數(shù)的設(shè)置;孫凱等［12］還將蟻群算法與其它優(yōu)化算法相融合，提高了部分TSP 問題的求解精度．

對于大規(guī)模的TSP，蟻群算法容易陷入局部最優(yōu)．考慮到旅行商問題的實際背景，商人訪問一個城市群中的每一個城市后，再訪問下一個城市群是合理的，為此，先將所有城市聚類成若干城市群后，在每一個城市群內(nèi)求解TSP 子問題，然后選擇合適的城市群之間的連接線路，使總的的連接路線最短，這樣可以降低算法的復(fù)雜度，最終得到所有城市最佳巡游路線的一個滿意解．依據(jù)這一思想，盧欣［13］對這一算法的復(fù)雜度進(jìn)行了分析;丁建立［14］以pcb442 問題為例，通過動態(tài)聚類結(jié)合蟻群優(yōu)化算法得到了該問題的一個近似解，冀俊忠［4］、侯文靜［15］、任志剛等［16］通過不同的類與類之間連接方式結(jié)合蟻群算法，得到了大規(guī)模TSP 的近似解．通過聚類的方法求解TSP 問題，其準(zhǔn)確性依賴于各城市群建的連接順序，這樣，如何從已有的分類及連接順序中找到一個滿意的巡游圈，就是一個值得研究的問題，本文通過蟻群算法確定了城市群的連接順序，并在此順序下，通過標(biāo)記城市群接入點的方式，以TSP 問題測試庫中的Pr152 數(shù)據(jù)為例，得到了一個最佳巡游圈的滿意解．

1 算法基本思想

如圖1 示，將所有城市聚類，圖1 所示聚成4 個城市群，在每一城市群中用蟻群算法求解其最佳巡游圈，并求出城市群的連接順序，圖1 中每一類的最佳巡游圈如黑色線條所示，城市群的連接順序為G1→G2→G3→G4→G1．任給一點P1∈G1，在下一個城市群G2找到距P1離最短的點P2，將P2標(biāo)記為G2的接入點，P'2，P″2為P2在G2中巡游圈中的鄰接點;在第三個城市群G3中找到距P'2，P″2最 短 的 點P'G3，P″G3，并 分 別 求 其 距 離DP'2P'G3，DP″2P″G3，計算DP'2P'G3－w'2，DP″2P″G3－w″2，比較兩者中的最小值，將最小值對應(yīng)的在G3中的點記為P3，P3作為G3城市群的接入點，P'3，P″3為P3在G3城市群中巡游圈中的鄰接點;

按此方法依次經(jīng)行下去，當(dāng)同一個點有兩次標(biāo)記為接入點時，輸出一個巡游圈，更新P1．尋找下一個巡游圈，當(dāng)P1遍歷完第一個城市群中的每一個點時，結(jié)束循環(huán)．將巡游圈距離最小者作為輸出．

圖1 算法示意圖Fig．1 Schematic algorithm

2 聚類分析的蟻群算法

2．1 聚類分析

在上節(jié)中，首先要對所有城市進(jìn)行聚類．本文采用的是譜系聚類以城市點間的歐氏距離來進(jìn)行分類，譜系聚類是對統(tǒng)計樣本進(jìn)行定量分析的一種多元統(tǒng)計分析法，該方法是對待處理樣本進(jìn)行依次歸類，然后由聚類的方法得到一個二叉樹聚類圖．觀測點之間的距離能夠用歐氏距離或歐氏距離的平方來計算，而類間聚類的計算方法有多種，這里計算類間距離的方法是Ward 最小方差法:若現(xiàn)在有n個觀測數(shù)，v個變量數(shù)，G為分類的個數(shù)，xi為i個觀測，CK是當(dāng)前水平G的第K類，NK為CK中的觀測個數(shù)，均值向量為，類CK中的均值向量(中心)為為歐氏長度是總離差平方和，是類CK的類內(nèi)離差平方和，PG=ΣWJ為聚類水平G對應(yīng)的各類的類內(nèi)離差平方和的總和．假設(shè)某一步聚類過程中把類CK和類CL合并為下一水平的類CM，那么定義BKL=WM－WK－WL為合并導(dǎo)致的類內(nèi)離差平方和的增量．用d(x，y)來表示兩個觀測點之間的距離或非相似性測度，DKL是第G水平的類CK和類CL之間的距離或非相似性測度．采用Ward 最小方差法時

當(dāng)觀測距離為d(X，Y)=‖X－Y‖2/2 時遞推公式為:

2．2 基本蟻群優(yōu)化算法

設(shè)C表示觀測點的集合，bi(t)表示t時刻位于城市點i的螞蟻數(shù)目，τij(t)為t時刻路徑(i，j)上的信息量，m為蟻群中螞蟻的總數(shù)目，n表示TSP 規(guī)模，則是t時刻集合C中所有城市點任意兩個城市點間殘留信息素量的集合，設(shè)定在最開始時刻每條路徑上的存儲信息量相等，設(shè)定τij(0)=const．因為任意螞蟻k在遍歷過程中不能重復(fù)經(jīng)過同一個城市，建立禁忌表tabuk(k=1，2，…，11)來記錄螞蟻已經(jīng)過的城市，禁忌表隨著螞蟻的運(yùn)動做動態(tài)變化．搜索過程中，每只螞蟻根據(jù)每條路徑上的信息量及路徑本身的啟發(fā)信息來計算狀態(tài)轉(zhuǎn)移概率，建立螞蟻k由i城市轉(zhuǎn)移到j(luò)城市的狀態(tài)轉(zhuǎn)移概率如下［16］:

其中:ηij表示從i到j(luò)的期望程度，一般認(rèn)為從i到j(luò)的距離的倒數(shù)即ηij=1/dij，成為啟發(fā)函數(shù);α 為信息啟發(fā)式因子，表示路徑的相對重要性，反映了螞蟻在搜索路徑過程中所積累的信息量在螞蟻運(yùn)動中所起的作用，其值越大，那么其它螞蟻走過的路徑就更容易被后續(xù)螞蟻選擇，螞蟻之間的相互協(xié)作性也就越強(qiáng);β 為期望啟發(fā)式因子，反映了螞蟻在搜索路徑過程中啟發(fā)信息在螞蟻選擇路徑中所受到重視程度，其值越大，則該狀態(tài)轉(zhuǎn)移概率就會越接近貪心規(guī)則，越傾向于最優(yōu)路徑;pkij(t)表示信息素較多且距離較短的路徑被選中的概率越大．

引入信息素在算法中的全局更新規(guī)則:當(dāng)全部螞蟻完成一次游歷后，在其走過的路徑上留下一定量的信息素，從而改變信息素，則t+n時刻的信息素修改公式:

其中:ρ 表示信息素?fù)]發(fā)系數(shù)，則1－ρ 表示信息素的持久性系數(shù)，ρ∈［0，1);初始時刻)表示第k只螞蟻在本次迭代中留在邊eij上信息素量，若螞蟻k沒有經(jīng)過eij，則的值為零，所以將表示為:

其中:Q表示信息素強(qiáng)度;Ck表示第k只螞蟻在本次周游中所走過的路徑長度．

信息素局部更新規(guī)則:在路徑構(gòu)建過程中，對每只螞蟻，每當(dāng)其經(jīng)過一條eij時，它將立刻對這條邊進(jìn)行信息素的更新:

其中:ξ 是信息素局部揮發(fā)速率，滿足0 ＜ξ ＜1;τ0是信息素的初始值．

在算法的構(gòu)建過程中，信息啟發(fā)式因子α 和期望值啟發(fā)式因子β 對算法性能的影響和作用是相互配合、密切相關(guān)的，要得到好的優(yōu)化結(jié)果必須適當(dāng)?shù)倪x擇α 和β 的取值范圍一般的選取范圍為α=0．5～5，β =1～5．研究表明信息素的持久性系數(shù)1－ρ 關(guān)系到蟻群算法的全局搜索能力及收斂速度，系數(shù)過大則以前搜索過的路徑被再次選擇的可能性過大，也會影響到算法的隨機(jī)性能和全局搜索能力，反之減少系數(shù)雖可以提高算法的隨機(jī)性能和全局搜索能力但又會使得算法的收斂速度降低，因此在信息素的持久性系數(shù)選擇的時候要對全局搜索能力和收斂速度兩方面做出合理折中的選擇．

在TSP 測試庫中以O(shè)liver30(問題規(guī)模30)數(shù)據(jù)為例，設(shè)定參數(shù):α =1，β =5，ρ =0．1，Q=100，最大迭代次數(shù)為200 次，計算得到圖2 所示結(jié)果．

由圖2 可知蟻群優(yōu)化算法在解決TSP 上能較快得到可行解，結(jié)果也較為理想，但隨著問題規(guī)模的增加，算法的計算復(fù)雜度也在增加，收斂速度變慢，極有可能陷入局部最優(yōu)解，例如取測試庫中的pr107(問題規(guī)模107)測試時，得到如圖3 所示的結(jié)果．

圖2 Oliver30 的TSP 最短路徑及收斂分析Fig．2 The shortest route and the convergence analysis of Oliver 30

圖3 Pr107 的TSP 最短路徑及收斂分析Fig．3 The shortest route and the convergence analysis of Pro107

圖3 所示，按收斂分析顯示最短路徑已收斂到最優(yōu)解，但從其結(jié)果明顯可看出此結(jié)果并非最優(yōu)． Pr107問題的最優(yōu)解為44303，而圖3 所示的路徑的最優(yōu)解為45845．大量的實驗顯示ACO 算法因為其本身的魯棒性、自學(xué)習(xí)能力強(qiáng)能特點能有效解決小規(guī)模TSP 問題，但隨著問題的規(guī)模變大、復(fù)雜度增加，迭代次數(shù)也要增加，時間花費(fèi)變大且不能得到全局最優(yōu)解．

2．3 基于聚類處理蟻群算法的步驟

針對單純的ACO 算法已不能完全解決大規(guī)模TSP 問題，為了能有效求得可行解并求解過程中提高求解速度，因此在ACO 算法的基礎(chǔ)上加入聚類處理，通過聚類分析，將相似性大的城市點聚為一類，相似性小的分開，每個小類可做一次TSP 子問題求解，然后將每個類作為一個城市點，再進(jìn)行一次求解，最后即可合成所需問題的可行解．如此一來，既保留了算法的特點，同時也提高了算法的求解速度，可避免出現(xiàn)局部最優(yōu)現(xiàn)象．其基本步驟如下:

1)對所有城市進(jìn)行聚類．得到若干個城市群G1，G2，…，Gk;

2)利用蟻群算法，求每一個城市群的最佳巡游圈CG1，CG2，…，CGk．并求每一類城市的聚類中心;

3)確定聚類中心的連接順序，并將其作為城市群的連接順序，不妨設(shè)其順序就為G1，G2，…，Gk;

4)確定城市群的接入點．任給Pi∈Gi，在Gi+1中確定到Pi距離最短的點Pi+1，將Pi+1標(biāo)記為Gi+1的接入點，P'i+1，P″i+1為Pi+1在第二類中巡游圈中的鄰接點;在Gi+2中確定到P'i+1，P″i+1距離最短的點P'Gi+2，P″Gi+2，并分別求其距離DP'i+1P'Gi+2，DP″i+1P″Gi+2，計算DP'i+1P'Gi+2－w'i+1，DP″i+1P″Gi+2－w″i+1，比較兩者中的最小值，將最小值對應(yīng)的在Gi+2中的點記為Pi+2，Pi+2作為Gi+2的接入點，P'i+2，P″i+2為Pi+2在Gi+2中巡游圈中的鄰接點;按此方法依次經(jīng)行下去，當(dāng)同一個點有兩次標(biāo)記為接入點時，輸出一個巡游圈，更新Pi及接入城市標(biāo)志．尋找下一個巡游圈，當(dāng)Pi遍歷完Gi中的每一個點時，結(jié)束循環(huán)．將巡游圈距離最小者作為輸出．

3 實驗結(jié)果及分析

同樣的設(shè)定參數(shù)α=1，β=5，ρ=0．1，Q=100，最大迭代次數(shù)為500 次，分成30 個城市群，以測試數(shù)據(jù)庫中的Pr152 為例，計算得到如圖4 所示，其可行解為73 683 與其最優(yōu)解73 682 的誤差不超過0．001 5%．

圖4 本文算法處理Pr152 所得結(jié)果Fig．4 The processing result of pr152

4 結(jié)論

本文所提出的在ACO 蟻群優(yōu)化算法的基礎(chǔ)上加入聚類的處理，對大規(guī)模的TSP 問題進(jìn)行分解，大大降低了問題的難度系數(shù)，也減小了問題的復(fù)雜度，同時也保留了算法的求解特點．在聚類的基礎(chǔ)上，問題被細(xì)化，算法求解速度得到提高，避免了算法本身易陷入停滯現(xiàn)象的局限性，但此方法也會因聚類的方法不一樣而得到不一樣的結(jié)果，同時還會因城市點間的相似程度而影響聚類結(jié)果，所以對于這類的大規(guī)模TSP 問題的求解還需具體考慮到實際問題，從實際出發(fā)才能更好的解決問題．

［1］ Colorni A，Dorigo M，Maniezzo V．Distributed optimization by ant colonies． Proceeding of the 1st European Conference on Arificial Life［C］//Paris，F(xiàn)rance:Elsevier Publishing，1991:134－142．

［2］ 黃翰，郝志峰，吳春國，等．蟻群算法的收斂速度分析［J］．計算機(jī)學(xué)報，2007(8):1344－1353．

［3］ 徐紅梅，陳義保，劉加光，等．蟻群算法中參數(shù)設(shè)置的研究［J］．山東理工大學(xué)學(xué)報:自然科學(xué)版，2008(1):7－11．

［4］ 冀俊忠，黃振，劉椿年．基于聚類和分段優(yōu)化的蟻群算法［J］．北京工業(yè)大學(xué)學(xué)報，2008(4):434－440．

［5］ 冀俊忠，黃振，劉椿年．一種快速求解旅行商問題的蟻群算法［J］．計算機(jī)研究與發(fā)展，2009(6):968－978．

［6］ 李成兵，郭瑞雪，李敏．改進(jìn)蟻群算法在旅行商問題中的應(yīng)用［J］．計算機(jī)應(yīng)用，2014(S1):131－132．

［7］ 吳華鋒，陳信強(qiáng)，毛奇凰，等．基于自然選擇策略的蟻群算法求解TSP 問題［J］．通信學(xué)報，2013(4):165－170．

［8］ 梁志茂，騰建華，何晉．基于改進(jìn)蟻群算法的TSP 問題研究［J］．云南民族大學(xué)學(xué)報:自然科學(xué)版，2010，19(3):220－223．

［9］ 胡俊鵬．基于雙向選擇的蟻群相遇算法的優(yōu)化［J］．湖北民族學(xué)院學(xué)報:自然科學(xué)版，2013，31(1):60－64．

［10］ 懷麗波，崔某一，趙在慧．基于改進(jìn)的蟻群算法的教室管理的優(yōu)化問題［J］．延邊大學(xué)學(xué)報:自然科學(xué)版，2014，40(4):335－339．

［11］ 春花，特日格勒，任哲明．關(guān)于蟻群算法參數(shù)的設(shè)定［J］．內(nèi)蒙古民族大學(xué)學(xué)報:自然科學(xué)版，2011，26(4):402－404．

［12］ 孫凱，吳紅星，王浩，等．蟻群與粒子群混合算法求解TSP 問題［J］．計算機(jī)工程與應(yīng)用，2012(34):60－63．

［13］ 盧欣，李衍達(dá)．TSP 問題分層求解算法的復(fù)雜度研究［J］．自動化學(xué)報，1999(2):139－142．

［14］ 丁建立，陳增強(qiáng)，袁著祉．基于動態(tài)聚類鄰域分區(qū)的并行蟻群優(yōu)化算法［J］．系統(tǒng)工程理論與實踐，2003(9):105－110．

［15］ 侯文靜，馬永杰，張燕，等．求解TSP 的改進(jìn)蟻群算法［J］．計算機(jī)應(yīng)用研究，2010(6):2087－2089．

［16］ 任志剛，馮祖仁，柯良軍，等．基于聚類分析的增強(qiáng)型蟻群算法［J］．控制與決策，2010(8):1201－1206．