張玉州，梅海俊，徐廷政

(安慶師范大學計算機與信息學院，安徽安慶246133)

旅行商問題(TSP)是一類應用在組合優(yōu)化和路徑規(guī)劃等領域中著名的NP-hard問題，由美國學者Dantzig于1954年提出[1]。因TSP問題廣泛應用于如物流配送、智能交通控制、電路板鉆孔等方面，所以近年來引發(fā)了眾多學者的關注，并取得一系列的研究成果[2-3]。對于較小規(guī)模的TSP問題，精確算法能快速地取得最優(yōu)解，但難以應對規(guī)模較大、結構較復雜的問題。于是學者提出在不能獲得全局最優(yōu)的情況下，尋找高質(zhì)量的近似解來求解TSP問題的啟發(fā)式算法，包括遺傳算法（GA）[4-5]、粒子群算法、模擬退火算法、禁忌搜索算法、蟻群算法等以及此類算法的混合算法或改進算法[6-7]。在遺傳算法中，通過產(chǎn)生高質(zhì)量的初始解可以提高求解問題的速度，甚至改進最終解的質(zhì)量[8]。因此，本文在遺傳算法的種群初始化上采用生成二種初始解的策略，分別采用最近鄰域（NN）算法[9]以及個體隨機生成策略，既保證種群的多樣性，也提高了初始解的質(zhì)量。遺傳算法雖然有較好的全局搜索能力，但是難以對局部空間進行搜索，導致進化后期搜索效率偏低，解質(zhì)量不高。因此引入局部搜索算法可以較好地解決遺傳算法的早熟收斂問題，從而提高解的質(zhì)量。常用的局部搜索有k-opt（2-opt，3-opt等）以及Lin-Kernighan[10]（LK），旨在對局部進行優(yōu)化，通過施展局部擾動改進一條路徑，其算法優(yōu)點是運算速度快，但缺陷是鄰域的搜索不夠徹底，這導致尋找的解更多是次優(yōu)的。因此本文借鑒限量弧路由問題[11]中的單點插入算子（SI）、交換算子（Swap）兩種局部搜索，并結合2-opt組成一種特有的局部搜索算子集合，以提高對鄰域的搜索能力。

1 TSP問題的描述

TSP問題可定義為給定n個節(jié)點無向完全圖G=(V，E，r)，要求在G中遍歷所有的節(jié)點形成簡單回路C，使C上所有邊的權值和最小，其中V={1，2，…，n}是圖的節(jié)點集，表示被訪問的城市，E是連接V中兩個不同頂點的邊集，r為邊的權值集合。其基于圖論的旅行商問題的數(shù)學模型定義如下：

（1）式為目標函數(shù)，為旅行商所經(jīng)路徑長度的最小化，其中dij表示城市i到城市j的權重；（2）式與（3）式一起表示每個城市有且只有一次被旅行商經(jīng)過；（4）式為旅行商在任何一個城市真子集中不能形成循環(huán)；（5）式表示決策變量的取值，xij=1表示旅行商已經(jīng)遍歷過的城市，xij=0則代表旅行商未曾經(jīng)過該城市。

2 混合遺傳算法

遺傳算法是一種基于生物進化理論發(fā)展起來的廣為應用的、高效的隨機搜索與優(yōu)化方法。通過隨機編碼策略產(chǎn)生初始群體，初始群體里個體定義為種群的染色體，每條染色體代表問題的解，這些染色體通過選擇、交叉、變異算子進行反復迭代，最終得到問題的滿意解。

2.1 編碼

本文在TSP問題中采用順序表示的編碼方法，每一個數(shù)字代表一個城市，遍歷所有的城市產(chǎn)生一條染色體即產(chǎn)生一個解。以8個城市為例，城市編碼是1～8的數(shù)字，若生成的染色體為12345678，則表示從城市1出發(fā)依次經(jīng)過城市2、3、4、5、6、7、8最終回到城市1的一條路徑回路。

