基于自適應層次譜聚類與遺傳優(yōu)化的TSP算法

楊彩虹, 楊明

(1.中北大學 理學院，山西 太原 030051;2.信息探測與處理山西省重點實驗室，山西 太原 030051 )

1 引 言

旅行商問題(TSP)是一個經(jīng)典的NP難度的組合優(yōu)化問題，也是計算機科學和地理信息科學等許多領域的研究熱點[1-4].大規(guī)模的TSP得到最優(yōu)解非常困難，因此人們提出了許多近似解法，但由于這些算法的自身缺陷，獲取的近似解可能會遠遠偏離于最優(yōu)解[5],而且許多實際問題不能在有效的時間內(nèi)找到相對較優(yōu)的解，促使啟發(fā)式算法的出現(xiàn)，如遺傳算法[6]、粒子群優(yōu)化算法、蟻群優(yōu)化算法[7-8]、人工神經(jīng)網(wǎng)絡、進化策略、進化編程、禁忌搜索和免疫計算[9]等.

遺傳算法是建立在自然選擇和自然遺傳機理基礎上的迭代自適應概率性搜索算法[6]，它的優(yōu)點在于能很好地處理約束，魯棒性強，具有潛在的并行性，全局搜索能力強；缺點是收斂較慢，甚至迭代難以收斂，局部搜索能力弱，運行時間長，當問題規(guī)模較大時，迭代過程中會占用很大的內(nèi)存空間，再加上遺傳算子中的交叉算子使得染色體之間具有很大的相似性，可能導致搜索停滯不前，使種群多樣性減少，同時，由于變異的力度不夠，遺傳算法的爬山能力很弱，導致種群多樣性得不到補充，使算法出現(xiàn)早熟特征[5-6].針對傳統(tǒng)遺傳算法出現(xiàn)的收斂慢及早熟現(xiàn)象，提出了一種基于自適應層次譜聚類與遺傳優(yōu)化算法求解大規(guī)模TSP.

2 自適應層次譜聚類

為提高大規(guī)模TSP的求解效率，首先對數(shù)據(jù)集進行聚類，將大規(guī)模TSP轉(zhuǎn)換為一個GTSP和多個小規(guī)模TSP的求解，針對聚類后數(shù)據(jù)集規(guī)模的不確定性以及傳統(tǒng)譜聚類高斯核函數(shù)尺度參數(shù)的影響，提出了利用自適應層次譜聚類的方法，該算法首先構(gòu)建出一種基于測地距離和局部密度的自適應相似矩陣，并應用到譜聚類算法中實現(xiàn)城市的初步聚類，當聚類城市規(guī)模超過設定閾值，用上述自適應譜聚類算法進行層次聚類，直到每類城市規(guī)模均小于閾值時停止聚類.

2.1 自適應相似矩陣的構(gòu)建

譜聚類算法的核心思想是對待聚類數(shù)據(jù)點的相似矩陣(拉普拉斯矩陣)進行特征分解，并對其特征向量聚類,因此相似矩陣的構(gòu)建很大程度上影響了聚類的效果.

2.1.1 距離函數(shù)

譜聚類在構(gòu)建相似性矩陣時，距離函數(shù)的選擇尤為重要.測地距離是由Tenenbaum等人最早提出[10]，可以有效表示流體結(jié)構(gòu)上數(shù)據(jù)點間的真實距離，故選擇測地距離作為距離函數(shù)可提高聚類精度.測地距離計算過程：

1)輸入數(shù)據(jù)集X=[x1,x2,…,xn]，并求得每個數(shù)據(jù)點的l個歐式近鄰點；

3)任兩點測地距離

(1)

其中T=[1,2,…,n].

2.1.2 局部密度

根據(jù)文獻[11] 提出的基于共享近鄰的相似性度量聚類，可利用兩點間的共享近鄰來表示兩點間的局部密度

Dens(xi,xj)=|n(xi,p)∩n(xj,p)|

(2)

其中，n(xi,p)為距離xi最近的前p個點，n(xj,p)為距離xj最近的前p個點.一般地，取共享近鄰數(shù)p=round(樣本數(shù)×3%).

2.1.3 自適應相似矩陣

為消除傳統(tǒng)譜聚類高斯核函數(shù)尺度參數(shù)的影響，構(gòu)建了一種密度自適應的相似矩陣S=[sij]n×n，其中

(3)

