基于改進遺傳算法的大規(guī)模TSP 問題求解方案

雷玉梅

(阜新高等專科學校，遼寧 阜新 123000)

0 引言

TSP(Traveling Salesman Problem)問題，也稱旅行商問題或貨郎擔問題，是一個典型的NP(Non-deterministic Polynomial)完全問題。它不僅描述了商人從一個城市出發(fā)，經(jīng)過其他多個城市，且只經(jīng)過一次之后，又回到出發(fā)城市的問題，也是數(shù)學領域一個復雜的組合優(yōu)化問題，更是諸多領域內(nèi)許多復雜問題的概括的形式化描述。凡是可以抽象地表示為遍歷且只遍歷所有結(jié)點一次，最終回到初始結(jié)點，求代價最小的回路問題，都可以仿照求解TSP 問題的方法進行求解。因此，TSP 問題的解決方案在計算機理論和實際應用中得到廣泛的關注。

目前解決TSP 問題的方法大致可以分為2 大類［1］，一類是擁有較好的數(shù)理邏輯和理論基礎的精確的計算方法(Exact Algorithm)，能夠找到問題的最優(yōu)解，另一類是近似的計算方法(Approximation Algorithm)，沒有嚴密的數(shù)理邏輯，但通常能夠更為高效地求得可接受的問題的解，因此在實際中應用更為廣泛，遺傳算法就是一種典型的近似計算方法。

遺傳算法是根據(jù)優(yōu)勝劣汰的生物進化理論設計出來的一種優(yōu)化的搜索算法，主要通過遺傳染色體信息，選擇對“環(huán)境”的“適應能力”高于父代的子代，直到適應能力滿足一定的要求。高經(jīng)緯等人在文獻［2］中證明了使用遺傳算法求解TSP 問題時具有結(jié)果準確、收斂速度快的特點。文獻［3-9］從不同的方面對遺傳算法進行改進，提升了其解決TSP 問題的能力。然而，對于大規(guī)模的TSP 問題，始終沒有較好的解決辦法，也吸引了越來越多的研究學者的關注。

本文結(jié)合啟發(fā)式的思想和改進的遺傳算法，提出了新的解決大規(guī)模TSP 問題的HG 方法，采用分而治之和啟發(fā)式的初始化方法，利用改進的遺傳算子，提高了遺傳算法的性能，多個數(shù)據(jù)集上的實驗結(jié)果證明了HG 算法的有效性。

1 相關概念

1.1 TSP 問題形式化描述