2.2 適應度函數(shù)

假設由n個城市構成的染色體為p1|p2|...|pn-1|pn，則此個體的適應度函數(shù)值：

其中，d(pi,pi+1)表示路徑中相鄰的城市i到城市i+1的距離。此適應度函數(shù)f表示旅行商遍歷所有城市并回到起點城市所產(chǎn)生路徑距離的倒數(shù)。適應度函數(shù)越大代表染色體品質(zhì)越好，即總路徑長度越短；反之則表示染色體品質(zhì)越差，即總路徑長度越長。

2.3 局部搜索算子

在算法選擇策略期間，最優(yōu)的染色體不進行交叉，在迭代次數(shù)有限的情況下，往往可以得到比較優(yōu)秀的結果，但是也容易造成種群泛濫，導致算法早熟收斂。而當遺傳算法采取合適的局部優(yōu)化方法時，通過施展局部擾動改進一條路徑，提升對鄰域的搜索能力，可以使算法的性能得到較大幅度的提升。本文采用3種局部搜索策略形成一種特有的局部搜索算子集合，其中SI，Swap能夠精細地對個體鄰域進行搜索，并且利用2-opt的擾動過程增加搜索維度，這樣不僅克服了算法對單一鄰域的過分依賴，也擴大了局部搜索范圍。具體的局部搜索算子如下：

（1）SI：在一條染色體中，將每個基因分別插入到所有路徑的各個位置，尋找最優(yōu)插入位置，獲取鄰域解，比較其與原解的適應度大小。若鄰域解的適應度大于原解的適應度，則前者替換后者。

（2）Swap：在一條染色體中，將每個基因分別與所有路徑中各個位置的基因進行互換，尋找最優(yōu)交換位置，得到鄰域解，對其與原解進行適應度比較，并進行與上述（1）相同方式的替換。

（3）2-opt：在一條染色體中，隨機在此條染色體中選取一段區(qū)間，將該區(qū)間內(nèi)所有的基因序列進行翻轉(zhuǎn)，區(qū)間外的基因不做改動，直接復制到子代染色體中，倒置區(qū)間中的基因序列也復制到代染色體中，形成一鄰域解，并按上述規(guī)則進行個體替換。

2.4 初始化種群

遺傳算法中初始化種群的質(zhì)量影響算法的全局性能，基本遺傳算法隨機生成的初始種群中染色體適應度低且算法效率低下。本文算法的種群初始化采用兩種生成策略：最近鄰域法、隨機生成法。最近鄰域法過程如下：

Step1：隨機選擇一個城市為起點城市，在剩余未旅行的城市中選擇距離最近的城市作為第二個城市；

Step2：比較剩余未旅行的城市到當前城市的距離，選擇距離最近的城市作為下一個城市；

Step3：重復Step2直到旅行完所有城市再回到起點城市，構成一條完整的路徑，得到一個解。

因為最近鄰域算法存在每一步?jīng)Q策的短視行為，所以將導致在構造路徑的后階段可能需要連接距離較遠的城市才能構造成完整路徑，這容易造成個體生成同質(zhì)化的缺陷。鑒于此，本文采用隨機生成法來提高初始化種群的多樣性。最近鄰域法相較隨機生成法，產(chǎn)生的種群個體在初始時就保持較高的適應度，提高了算法的收斂速度。

2.5 選擇算子

選擇算子使用輪盤賭選擇法，個體選擇的概率與適應度大小成正比。假設種群規(guī)模為M，則個體被選擇的概率為，其中fi為第i個個體的適應度，pri為第i個個體被選擇的概率，得出選擇概率后，于[0,1]區(qū)間產(chǎn)生一個均勻分布的隨機數(shù)來選擇個體進行下一步操作。為保證算法的收斂性，算法采用精英保留策略。

2.6 交叉算子