其中，σi=norm((xi-xil),2)表示數(shù)據(jù)點xi到其第l個最近鄰樣本點xil的歐式距離，σj=norm((xj-xjl),2)表示數(shù)據(jù)點xj到其第l個最近鄰樣本點xjl的歐式距離，一般地，取l=7[12-13].

2.2 自適應譜聚類過程

Step 1輸入數(shù)據(jù)集X=[x1,x2,…,xn];初始聚類個數(shù)k;

Step 2構(gòu)造自適應相似矩陣S=[sij]n×n;

Step 4求L的前k個最大特征值對應的特征向量ξ1,ξ2,…,ξk，構(gòu)造特征矩陣E=[ξ1,ξ2,…,ξk]n×k，并將矩陣E的行向量單位化得矩陣U；

Step 5將矩陣U的每個行向量對應到原數(shù)據(jù)集的相應點，并利用K-means將其聚類，得到C1,C2,…,Ck.

2.3 自適應層次譜聚類流程

Step 1輸入數(shù)據(jù)集X=[x1,x2,…,xn]；根據(jù)數(shù)據(jù)集規(guī)模設定初始聚類個數(shù)k，以及城市規(guī)模閾值thvalue；

Step 2利用自適應譜聚類算法將數(shù)據(jù)集X進行初始聚類，得到C1,C2,…,Ck；

Step 3若|Ci|>thvalue,i∈[1,2,…k]，其中|Ci|表示類Ci中數(shù)據(jù)點個數(shù)，利用自適應譜聚類算法將Ci聚為兩類得到類Ci1，Ci2；反之，則不再次進行聚類；

Step 4若|Cit|>thvalue,t∈[1,2]，則對Cit重復Step3，直到滿足層次聚類終止條件|Cit|

Step 5通過上述操作，最終形成新類群C1,C2,…,Ck,…,Cs，其中s≤k.

3 改進遺傳優(yōu)化算法

自適應層次譜聚類將大規(guī)模TSP轉(zhuǎn)換為一個GTSP和多個小規(guī)模的TSP，針對該問題的求解提出了一種基于最近鄰、禁忌搜索和傳統(tǒng)遺傳算法的改進遺傳算法.

3.1 算法編碼方式

采用路徑表示法，種群中每個染色體長度為n，染色體中的每個基因由1～n的數(shù)字組成，且為1～n的全排列.

3.2 適應度函數(shù)的選擇

判斷TSP可行解的優(yōu)劣的標準是看其適應度函數(shù)的值，本研究用其目標函數(shù)值的倒數(shù)作為其適應度函數(shù)的值，即

(4)

當Fitness(x)越大，F(xiàn)(x)值越小，對應TSP解越好.

3.3 種群選擇策略、交叉和變異

3.3.1 種群選擇策略

采用精英保留策略，此方法是比較種群中所有個體的適應度值，從中擇優(yōu)選擇一部分個體作為父體，并利用選擇的個體進行交叉和變異操作.

3.3.2 交叉

交叉是父代將自身優(yōu)秀基因遺傳給子代的一種操作.常用交叉算子有順序交叉(Ordered Crossover，OX)、部分映射交叉(Partially Mapped Crossover，PMX)和循環(huán)交叉(Cycle Crossover，CX)[14]；改進算法選擇順序交叉算子，在父代F1中隨機選擇兩個交叉點，將父代F1交叉點之間的基因片段作為子代K相同位置的基因片段，把F2中非F1交叉點之間的基因按順序分別放在子代K的基因片段兩邊的位置，生成新的子代個體.以染色體長度n=10為例，選擇父代F1、F2，若隨機選擇交叉點位置為4、7，則具體交叉操作如下：

3.3.3 變異

變異是保留父代優(yōu)秀基因并保持種群多樣性的一種進化手段.常用變異算子有：移位變異(Displacement Mutation，DM)、交換變異(Exchange Mutation，EM)和逆轉(zhuǎn)變異 (Inversion Mutation，IVM)[14]；改進算法采用交換變異算子進行變異操作，隨機作用在一個父代染色體上，在父代F中隨機選擇四個變異點，按升序排列n1

父代F：6(5 1)7 4 2(10 3 8)9

子代K：6(10 3 8)7 4 2(5 1)9

3.4 改進遺傳算法流程

最近鄰算法生成的路徑的基因總體比較優(yōu)良，而禁忌搜索能夠增強遺傳算法的爬山能力,因此設計了結(jié)合最近鄰和禁忌搜索思想的改進遺傳算法來求解TSP.

