一種求解TSP問(wèn)題的混合遺傳算法

張玉州，梅海俊，徐廷政

(安慶師范大學(xué)計(jì)算機(jī)與信息學(xué)院，安徽安慶246133)

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

1 TSP問(wèn)題的描述

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

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

2 混合遺傳算法

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

2.1 編碼

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

2.2 適應(yīng)度函數(shù)

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

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

2.3 局部搜索算子

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

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

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

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

2.4 初始化種群

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

Step1：隨機(jī)選擇一個(gè)城市為起點(diǎn)城市，在剩余未旅行的城市中選擇距離最近的城市作為第二個(gè)城市；

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

Step3：重復(fù)Step2直到旅行完所有城市再回到起點(diǎn)城市，構(gòu)成一條完整的路徑，得到一個(gè)解。

因?yàn)樽罱徲蛩惴ù嬖诿恳徊經(jīng)Q策的短視行為，所以將導(dǎo)致在構(gòu)造路徑的后階段可能需要連接距離較遠(yuǎn)的城市才能構(gòu)造成完整路徑，這容易造成個(gè)體生成同質(zhì)化的缺陷。鑒于此，本文采用隨機(jī)生成法來(lái)提高初始化種群的多樣性。最近鄰域法相較隨機(jī)生成法，產(chǎn)生的種群個(gè)體在初始時(shí)就保持較高的適應(yīng)度，提高了算法的收斂速度。

2.5 選擇算子

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

2.6 交叉算子

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

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

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

2.7 變異算子

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

2.8 HGA的步驟描述

HGA具體步驟描述如下。

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

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

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

Step4從種群pop′挑選適應(yīng)度最高的個(gè)體Nmax，將其加入到新種群pop*；

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

Step6從pop′選取個(gè)體：N1，N2，按照概率Pc進(jìn)行交叉生成子個(gè)體M1，M2；

Step7對(duì)個(gè)體M1，M2按照變異概率Pm進(jìn)行變異操作生成子個(gè)體K1和K2；

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

Step9 k=k+1；

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

Step11對(duì)pop*所有個(gè)體進(jìn)行局部搜索操作；

Step12以pop*更新種群pop；

Step13 t=t+1；

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

3 實(shí)驗(yàn)結(jié)果及分析

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

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

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

3.2 實(shí)驗(yàn)結(jié)果對(duì)比

（1）單個(gè)算例Att48

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

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

（2）TSPLIB測(cè)試樣例集運(yùn)行結(jié)果

為了更好地說(shuō)明算法的有效性，本文對(duì)所選取的20個(gè)測(cè)試樣例分別采用5種算法求解，其結(jié)果如表1所示。

表1 5種算法求解20個(gè)TSP測(cè)試算例結(jié)果對(duì)比

表1中，算例名稱為T(mén)SP的實(shí)例名稱及其測(cè)試算例包含的城市數(shù)目；平均解和最優(yōu)解分別表示算法的30次運(yùn)行結(jié)果的平均質(zhì)量和最優(yōu)解質(zhì)量，并且均用百分號(hào)表示，計(jì)算方式：（求解得路徑長(zhǎng)度-最優(yōu)解路徑長(zhǎng)度）/最優(yōu)解路徑長(zhǎng)度×100%，解質(zhì)量的數(shù)值越低代表算法越優(yōu)秀。5種算法GA、NN、TDMDA、HFA以及HGA算法都因?yàn)樯沙跏冀饨饧牟煌?，使得每次?shí)驗(yàn)得出的最優(yōu)解都不相同，故而都為不確定性的算法，需要進(jìn)行重復(fù)實(shí)驗(yàn)得出結(jié)果。

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

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

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

4 結(jié)論

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

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

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