交叉算子采用順序交差法(OX)，從父代A隨機選一個編碼子串，放到子代A′的對應位置；子代A′空余的位置從父代B中按照B中的順序選取，但不能重復已經(jīng)選取的編碼。同理得到子代B′，由于很難直接找到適應問題的交叉概率Pc，需要通過經(jīng)驗值和反復實驗來確定。交叉算子過程如下：

父代 A：875|193|0624，父代 B：583|470|9216經(jīng)過交叉后得到：

子代 A′：584|193|7026，子代 B′：851|470|9362。

2.7 變異算子

變異算子主要為了維護種群的多樣性，防止算法陷入局部最優(yōu)，并對當前解的鄰域作一定程度的搜索，本文采用多次對換變異算子。當變異概率小于Pm時，產(chǎn)生不大于城市數(shù)目的隨機數(shù)r，染色體按照變異策略隨機產(chǎn)生2個位置，進行r次2個位置間基因的交換。為了說明多次對換變異算子過程，假設r=1，即只進行一次對換變異，過程如下：父代（123456789）經(jīng)變異后得到子代（127456389），變異概率Pm一般取值較小。

2.8 HGA的步驟描述

HGA具體步驟描述如下。

Step1采用2.4節(jié)所述方法生成初始種群pop，規(guī)模定義為scale，設置染色體交叉概率Pc、變異概率Pm和最大進化代數(shù)Tmax，評價種群各個體的適應度；

Step2令當前代數(shù)t=1；

Step3挑選當前代適應度最高的個體直接賦予子代，并依據(jù)2.5節(jié)的輪盤賭選擇策略挑選scale-1個子代個體，得到過渡種群pop′；

Step4從種群pop′挑選適應度最高的個體Nmax，將其加入到新種群pop*；

Step5令個體生成次數(shù)k=1;

Step6從pop′選取個體：N1，N2，按照概率Pc進行交叉生成子個體M1，M2；

Step7對個體M1，M2按照變異概率Pm進行變異操作生成子個體K1和K2；

Step8對個體K1和K2按照2.3節(jié)所述SI、Swap、2-opt 3種局部搜索算子分別進行局部搜索操作，從而得到優(yōu)秀鄰域解，并插入到pop*中；

Step9 k=k+1；

Step10若k＜=scale/2-1，則轉(zhuǎn)至Step6繼續(xù)產(chǎn)生新的個體。若pop′尚存?zhèn)€體Nlast，則對其進行變異操作，并插入到pop*；

Step11對pop*所有個體進行局部搜索操作；

Step12以pop*更新種群pop；

Step13 t=t+1；

Step14若t＜=Tmax，則轉(zhuǎn)Step3繼續(xù)執(zhí)行，否則結束算法。

3 實驗結果及分析

本文采用Java語言對所提HGA進行實現(xiàn)，對TSPLIB中的測試樣例進行計算，并對比GA、NN、雙向擴展差額算法（TDMDA）[12]、分層融合算法（HFA）[13]以及HGA共5種算法的求解結果。其中GA是基本遺傳算法；NN為典型的構建型算法；TDMDA是基于NN的改進的算法，主要區(qū)別為每次選擇延伸方向的規(guī)則不同；HFA通過建立分層模型規(guī)避算法路徑中不合理的邊，從而得到較好的實驗結果。實驗環(huán)境：windows7系統(tǒng)，intel（R）Core（TM），i3-4160 CPU@3.60 GHz。

3.1 參數(shù)設置及測試樣例

種群規(guī)模N=100，最大進化代數(shù)T=200，交叉概率Pc=0.5，變異概率Pm=0.085。為了驗證算法的有效性，選取了TSPLIB樣本案例庫中規(guī)模有代表性的20個算例為測試數(shù)據(jù)，并且每個測試樣例獨立運行30次。

3.2 實驗結果對比

（1）單個算例Att48