改進遺傳算法的流程如下：

Step 1設定種群大小Numpop、設定交叉概率crate、變異概率mrate、選擇率srate和隨機概率rrate，并且設定算法的終止條件r=Iteration，設置進化代數(shù)r=0，禁忌表tabu=[]；

Step 2將每一個個體作為出發(fā)點，由最近鄰算法生成的路徑所構(gòu)成的集合記為P，并計算個體的適應度，從P中隨機選擇Numpop個個體初始化第一代種群S(r)；

Step 3更新禁忌表tabu，禁忌表中存放已經(jīng)搜索過的路徑；

Step 4擇優(yōu)選擇，比較種群S(r)中所有個體的適應度值，從中擇優(yōu)選擇一部分個體作為父體F；

圖1 改進遺傳算法流程圖

Step 7更新父代和子代的并集Srecent(r)；

Step 8隨機生成新的路徑S*(r)，且新的路徑不與禁忌表中路徑重復(引入新個體，增加種群多樣性)；

Step 9r←r+1，在Srecent(r)∪S*(r)擇優(yōu)選擇Numpop個個體作為新的種群S(r)；

Step 10若滿足終止條件，則停止并輸出最短路徑F(xbest)；否則轉(zhuǎn)step3.

4 大規(guī)模TSP的求解

為提高大規(guī)模TSP的求解效率，首先利用自適應層次聚類算法對數(shù)據(jù)集進行聚類，將大規(guī)模TSP轉(zhuǎn)換為對一個類間最短路徑的求解和多個類最短路徑的求解，即GTSP和小規(guī)模的TSP的求解.

4.1 類間最短路徑

類間最短路徑求解即為GTSP的求解，GTSP的一個可行解即為類與類之間的連接順序.

定義1.類Ci與類Cj之間的距離函數(shù):

Dij=D(Ci,Cj)=min{d(x1,y1),d(x1,y2),…,d(x1,yr),

d(x2,y1),d(x2,y2),…,d(x2,yr),…,d(xt,y1),d(xt,y2),…,d(xt,yr)}

(5)

其中，x1,x2,…,xt表示Ci中的數(shù)據(jù)點，y1,y2,…,yr表示Cj中的數(shù)據(jù)點，d(xt,yr)表示兩個數(shù)據(jù)點的歐氏距離.

定義2.兩個類之間歐式距離最小的兩個點即分別為兩個類的邊界點，即：

d(x2,y1),d(x2,y2),…,d(x2,yr),…,d(xt,y1),d(xt,y2),…,d(xt,yr)}

(6)

則

分別為類Ci，Cj的邊界點.

設該GTSP模型集合為G=(V,E)，其中V={1,2,…,s}，1～s表示類標號；E為類間連線的集合，邊(i,j)的權(quán)值為Dij，i,j∈V，在該問題中，Dij取(5)式定義的距離函數(shù)；類間路徑的優(yōu)化是尋找G的最短巡回路線，該巡回路線是類間連線最短回路，且最終在每個類中均可找到兩個類邊界點.經(jīng)過圖V集中每個類頂點恰好兩次(每類有兩個邊界點)，即尋找經(jīng)過V集的不同類邊界點連線的最短巡回線路，圖2為類邊界點連線示意圖.

圖2 類邊界點連線示意圖

則類間最短路徑總長度

FC(Xopt)=min{FC(X)}

(7)

其中FC(x)為類間路徑總長度，且

(8)

其中，i,j∈V,i≠j，而

(9)

4.2 類內(nèi)最短路徑模型建立

類內(nèi)最短路徑求解即是對TSP的求解，本文采用自適應層次聚類算法將數(shù)據(jù)點聚為C1,C2,…,Ck,…,Cs，則類內(nèi)最短路徑的求解即為對s個TSP的求解.以類Ci為例，其最短路徑為：

FCi(Xi)=min{FCi(Xi)}

(10)

(11)

(12)

4.3 大規(guī)模TSP模型建立與求解

結(jié)合類間和類內(nèi)最短路徑的建立過程，可建立大規(guī)模TSP的數(shù)學模型：

(13)

其中s為聚類總數(shù),采用本文提出的改進遺傳算法進行求解.

5 數(shù)值實驗