給定N 個城市的集合，城市用ci，i∈{0，1，...，N-1］表示，R=(c0，c1，...，cN-1)表示經(jīng)過所有N個城市的一條路線，當路線R 滿足公式(1)取得最小值時，R 即為TSP 問題的最優(yōu)解:

其中，d(ci，ci+1)表示城市ci與城市ci+1之間的距離，f(R)表示路線R 的距離。

解決TSP 問題的目標就是找到一條路線R*，使得f(R*)取得最小值。對于N 個城市的TSP 問題，采用全局搜索的方式，可行的組合有(N-1)!種，當N 變得很大時，全局搜索的方法已經(jīng)不可能解決TSP 問題。

1.2 遺傳算法

遺傳算法首先對問題中的參數(shù)集進行編碼，形成初始種群，計算適應度，然后通過染色體信息的代代相傳(利用選擇、交叉和變異算子不停地進行算法迭代)搜索具有最高適應度的個體，算法流程可用圖1 表示。

圖1 遺傳算法流程圖

2 HG 算法

2.1 聚類

本文沿用分而治之的思想解決大規(guī)模的TSP 問題，根據(jù)坐標位置進行聚類操作，把相對位置較近的城市劃分到一個類簇(聚類的結(jié)果)中。城市之間的“相似性”采用歐式距離描述，如公式(2)所示:

其中，p 表示結(jié)點的屬性的數(shù)量，這里是2(城市的經(jīng)度和緯度)，wij表示結(jié)點ci與cj的相似性。在TSP問題中，結(jié)點之間的歐式距離表示城市之間的位置距離，因此聚類操作會把距離較近的城市劃分到同一個類簇，符合進行聚類操作的初衷。

經(jīng)過聚類操作，把一個大規(guī)模的TSP 問題，劃分為多個類簇中的子TSP 問題，然后采用本文改進的遺傳算法求解各個子TSP 問題。

2.2 編碼與初始化

本文采用序號編碼的方式，把每個類簇中的城市編號為1，2，3，…，ni，ni表示第i 個類簇的城市數(shù)量。一條路徑編碼為一條染色體，用1～ni的任一排列組合表示。

初始化過程用來構(gòu)造初始的種群(染色體的集合)，初始化結(jié)果的好壞，一定程度上決定了遺傳算法收斂所用的時間。傳統(tǒng)的遺傳算法中，一般采用隨機的方式產(chǎn)生初始化種群，但是這種方法的不穩(wěn)定性極高，遺傳算法的收斂可能需要很長時間。Osaba 等人在文獻［9］中指出，使用啟發(fā)式的初始化函數(shù)能夠有效地提升遺傳算法的性能。本文就采用了NN［10］的啟發(fā)式初始化函數(shù)，具體地，在類簇i 中隨機選擇一個起始城市c0∈{1，2，...，ni}，然后根據(jù)公式(3)依次選擇剩下的ni-1 個城市，組成初始路線:

HG 的初始化方法，使最初的路線擁有較高的適應度，有利于從根本上提升算法的收斂速度以及優(yōu)化收斂結(jié)果。

2.3 適應度函數(shù)

適應度是用來評價個體對“環(huán)境”的適應能力，適應度越高，說明適應能力越強。在TSP 問題中，適應度可以用路線的距離來表示，路線的距離越短，說明路線越優(yōu)。為方便后續(xù)的遺傳算子的操作，HG 方法采用公式(4)所示的適應度函數(shù):

其中，MAX 表示無窮大，f(Ri)表示種群中個體i 的適應度，其值越大，表示個體的適應能力越強。

2.4 交叉算子

交叉是指父代2 個個體的部分染色體信息進行互換，重組為新的個體的操作，在生物進化的過程中發(fā)揮著核心作用。遺傳算法中的交叉算子同樣發(fā)揮著重要作用，但不是任意2 個父代的個體都會進行交叉操作，交叉行為的發(fā)生有一定的概率，發(fā)生交叉行為的個體占種群個體總數(shù)的比例稱為交叉率。由于HG 方法采用的是序號編碼，因此采用單親遺傳的方法，在單條染色體內(nèi)進行單點交叉操作。對滿足交叉率的染色體，利用公式(5)選擇交叉點:

其中，tik表示染色體i 的第k 個交叉點，S 表示交叉點的總數(shù)。由公式(4)可知，根據(jù)路線Ri中連續(xù)2 個城市之間的距離最遠的S 個位置，依次選擇S 個交叉點，把染色體i 切成S +1 個片段，然后將這S +1 個片段重新組合成完整的一條染色體。

HG 的交叉算子消除了個體中對適應度影響最大的染色體信息(切斷路線中距離最遠的連續(xù)的2 個城市)，有利于促進算法的收斂進程，同時能夠增加種群的多樣性，有利于避免過早收斂的現(xiàn)象。

2.5 變異算子

變異算子是指對染色體上某位置的信息進行變動，比如，交換路線上任意2 個不同城市的位置。跟交叉操作一樣，變異操作同樣有變異率的約束，是指發(fā)生變異的個體占種群中個體總數(shù)的比例。傳統(tǒng)的遺傳算法通常為變異率選擇固定的數(shù)值，而HG 算法利用公式(6)定義動態(tài)的變異率:

其中，mutation 表示變異率，分子表示種群中染色體信息相同的個體數(shù)目的最大值，分母表示種群的數(shù)量。比如，隨著算法的迭代，在某一世代的種群中染色體A 出現(xiàn)了2 次，染色體B 出現(xiàn)了3 次，且A≠B，且沒有其他染色體對應多個個體，則公式(6)的分子值為3。

在滿足變異率的前提下，隨機交換染色體2 個位置的信息，而且在算法迭代初期，只針對染色體的前段信息進行變異操作，以擴大解空間的搜索范圍，到算法迭代后期，則只變異染色體的后段信息，否則可能會影響算法的收斂。

HG 算法的動態(tài)變異算子，保證了種群的多樣性，有利于避免過早收斂的問題，同時還保證了較大的解空間的搜索范圍和較好的收斂結(jié)果。

2.6 選擇算子

選擇算子用來把種群中的優(yōu)良個體直接選入下一代。輪盤賭方法是一種簡單又常用的選擇方法，每個個體對應一個選擇概率，適應能力強的個體，選擇概率大，適應能力低的，選擇概率小，選擇概率通過公式(7)計算:

其中pik表示種群i 中個體k 的選擇概率。

由公式(7)可知，種群中所有個體的選擇概率之和為1，因此可以通過累加的方式為每個個體確定一個概率區(qū)間。比如個體1 的選擇概率為0.1，個體2的選擇概率為0.2，則個體1 的概率區(qū)間為0～0.1，而個體2 為0.1～0.3。然后根據(jù)0～1 區(qū)間內(nèi)的一個隨機數(shù)，確定被選中的個體。

2.7 全局TSP 問題的解

在求得各子TSP 問題的解之后，需要將它們集成為全局的TSP 問題的解，即把各個類簇連接起來。HG 方法仿照單鏈接的聚類方法，在2 個待連接的類簇之間應用2 次單鏈接方法，把2 個類簇連接起來，但要求2 次單鏈接方法選中的4 個點必須是2 對點，即同一個類簇中的2 個點是直接相連的。單鏈接聚類是指根據(jù)2 個類簇對象之間的最短距離連接類簇的方法，具體可由圖2 表示。

圖2 聚類連接

圖2 中，中間的虛線分割的上下2 個類簇就是待連接的類簇。2 次單鏈接方法，分別可以找到結(jié)點1和3 之間的虛線，以及結(jié)點2 和4 之間的虛線，然后把結(jié)點1 和2 之間以及結(jié)點3 和4 之間的黑色加粗連線剪斷，把結(jié)點1 和3 以及結(jié)點2 和4 連接起來，就成功地把2 個類簇連在了一起。實際操作過程中，是先找到2 個類簇距離最近的4 個點，如圖2 中的1，2，3，4，然后比較1-3，2-4 的距離之和與1-4，2-3 的距離之和，選擇較短的一組進行連接。這樣就把2 個類簇連接成了一次類簇，再繼續(xù)與其他的類簇連接，就可以得到全局的TSP 問題的解。

2.8 HG 算法流程

根據(jù)前文的闡述，可用表1 描述HG 算法的流程。

表1 HG 算法流程

3 實 驗

為了驗證HG 算法解決大規(guī)模的TSP 問題的性能，本節(jié)選用標準問題庫 TSPLIB 的 A280 和NRW1379 兩個數(shù)據(jù)集進行實驗，采用標準的遺傳算法(SGA)以及Le 等人［10］和金聰［11］提到的利用啟發(fā)式思想改進的遺傳算法作為對比算法。文獻［10］主要將NN 的啟發(fā)式思想用于初始路徑的選取(HNN)，而文獻［11］則選用梯度尋優(yōu)技術(shù)對變異算子進行了改進(H-GO)。

實驗中選用k-means 的聚類方法［12］，A280 數(shù)據(jù)集聚成10 個類簇，NRW1379 數(shù)據(jù)集聚成25 個類簇。實驗均在Intel i5 處理器、2G 的PC 機上運行。

方便自學：教師應根據(jù)學員的現(xiàn)有水平從互聯(lián)網(wǎng)上篩選適宜的視頻資料幫助學員課后復習消化，如“交流接觸器工作原理及內(nèi)部結(jié)構(gòu)”視頻資料。

圖3 和圖4 分別展示了HG 和H-NN 算法在2 個數(shù)據(jù)集上隨著迭代次數(shù)的增加，所計算出來的全局聯(lián)通路徑的長度的變化，而圖5 和圖6 則是與SGA 算法以及H-GO 算法的對比結(jié)果。

圖3 路徑長度隨迭代次數(shù)的變化(A280)

圖4 路徑長度隨迭代次數(shù)的變化(NRW1379)

圖5 HG VS(SGA ＆＆ H-GO)(A280)

圖6 HG VS (SGA ＆＆ H-GO)(NRW1379)

從圖3～圖6 可以看出，隨著迭代次數(shù)的增多，HG 算法計算得到的路徑長度逐漸減小。在A280 數(shù)據(jù)集上，HG 算法經(jīng)過3 000 次迭代之后，路徑長度已減小到3 200 左右，而SGA 算法仍徘徊在13 000 附近，大概是HG 計算結(jié)果的4 倍。H-NN 與HG 算法的效果比較接近，但H-GO 算法由于采用了梯度優(yōu)化的方法，在算法迭代后期，收斂速度較慢。在NRW1379 數(shù)據(jù)集上，HG 算法經(jīng)過5 000 次迭代，路徑長度已減小到68 000 左右，而SGA 算法的計算結(jié)果卻仍相當于HG 的7 倍之多。H-NN 算法由于并沒有考慮樣本的多樣性，出現(xiàn)了過早收斂的趨勢，而HGO 算法同樣存在后期收斂速度減緩的問題。此外，SGA 算法在A280 數(shù)據(jù)集上表現(xiàn)出了不穩(wěn)定，距離長度曲線有回升的情況，這是由于算法運行一段時間后，路徑的前段序列已接近最優(yōu)，而在變異算子隨機交換了2 個結(jié)點之間的順序之后，使得原本較優(yōu)的路徑變差所導致的，采用動態(tài)變異算子的HG 算法就沒有出現(xiàn)這種情況。

迭代次數(shù)的增加，必然伴隨著運行時間的增加，圖7和圖8 展示了算法計算結(jié)果隨著運行時間的變化。

圖7 路徑長度隨運行時間的變化(A280)

圖8 路徑長度隨運行時間的變化(NRW1379)

從圖7 和圖8 中可以看出，隨著運行時間的增加，HG 算法和SGA 算法計算的路徑長度大體都呈下降趨勢，但兩者之間仍存在很大差距。例如在NRW1379 數(shù)據(jù)集上，當HG 算法的計算結(jié)果達到70 000 左右時，SGA 的計算結(jié)果還停留在250 000 附近，并且有出現(xiàn)過早收斂的跡象，而HG 算法則始終呈現(xiàn)較好的下降趨勢。在圖7 和圖8 中，H-NN 算法過早收斂的問題和H-GO 后期收斂速度緩慢的問題表現(xiàn)的更加明顯。

此外，為了直觀、明顯地觀察HG 算法分而治之的思想，以及各個類簇連接的效果，圖9 展示了NRW1379 數(shù)據(jù)集上HG 算法在迭代5 000 次之后的路徑(并沒有把各個聚類連接)，而圖10 則展示了A280 數(shù)據(jù)集上類簇連接前后的路徑結(jié)果圖，同樣證明了HG 算法的有效性。

圖9 NRW1379 數(shù)據(jù)集路徑

圖10 A280 數(shù)據(jù)集路徑

從圖9 和圖10 中可以分析出，最終算法的計算結(jié)果，受聚類結(jié)果的影響很大。表2 給出了2 個數(shù)據(jù)集上進行20 次實驗所統(tǒng)計的HG 方法計算的全局路徑長度的均值和均方差。

表2 HG 全局路徑長度均值與均方差

其中，MSE 表示均方差，AVG 表示均值，N 表示進行實驗的次數(shù)，此處取20。

實驗過程中可能出現(xiàn)多次實驗的聚類結(jié)果不盡相同的情況。因此，如何選擇聚類算法，聚類的數(shù)量如何確定，以及是否存在最適合TSP 問題的聚類方法，這些都將成為筆者后續(xù)研究的課題。

4 結(jié)束語

大規(guī)模的TSP 問題不僅描述了旅行商人的路徑選擇問題，同時也是計算機、物流等諸多領域的復雜非線性問題的抽象模型。本文提出的HG 算法，化繁為簡，把大規(guī)模的TSP 問題分割成多個子TSP 問題，并利用改進的遺傳算法對各子問題求解，高效地解決了大規(guī)模的TSP 問題，同時有效地解決了過早收斂的問題。在標準問題庫TSPLIB 的多個數(shù)據(jù)集上的實驗結(jié)果，驗證了HG 算法的有效性。

［1］Li Ying，Ma Kai，Zhang J iong.An efficient multicore based parallel computing approach for TSP problems［C］// 2013 the Ninth International Conference on Semantics，Knowledge and Grids (SKG).2013:98-104.

［2］高經(jīng)緯，張煦，李峰，等.求解TSP 問題的遺傳算法實現(xiàn)［J］.計算機時代，2004(2):19-21.

［3］張煜東，吳樂南，韋耿.智能算法求解TSP 問題的比較［J］.計算機工程與應用，2009，45(11):11-15.

［4］Yu Yingying，Chen Yan，Li Taoying.A new design of genetic algorithm for solving TSP［C］// Proceedings of the Fourth International Joint Conference on Computational Sciences and Optimization.2011:309-313.

［5］王斌，李元香，王治.一種求解TSP 問題的單親遺傳算法［J］.計算機科學，2003，30(5):73-75.

［6］李茂軍，朱陶業(yè)，童調(diào)生.單親遺傳算法與傳統(tǒng)遺傳算法的比較研究［J］.系統(tǒng)工程，2001，19(1):61-65.

［7］Chen Junhong，Hu Junxiang，Zhen Xunyan.Application of improved partheno-genetic algorithm in distribution network switch optimal planning［C］// 2010 International Conference on Electrical and Control Engineering(ICECE).2010:467-470.

［8］Yang Jinqiu，Yang Jiangang，Chen Genlang.Solving largescale TSP using adaptive clustering method［C］// The Second International Symposium on Computional Intelligence and Design.2009:49-51.

［9］Osaba E，Carballedo R，Diaz F，et al.On the influence of using initialization functions on genetic algorithms solving combinatorial optimization problems:A first study on the TSP［C］// 2014 IEEE Conference on Evolving and Adaptive Intelligent Systems (EAIS).2014:1-6.

［10］Le Ny J，F(xiàn)eron E，F(xiàn)razzoli E.On the Dubins traveling salesman problem［J］.IEEE Transactions on Automatic Control，2012，57(1):265-270.

［11］金聰.啟發(fā)式遺傳算法及其應用［J］.數(shù)值計算與計算機應用，2003，24(1):30-35.

［12］戴文華，焦翠珍，何婷婷.基于并行遺傳算法的K-means聚類研究［J］.計算機科學，2008，36(6):171-174.

［13］戚玉濤，劉芳，焦李成.求解大規(guī)模TSP 問題的自適應規(guī)約免疫算法［J］.軟件學報，2008，19(6):1265-1273.

［14］趙連朋，金喜子，王娜，等.求解超大規(guī)模旅行商問題的縱深遺傳算法［J］.計算機工程與應用，2009，45(4):56-58.

［15］左國才，楊金民.K-means 算法在電信CRM 客戶分類中的應用［J］.計算機系統(tǒng)應用，2010，19(2):155-159.

［16］溫光輝，王明旭，郭嗣琮.一種求解TSP 問題的新型遺傳編碼方案［J］.科學技術(shù)與工程，2006，6(2):206-208

［17］滕奇志，唐棠，何小海，等.基于交換-單親遺傳算法的砂巖三位顯微圖像重建［J］.數(shù)據(jù)采集與處理，2010，25(3):364-368.