HGA對測試算例Att48的30次運行結果中，最優(yōu)的路徑長度為10 628，最差的路徑長度為10 812，平均路徑長度為10 678。算例Att48運行結果的最優(yōu)路徑示意圖如圖1所示。其余4種算法均未能達到最優(yōu)路徑，其中HFA相比能求得較好的結果，得出的最優(yōu)結果為10 753。

圖1 HGA算法得到的Att48最優(yōu)路徑軌跡圖

（2）TSPLIB測試樣例集運行結果

為了更好地說明算法的有效性，本文對所選取的20個測試樣例分別采用5種算法求解，其結果如表1所示。

表1 5種算法求解20個TSP測試算例結果對比

表1中，算例名稱為TSP的實例名稱及其測試算例包含的城市數(shù)目；平均解和最優(yōu)解分別表示算法的30次運行結果的平均質(zhì)量和最優(yōu)解質(zhì)量，并且均用百分號表示，計算方式：（求解得路徑長度-最優(yōu)解路徑長度）/最優(yōu)解路徑長度×100%，解質(zhì)量的數(shù)值越低代表算法越優(yōu)秀。5種算法GA、NN、TDMDA、HFA以及HGA算法都因為生成初始解解集的不同，使得每次實驗得出的最優(yōu)解都不相同，故而都為不確定性的算法，需要進行重復實驗得出結果。

最優(yōu)解方面。由表1可知在求得最優(yōu)路徑方面，HGA有明顯的提升，城市數(shù)目不大于100的測試算例共有12個，其中有9個均求出最優(yōu)解路徑，其余3個最優(yōu)解質(zhì)量均不超過1%，說明本文算法在求得城市數(shù)目不大于100的TSP算例上，可以取得較好的結果甚至達到最優(yōu)解。在剩下8個測試算例中，HGA算法有2個測試算例KroB150和KroA200的最優(yōu)解質(zhì)量略低于HFA算法，遠遠高于其余的3個算法。并且從表1中可以看出HGA算法最優(yōu)解質(zhì)量的平均值為最優(yōu)，達到1.11%。5種算法的最優(yōu)解質(zhì)量對比折線

圖2 5種算法最優(yōu)解質(zhì)量對比

通過實驗仿真發(fā)現(xiàn)混合遺傳算法在求解小規(guī)模TSP問題上的尋優(yōu)能力具有較為明顯的提高，比較5種算法的解質(zhì)量，HGA算法在大部分TSP算例上優(yōu)于其他4種算法，并且通過圖2，圖3可以直觀地看出HGA算法在解質(zhì)量方面一直趨于穩(wěn)定狀態(tài)，證明了本文算法的魯棒性和有效性。

4 結論

局部搜索是求解組合優(yōu)化問題的重要組成部分，當遺傳算法引用合適的局部優(yōu)化方法時，可以使算法的性能得到較大幅度的提升。本文基于SI、Swap以及2-opt 3種鄰域搜索和遺傳算法中2種初始解生成策略，提出一種混合遺傳算法HGA。通過對TSPLIB中的20個測試樣例進行計算，對比GA、NN、TDMDA、HFA以及HGA共5種算法的求解結果，驗證了算法的有效性和穩(wěn)定性。圖如圖2所示。

平均解質(zhì)量方面。TSP為最小化問題，解的數(shù)值越低代表對應算法越優(yōu)秀。GA的平均解質(zhì)量數(shù)值最高，為61.10%，代表其算法性能最差；NN算法和TDMAA算法的平均解質(zhì)量相近，分別為26.43%和27.72%；HFA算法的平均解質(zhì)量提升明顯，達到7.45%；本文提出的HGA算法相較其他算法有較為明顯的優(yōu)勢，平均解質(zhì)量為4.6%，說明本文算法在20個算例上，每次求出的結果與最優(yōu)解路徑相近，證明算法有較好魯棒性。5種算法的平均解質(zhì)量對比折線圖如圖3所示。

圖3 5種算法平均解質(zhì)量對比