為了驗證提出的基于自適應層次譜聚類與遺傳優(yōu)化的算法的性能，在仿真環(huán)境Intel(R)Core(TM).i5-2450M CPU、4.00 GB RAM、Window7(32bit)、MATLAB r2013a下，采用本文算法和傳統(tǒng)遺傳優(yōu)化算法，選用TSP標準測試庫TSPLIB[15]中的問題進行數(shù)值實驗.在實驗中，兩算法參數(shù)設置相同，設置如下：種群大小Numpop=120、交叉概率crate=0.9、變異概率mrate=0.2、選擇率srate=0.3、隨機概率rrate=0.3和城市規(guī)模閾值thvalue=200，且設定類內(nèi)進化代數(shù)、類間進化代數(shù)以及遺傳算法進化代數(shù)均為Iteration =300.表1為9個不同TSP實例的遺傳算法和本文算法實驗數(shù)據(jù)，9個TSP實例數(shù)據(jù)規(guī)模分別為150、198、280、417、535、783、1 000、1 379和5 915，數(shù)據(jù)整體呈遞增趨勢.由表1可以看出本文算法的最優(yōu)解均優(yōu)于遺傳算法最優(yōu)解，運行時長更短，且遺傳算法結(jié)果誤差在10%～22%之間，本文算法結(jié)果誤差在3%～11%之間.圖3直觀地展示了兩算法在相同參數(shù)時，9個不同TSP實例的結(jié)果誤差和運行時間的折線圖.由圖3(a)知，本文算法的結(jié)果誤差總體小于遺傳算法誤差，且隨著數(shù)據(jù)規(guī)模的增大，本文算法的結(jié)果優(yōu)勢更明顯；由圖3(b)知，本文算法的運行時間均小于遺傳算法運行時間，當數(shù)據(jù)規(guī)模增大時，兩算法運行時間整體呈上升趨勢，且本文算法在TSP數(shù)據(jù)規(guī)模增大時，用時優(yōu)勢更加明顯.由此可見，本文算法針對大規(guī)模TSP，有效避免收斂速度慢以及早熟現(xiàn)象，較大程度減少了運算時間，提高了計算效率.

表1不同TSP實例遺傳算法與本文算法實驗結(jié)果

Table1DifferentTSPinstancesresultsofgeneticalgorithmandadaptivehierarchicalclusteringgeneticalgorithm

序號TSP問題最優(yōu)解 GA算法 本文算法 解誤差/%運行時間/s解誤差/%運行時間/s1ch1506 5287 20510.377156 874655.302d19815 78018 44116.861 39916 5901275.133a2802 5793 03617.725472 8433810.244fl41711 86113 80216.361 39412 2091102.935ali535202 339230 05813.70845214 9771536.256rat7838 80610 70921.612389 376826.477dsj100018 659 68822 449 66520.311 34620 382 0567219.238nrw137956 63868 32720.648 01362 3371 33210.069rl5915565 530684 58421.0510 472583 7252 3483.22

(a)遺傳算法與本文算法結(jié)果誤差折線圖 (b)遺傳算法與本文算法運行時間折線圖

圖3不同TSP實例遺傳算法與本文算法比較

Fig.3DifferentTSPinstancescomparisonofgeneticalgorithmandadaptivehierarchicalclusteringgeneticalgorithm

6 總 結(jié)

提出了一種基于自適應層次譜聚類與遺傳優(yōu)化的TSP算法，該算法首先構(gòu)建一種自適應相似矩陣，并應用到譜聚類算法中實現(xiàn)城市的初步聚類，當聚類城市規(guī)模超過設定閾值，用上述自適應譜聚類算法進行層次聚類，直到每類城市規(guī)模均小于閾值,從而將大規(guī)模TSP轉(zhuǎn)換為一個GTSP和多個小規(guī)模TSP；其次，利用結(jié)合了最近鄰與禁忌思想的改進遺傳算法求GTSP的最優(yōu)解；最后，用改進遺傳算法求各個小規(guī)模TSP的最優(yōu)解;綜合GTSP和各TSP的最優(yōu)解，即得大規(guī)模旅行商問題的最優(yōu)解.改進遺傳算法采用最近鄰算法選取一系列好的初始種群，加快了種群的搜索速度，同時將禁忌搜索中“禁忌”的思想引入到遺傳算法中，使得種群在進化過程中保證了多樣性，增強了算法的爬山能力，避免了算法出現(xiàn)早熟.選取TSP標準測試庫TSPLIB中不同分布的數(shù)據(jù)集進行數(shù)值實驗，結(jié)果表明該算法達到了預期的結(jié)果，可以將該算法運用到實際的生產(chǎn)生活中.