宗德才，王康康，丁 勇

(1.常熟理工學(xué)院計算機(jī)科學(xué)與工程學(xué)院，江蘇 常熟 215500;2.江蘇科技大學(xué)數(shù)理學(xué)院，江蘇 鎮(zhèn)江 212003;3.南京理工大學(xué)泰州科技學(xué)院計算機(jī)科學(xué)與技術(shù)系，江蘇 泰州 225300)

0 引言

旅行商問題(Traveling Salesman Problem，TSP)是一個典型的NP難的組合優(yōu)化問題。該問題可描述為[1]:給定n個城市和兩兩城市之間的距離，要求確定一條經(jīng)過各城市當(dāng)且僅當(dāng)一次的最短巡回路徑。

假設(shè)有n個城市，用1～n對城市進(jìn)行編號，1表示城市1，2表示城市2，…，n表示城市n。Θ是所有1，2，…，n 排列的集合，di，j是城市 i到城市 j的距離，s=(a1，a2，…，an)是 1，2，…，n 的一個排列，(a1，a2，…，an)表示訪問的第1個城市是城市a1，第2個城市是城市a2，…，訪問的最后一個城市是an，最后再回到第1個城市a1的一條回路。當(dāng)di，j=dj，i時，稱為對稱 TSP 問題;當(dāng) di，j≠dj，i時，稱為不對稱TSP問題。本文中提到的TSP問題均是指對稱TSP問題。

TSP問題可以用數(shù)學(xué)表達(dá)式表示為:

近年來，為解決TSP問題出現(xiàn)了許多隨機(jī)優(yōu)化算法或局部搜索算法，比較著名的有:遺傳算法、粒子群算法、模擬退火算法、禁忌搜索算法、2-opt算法、3-opt算法、Lin-Kernighan(LK)算法等。這些算法能夠在較短時間內(nèi)獲得近似解。嵌套分區(qū)算法(Nested Partitions Method，NPM)[2]是由 Shi Leyuan 等提出的一種能夠高效求解大規(guī)模問題的優(yōu)化方法，該算法提供了一個框架，能夠?qū)⑷炙阉髋c局部搜索相融合，具有易實現(xiàn)、并行性、全局性等優(yōu)點。文獻(xiàn)[3]將嵌套分區(qū)算法應(yīng)用于銀行分支機(jī)構(gòu)選址問題，文獻(xiàn)[4]將嵌套分區(qū)算法應(yīng)用于大規(guī)模車間作業(yè)調(diào)度問題，文獻(xiàn)[5]將嵌套分區(qū)算法應(yīng)用于產(chǎn)品裝配子序列合并問題，都取得了較好的效果。目前國內(nèi)對于嵌套分區(qū)算法的研究還比較少。文獻(xiàn)[6]將嵌套分區(qū)算法應(yīng)用于求解旅行商問題，通過在抽樣算子中引入2-opt局部搜索算法，對抽樣得到的初始回路進(jìn)行2-opt優(yōu)化，能夠顯著提高解的質(zhì)量和算法的收斂速度，但是能夠搜索到最優(yōu)解的概率不高，而且文獻(xiàn)[6]中沒有列出對具體的TSP問題實例的仿真結(jié)果。文獻(xiàn)[7]將嵌套分區(qū)算法應(yīng)用于置換流水作業(yè)優(yōu)化調(diào)度問題，使用啟發(fā)式算法對子域和裙域進(jìn)行抽樣，并對抽樣點進(jìn)行鄰域搜索，該算法比單純的啟發(fā)式算法和鄰域搜索算法有更好的尋優(yōu)能力。文獻(xiàn)[8]針對二次分配問題，在嵌套分區(qū)算法的基礎(chǔ)上提出了一種禁忌嵌套分區(qū)算法，該算法結(jié)合了嵌套分區(qū)算法的全局搜索能力和禁忌搜索算法的局部搜索能力，獲得了比嵌套分區(qū)算法和禁忌搜索算法更優(yōu)的解。文獻(xiàn)[9]提出了一種基于禁忌搜索的復(fù)合嵌套分區(qū)算法用于解決函數(shù)優(yōu)化問題，在嵌套分區(qū)算法中加入禁忌搜索抽樣算子后，減少了回溯次數(shù)，提高了嵌套分區(qū)算法的收斂能力。文獻(xiàn)[10]提出了一種改進(jìn)的嵌套分區(qū)算法，將其應(yīng)用于節(jié)能ATP控制曲線的惰行點搜索，將禁忌搜索思想引入抽樣算子，減少了回溯次數(shù)，增強(qiáng)了嵌套分區(qū)算法的局部搜索能力。

本文提出一種混合改進(jìn)遺傳算法的嵌套分區(qū)算法用于求解TSP問題，該算法用加權(quán)抽樣法產(chǎn)生初始最可能域，用全局?jǐn)?shù)組GL和GP保存每個區(qū)域的歷史最優(yōu)解，設(shè)計實現(xiàn)了一種子域交叉算子和子域變異算子，用改進(jìn)的遺傳算法搜索每個子域和裙域的最好解，在用改進(jìn)遺傳算法搜索裙域最好解的過程中，用改進(jìn)的Lin-Kernighan算法優(yōu)化種群中優(yōu)秀的個體，對TSPLIB中問題實例的仿真實驗結(jié)果表明，本文算法在求解旅行商問題時可以獲得高質(zhì)量的解。

1 嵌套分區(qū)算法求解TSP問題

定義1 回路。本文算法中用一個數(shù)組表示一條回路。例如，用一個數(shù)組 a=(1，6，2，9，8，4，5，7，3，10)表示從城市 1 出發(fā)，依次訪問城市 6，2，9，8，4，5，7，3，10并且最后回到出發(fā)城市1的一條回路。

定義2 區(qū)域和區(qū)域長度。本文中用一個數(shù)組表示一個區(qū)域。用 regionk(region(1)，region(2)，…，region(k))，(1≤k≤n)(n表示城市個數(shù))表示第1個城市固定為城市region(1)，第2個城市固定為城市region(2)，…，第k個城市固定為城市region(k)，剩下的n－k個城市的訪問順序未確定的區(qū)域，稱k為此區(qū)域的長度。一個區(qū)域中可以包含一條或多條回路。

例如，對于10個城市的TSP問題，有2條回路a=(1，6，2，9，8，4，5，7，3，10)，b=(1，6，8，2，9，4，5，7，3，10)，則回路 a 不屬于區(qū)域 region3(1，6，8)，回路b 屬于區(qū)域 region3(1，6，8)。

定義3 單解域。對于TSP問題，只含有一條回路(一個單解)的區(qū)域稱為單解域。

定義4 子域和父域。如果一個區(qū)域T是通過分割區(qū)域P得來的，則稱T為P的子域，P為T的父域。

利用嵌套分區(qū)算法求解旅行商問題時的基本過程如下:

1)分區(qū)[6]:本文中采用的是均勻分區(qū)方法。假設(shè)有n個城市，用1～n對城市進(jìn)行編號，則整個解空間為所有1，2，…，n的排列的集合。選擇城市1固定為訪問的第1個城市，分別將城市2，3，…，n固定為訪問的第2個城市，由此將城市1固定為訪問的第1個城市的解空間分為n－1個子域，用同樣的方法選擇訪問的第3個城市，從而將每個子域n－2等分。按照這種方法，直到所有的子域都成為單解域。如圖1所示。需要說明的是，分別將城市1，2，…，n固定為訪問的第1個城市的解空間包含的解是相同的。

圖1 嵌套分區(qū)算法求解TSP問題的分區(qū)樹

對于n個城市的TSP問題，分區(qū)樹的最大深度是n－1。

2)抽樣:本文采用加權(quán)抽樣法[2]獲得一個區(qū)域的多條回路。

3)選區(qū)[6]:如果本次迭代中具有最優(yōu)可能性指數(shù)的區(qū)域是當(dāng)前最可能域的子域，則將該子域作為下次迭代的最可能域。

4)回溯[6]:如果本次迭代中裙域的可能性指數(shù)為所有區(qū)域中最優(yōu)的，則需要進(jìn)行回溯操作。本文算法中回溯到截至目前為止所找到的最優(yōu)解的父域。

定義5 裙域[6]。設(shè)整個解區(qū)域為Θ，利用均勻分區(qū)方法分割區(qū)域σ(k)為Mσ(k)個子域，并將除區(qū)域σ(k)外的其他區(qū)域合并成一個區(qū)域Θσ(k)，區(qū)域Θσ(k)稱為裙域。

定義6 區(qū)域的可能性指數(shù)[6]。對于TSP問題，將每個區(qū)域中抽樣得到的多個初始回路中的最短回路長度作為該區(qū)域的可能性指數(shù)。

2 嵌套分區(qū)算法的改進(jìn)

2.1 混合改進(jìn)遺傳算法的嵌套分區(qū)算法

在嵌套分區(qū)算法中，如果能夠減少一次回溯，就可以少抽樣2N(Mσ(k)+1)次(其中Mσ(k)為每次分區(qū)的子域個數(shù)，N為每個子域和裙域的抽樣個數(shù))[11]，從而縮短尋優(yōu)時間，提高收斂速度。

圖2 混合改進(jìn)遺傳算法的嵌套分區(qū)算法求解TSP問題

為了減少回溯的次數(shù)和加快收斂速度，本文用全局?jǐn)?shù)組保存求解過程中獲得的每個區(qū)域的歷史最優(yōu)解。使用全局?jǐn)?shù)組GL記錄每個區(qū)域的最短回路長度，即GL(1)記錄區(qū)域region2(1，2)的最短回路長度，GL(2)記錄區(qū)域region2(1，3)的最短回路長度，GL(3)記錄區(qū)域region2(1，4)的最短回路長度，…，GL(n－1)記錄區(qū)域region2(1，n)的最短回路長度。同理，用一個全局?jǐn)?shù)組GP記錄每一區(qū)域的最短回路。令GL(1)，…，GL(n－1)的初始值為80 000(一個較大值)，令m=0(m用來記錄某個單解域的回路連續(xù)屬于同一個最可能域的次數(shù))，當(dāng)m≥5，即連續(xù)5次某個單解域的回路長度最短，輸出最優(yōu)回路和長度。

混合改進(jìn)遺傳算法的嵌套分區(qū)算法求解TSP問題的流程圖如圖2所示。

使用加權(quán)抽樣法產(chǎn)生初始最可能域的算法如下:

在中小規(guī)模TSP問題中，使用本文算法的回溯策略時，當(dāng)p=0.99時可以獲得質(zhì)量最好的解[6]。因此，在本文算法中令p=0.99。

2.2 改進(jìn)遺傳算法搜索子域的最好解

根據(jù)城市之間的距離，計算距離每個城市由近到遠(yuǎn)的10個城市，生成k-近鄰點集(k=10)。

設(shè)種群個數(shù)為m1，進(jìn)化代數(shù)為gens，用加權(quán)抽樣法產(chǎn)生子域regionk(region(1)，region(2)，…，region(k))的m1個初始個體，刪除種群中相同的個體，只保留一個，用k-近鄰法產(chǎn)生新的個體代替被刪除的個體，得到初始種群 P1、P2、…、Pm1，計算出個體 P1、P2、…、Pm1的路徑長度為 L1、L2、…、Lm1。

設(shè)每個個體的局部最優(yōu)解為 PLb1、PLb2、…、PLbm1，其對應(yīng)的長度為 PLl1、PLl2、…、PLlm1。

令 PLbi=Pi，PLli=Li，1≤i≤m1，計算出子域regionk(region(1)，region(2)，…，region(k))的全局最優(yōu)個體PGB及其長度為PGL。

將個體Pj與子域regionk(region(1)，region(2)，…，region(k))的全局最優(yōu)個體PGB使用子域交叉算子進(jìn)行交叉操作，得到個體Pc1j;

將個體Pc1j與局部最優(yōu)個體PLbj使用子域交叉算子進(jìn)行交叉操作，得到個體Pc2j;

將個體Pc2j使用倒置變異和帶約束的3-opt優(yōu)化算子進(jìn)行3-opt優(yōu)化變異，得到Pm2j，計算出路徑長度為 Lmj;如果 Lmj＜ Lj，或 Lmj＞ Lj并且(Lmj－ Lj)/Lj＜0.1，則 Pj=Pm2j;

如果 Lmj＜PLlj，則 PLbj=Pm2j，PLlj=Lmj;

End For

根據(jù)每個個體最新的局部最優(yōu)解 PLb1、PLb2、…、PLbm，更新子域 regionk(region(1)，region(2)，…，region(k))的全局最優(yōu)個體PGB及其長度PGL。

End For

輸出子域regionk(region(1)，region(2)，…，region(k))的全局最優(yōu)個體PGB作為子域regionk(region(1)，region(2)，…，region(k))的最好解。

2.2.1 子域交叉算子

對于子區(qū)域regionk(region(1)，region(2)，…，region(k))加權(quán)抽樣法得到的初始解為 P1、P2、…、Pm1(m1為抽樣個數(shù))，選擇2個個體 Pi和Pj進(jìn)行交叉，設(shè)Pi表示為p(1)，p(2)，…，p(n)，Pj表示為 q(1)，q(2)，…，q(n)，其中 p(1)=q(1)=region(1)，p(2)=q(2)=region(2)，…，p(k)=q(k)=region(k)，Pi和Pj交叉操作后所得的子個體也屬于子區(qū)域 regionk(region(1)，region(2)，…，region(k))的方法如下:

1)在父體Pj中隨機(jī)選擇一個參考城市q(r)，r≥k且 r≤n－1;

2)在父體Pi中找到城市p(u)=q(r)，p(v)=q(r+1)，如果 d(p(u)，p(v))+d(p(v)，p(u+1))+d(p(v－1)，p(v+1))＜d(p(u)，p(u+1))+d(p(v－1)，p(v))+d(p(v)，p(v+1))(d(x，y)表示城市x與城市y之間的距離)，即在父體Pi中刪除城市p(v)，然后在城市p(u)與p(u+1)之間插入城市p(v)，得到新的個體Pi1;

3)依次在父體Pj中取參考城市q(r+1)，…，q(n－1)，重復(fù)步驟2)，直到最終生成子個體Pi1;

4)將父體Pi和父體Pj相互交換，重復(fù)步驟1)、2)和3)，得到子個體Pj1。

使用以上方法可以保證交叉操作產(chǎn)生的子個體Pi1和Pj1屬于子區(qū)域 regionk(region(1)，region(2)，…，region(k))。

2.2.2 子域變異算子

1)倒置變異。

在一個個體中隨機(jī)選擇2個不同的城市，將這2個城市之間組成的路徑逆序，得到變異后的個體。

對于子區(qū)域regionk(region(1)，region(2)，…，region(k))中的個體 Pi，設(shè) Pi表示為 p(1)，p(2)，…，p(n)，其中 p(1)=region(1)，p(2)=region(2)，…，p(k)=region(k)，對個體Pi倒置變異后所得的個體Pmi也屬于子區(qū)域regionk(region(1)，region(2)，…，region(k))的方法如下:

a)隨機(jī)選擇2個不同的城市p(i1)和p(i2)，i1≠i2且 k≤i1，i2≤n。

b)將城市p(i1)和p(i2)之間組成的路徑逆序，得到 Pmi。

2)帶約束的3-opt優(yōu)化算子。

3-opt算法[12]是局部搜索算法中效率最高的kopt鄰域算法，其基本過程是:設(shè)T是一條初始回路，產(chǎn)生3個隨機(jī)位置t1、t3、t5，它們的下一個節(jié)點分別記為 t2、t4、t6，對應(yīng)的 3 條邊的集合記為{(t1，t2)，(t3，t4)，(t5，t6)}，該算法斷開這3條邊試圖找到另一個邊的集合{a，b，c}，使得新產(chǎn)生的回路長度變小。這里是3條邊則稱為3-opt，如圖3(a)所示。如果是2條邊則稱為2-opt，如圖3(b)所示。對于k-opt(k≥2)，最后一個節(jié)點必須與第一個節(jié)點重合。

圖3 3-opt算法和2-opt算法

對于一條巡回路徑，3-opt局部搜索算法就是從巡回路徑中選擇兩兩互不相鄰的3條邊，將這條巡回路徑分成3段路徑，然后重組這3段路徑，重組后有7條可能的巡回路徑，如果這7條巡回路徑中長度最短的巡回路徑小于原來的巡回路徑，則用此長度最短的巡回路徑代替原來的巡回路徑。

分析3-opt算法中邊的移動過程，可以發(fā)現(xiàn)t1和t6一直是連在一起的，也就是說t1和t6之間的點的相對位置保持不變。利用3-opt交換的這一特性，文獻(xiàn)[12]提出了一種帶約束的3-opt優(yōu)化方法，該方法能夠保證對子區(qū)域regionk(region(1)，region(2)，…，region(k))中的個體Pi進(jìn)行3-opt優(yōu)化變異后所得的解也屬于該子區(qū)域。

本文采用文獻(xiàn)[12]中的方法對子區(qū)域regionk(region(1)，region(2)，…，region(k))中的個體Pi進(jìn)行3-opt優(yōu)化變異。

2.3 對Lin-Kernighan算法的改進(jìn)

Lin-Kernighan算法[13]是 1971 年由 Lin Shen和B.W.Kernighan提出的一種解決對稱TSP問題的有效的啟發(fā)式方法。

Lin-Kernighan算法中只允許連續(xù)的邊交換。實驗結(jié)果表明[14]，不允許非連續(xù)的邊交換會大大降低找到最優(yōu)解的概率。為了提高找到最優(yōu)解的概率，本文算法在發(fā)現(xiàn)連續(xù)的邊交換不能再進(jìn)一步改進(jìn)解的質(zhì)量時，便嘗試進(jìn)行非連續(xù)的邊交換。非連續(xù)的邊交換的具體執(zhí)行過程如下。

1)如果2-opt交換產(chǎn)生了2個環(huán)路并且路徑長度是減少的，則轉(zhuǎn)到步驟1.1)，否則，轉(zhuǎn)到步驟2)。

1.1)如果通過2-opt交換連接2個子環(huán)能夠產(chǎn)生一條有效的回路，并且路徑長度是減少的，則進(jìn)行2-opt交換，如圖4(a)所示，然后轉(zhuǎn)步驟5)。

1.2)如果2-opt交換不能夠減少路徑長度，則嘗試3-opt交換，如果通過3-opt交換連接2個子環(huán)能夠產(chǎn)生一條有效的回路，并且路徑長度是減少的，則進(jìn)行3-opt交換，如圖4(b)所示，然后轉(zhuǎn)步驟5)。

1.3)如果3-opt交換不能夠減少路徑長度，則嘗試4-opt交換，如果通過4-opt交換連接2個子環(huán)能夠產(chǎn)生一條有效的回路，并且路徑長度是減少的，則進(jìn)行4-opt交換，如圖4(c)所示，然后轉(zhuǎn)步驟5)。

1.4)如果4-opt交換不能夠減少路徑長度，則嘗試另一個4-opt邊交換(換另一個t7)轉(zhuǎn)步驟1.3);如果所有的4-opt交換都不能夠減少路徑長度，則回到步驟1.2)，嘗試另一個3-opt邊交換(換另一個t5)。

1.5)如果所有的3-opt都不能減少路徑長度，則回到步驟1.1)，嘗試另一個2-opt邊交換(2-opt的變化情況較多:換另一個t4，換另一個t3，換另一個t1)。

1.6)如果所有的 2-opt交換、3-opt交換、4-opt交換都不能減少路徑長度，則轉(zhuǎn)步驟2)。

圖4 非連續(xù)的邊交換

2)如果3-opt交換產(chǎn)生了2個環(huán)路并且路徑長度是減少的，則轉(zhuǎn)到步驟2.1)，否則，轉(zhuǎn)到步驟3)。

2.1)如果通過2-opt交換連接2個子環(huán)能夠產(chǎn)生一條有效的回路，并且路徑長度是減少的，則進(jìn)行2-opt交換，如圖4(d)所示，然后轉(zhuǎn)步驟5)。

2.2)如果通過2-opt交換連接2個子環(huán)能夠產(chǎn)生一條有效的回路并且路徑長度是增加的，則嘗試另一個2-opt邊交換(2-opt的變化情況較多:換另一個t4，換另一個t3，換另一個t1)，然后轉(zhuǎn)步驟2.1)。

2.3)如果所有的2-opt交換都不能減少路徑長度，則轉(zhuǎn)步驟3)。

3)如果4-opt交換產(chǎn)生了2個環(huán)路并且路徑長度是減少的，則轉(zhuǎn)到步驟3.1)，否則，轉(zhuǎn)到步驟4)。

3.1)如果通過2-opt交換連接2個子環(huán)能夠產(chǎn)生一條有效的回路，并且路徑長度是減少的，則進(jìn)行2-opt交換，如圖4(e)或4(f)所示，然后轉(zhuǎn)步驟5)。

3.2)如果通過2-opt交換連接2個子環(huán)能夠產(chǎn)生一條有效的回路并且路徑長度是增加的，則嘗試另一個2-opt邊交換(2-opt的變化情況較多:換另一個t4，換另一個t3，換另一個t1)，然后轉(zhuǎn)步驟3.1)。

3.3)如果所有的2-opt交換都不能減少路徑長度，則轉(zhuǎn)步驟4)。

4)嘗試另一個4-opt邊交換，轉(zhuǎn)步驟3);如果所有的4-opt邊交換都嘗試過了，則嘗試另一個3-opt邊交換，轉(zhuǎn)步驟2);如果所有的3-opt邊交換都嘗試過了，則嘗試另一個2-opt邊交換，轉(zhuǎn)步驟1)。

5)結(jié)束非連續(xù)的邊交換，返回改進(jìn)解。

2.4 改進(jìn)遺傳算法搜索裙域的最好解

用改進(jìn)遺傳算法在搜索裙域最好解的過程中，設(shè)種群個數(shù)為m2，產(chǎn)生初始種群時，從全局?jǐn)?shù)組GP中選擇qr個個體作為裙域的初始種群的一部分個體，其他m2-qr個個體用k-近鄰法產(chǎn)生，設(shè)進(jìn)化代數(shù)為genq。

用改進(jìn)遺傳算法搜索子域的最好解時，存在很多限制條件，交叉操作和變異操作都必須保證產(chǎn)生的解仍然屬于該子域。而在用改進(jìn)遺傳算法搜索裙域的最好解時，交叉操作時需要將子域交叉算子中r≥k這個條件去掉，變異操作時不必使用帶約束的3-opt優(yōu)化算子，而只需使用一般的3-opt優(yōu)化算法，并且可以將倒置變異中k≤i1，i2≤n這個條件去掉。在每一代進(jìn)化結(jié)束后，選擇每一代種群中互不相同的最優(yōu)秀的5個個體，用改進(jìn)的Lin-Kernighan算法進(jìn)行優(yōu)化，然后保存這一代中屬于該裙域的最好解，在genq代進(jìn)化結(jié)束后，輸出所有代中屬于該裙域的最好解作為該裙域的最好解。

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

本文算法運(yùn)行環(huán)境如下:CPU為Intel Pentium 4 2.40 GHz;內(nèi)存為 1 GB;操作系統(tǒng)為 Windows XP sp3;開發(fā)工具及開發(fā)語言分別為 DEV-CPP-4.9.9.2、C語言。為了測試算法的性能，對每一個TSP問題，都運(yùn)行30次。

對于Berlin52問題、Eil51問題和st70問題，m1取20，gens取 30，m2取 30，qr取 20，genq取 50;對于Eil76問題、rd100問題、Eil101問題、Lin105問題、pr107問題、pr124問題、Ch130問題、Ch150問題、pr152問題、rat195問題、kroA200問題，m1取20，gens取40，m2取 50，qr取 30，genq取 80;對于 A280 問題、pcb442 問題，m1取20，gens取 50，m2取60，qr取30，genq取100。將加權(quán)抽樣法產(chǎn)生初始最可能域時的參數(shù)d設(shè)為10。

表1的仿真結(jié)果表明，本文算法對于200個以內(nèi)城市的TSP問題能夠在40秒以內(nèi)求得TSP問題的最優(yōu)解。但是對于200個以上城市的TSP問題，隨著城市規(guī)模的擴(kuò)大，求得最優(yōu)解的時間稍長。

表1 本文算法對TSPLIB中部分問題的仿真結(jié)果

為了比較本文算法和文獻(xiàn)[12]中算法的平均求解時間，將文獻(xiàn)[12]算法在本文算法的運(yùn)行環(huán)境中重新運(yùn)行，對文獻(xiàn)[12]中的每一個TSP問題都運(yùn)行30次，然后計算平均求解時間。

文獻(xiàn)[15]算法的硬件環(huán)境為Pentium Dual-Core CPU 2.20 GHz，內(nèi)存2.0 GB，編程語言為 C++，顯然文獻(xiàn)[15]算法的硬件環(huán)境優(yōu)于本文算法而編程語言與本文相似。

文獻(xiàn)[12]提出了一種改進(jìn)的嵌套分區(qū)算法，用3-opt算法改進(jìn)每個區(qū)域解的質(zhì)量，對于100個城市以下的TSP問題求解質(zhì)量較高。表2將本文算法與文獻(xiàn)[12]中算法的平均求解時間進(jìn)行了比較，本文算法平均能夠在13 s之內(nèi)求得100個以下城市的最優(yōu)解，而文獻(xiàn)[12]中算法的平均求解時間明顯較長，特別是對于rd100問題，本文算法平均能夠在12.5 s內(nèi)求得最優(yōu)解，而文獻(xiàn)[12]中算法平均需要105.2 s才能求得最優(yōu)解。

文獻(xiàn)[15]提出了一種基于距離的改進(jìn)量子交叉遺傳算法，通過在選擇城市時加入父代優(yōu)質(zhì)解的信息，提高了交叉所產(chǎn)生新解的質(zhì)量，從而提高了算法的尋優(yōu)能力。表2將本文算法與文獻(xiàn)[15]中算法的平均求解時間進(jìn)行了比較，結(jié)果表明雖然本文算法的硬件配置要低于文獻(xiàn)[15]中的，但是對于每一個TSP問題，本文算法都能更快地求得最優(yōu)解，對于200個以上城市的TSP問題，隨著城市規(guī)模的增加，本文算法與文獻(xiàn)[15]中算法的平均求解時間差距逐漸加大。

表2 參考文獻(xiàn)中的平均求解時間比較

表2中“/”表示文獻(xiàn)中沒有對相應(yīng)的TSP問題進(jìn)行仿真，沒有仿真結(jié)果。

表3將本文結(jié)果與文獻(xiàn)[12，15-18]的部分結(jié)果進(jìn)行了比較，結(jié)果表明本文算法能夠找到所有問題的最好解，求得的最短路徑長度最短，求解質(zhì)量最高。文獻(xiàn)[12]對于100個以下城市的TSP問題都找到了最優(yōu)解，但是求解時間較長;文獻(xiàn)[15]的算法對于表3中的12個TSP問題都沒有找到最優(yōu)解，求解質(zhì)量最差。

文獻(xiàn)[16]提出了一種改進(jìn)的蟻群算法，該算法采用信息素?fù)]發(fā)因子自適應(yīng)調(diào)整機(jī)制，同時根據(jù)公共路徑降低蟻群算法運(yùn)算時間并提高了算法的搜索能力。對于Eil51問題，將改進(jìn)算法連續(xù)運(yùn)行15次，找到的最短路徑長度為427，沒能找到最優(yōu)解426。

文獻(xiàn)[17]提出了一種模糊人工蜂群算法，將模糊輸入輸出機(jī)制引入到算法中實現(xiàn)蜜源訪問概率的有效調(diào)整，避免算法陷入局部極值。文獻(xiàn)[17]的算法對于Eil76問題和Ch150問題沒有找到最優(yōu)解。

文獻(xiàn)[18]將大洪水算法與2-opt算法融合在一起，提出了求解TSP問題的改進(jìn)大洪水算法。文獻(xiàn)[18]的算法對于Eil101問題、Ch130問題和rat195問題沒有找到最優(yōu)解。

表3 參考文獻(xiàn)中的求解質(zhì)量比較

表3中“/”表示文獻(xiàn)中沒有對相應(yīng)的TSP問題進(jìn)行仿真，沒有仿真結(jié)果。

表3中求的是最短路徑長度，數(shù)值越小，解的質(zhì)量越高。

4 結(jié)束語

本文在原有算法基礎(chǔ)上，提出了一種混合改進(jìn)遺傳算法的嵌套分區(qū)算法。該算法用加權(quán)抽樣法產(chǎn)生初始最可能域，設(shè)計實現(xiàn)了一種子域交叉算子和子域變異算子，并提出了一種改進(jìn)的遺傳算法，然后，用改進(jìn)的遺傳算法搜索每個子域和裙域的最好解。在用改進(jìn)遺傳算法搜索裙域最好解的過程中，改進(jìn)了Lin-Kernighan算法，用改進(jìn)的Lin-Kernighan算法優(yōu)化種群中優(yōu)秀的個體。對TSPLIB中16個問題實例的仿真實驗結(jié)果表明，本文算法在求解旅行商問題時可以獲得高質(zhì)量的解。但是對于城市規(guī)模較大的問題求解時間稍長。下一步將對交叉算子和Lin-Kernighan算法進(jìn)行進(jìn)一步改進(jìn)，使之能解決更大規(guī)模的TSP問題。

[1] 張家善，王志宏，陳應(yīng)顯，等.一種求解旅行商問題的改進(jìn)遺傳算法[J].計算機(jī)系統(tǒng)應(yīng)用，2012，21(9):192-194.

[2] Shi Leyuan，Olafsson S.An integrated framework for deterministic and stochastic optimization[C]//Proceedings of the 1997 Winter Simulation Conference.1997:358-365.

[3] Xia Li，Yin Wenjun，Dong Jin，et al.A hybrid nested partitions algorithm for banking facility location problems[J].IEEE Transactions on Automation Science and Engineering，2010，7(3):654-658.

[4] Yau Hoksung，Shi Leyuan.Nested partitions for the largescale extended job shop scheduling problem[J].Annals of Operations Research，2009，168(1):23-39.

[5] Zhou Wei，Zheng Jianrong，Wang Junfeng.Nested partitions method for assembly sequences merging[J].Expert Systems with Applications，2011，38(8):9918-9923.

[6] 劉昌軍，蘇琴，衛(wèi)軍胡，等.嵌套分割算法在旅行商問題上的應(yīng)用[J].系統(tǒng)仿真學(xué)報，2008，20(24):6858-6861.

[7] 武維，管曉宏，衛(wèi)軍胡.Flow shop問題的嵌套分區(qū)優(yōu)化調(diào)度方法[J].控制理論與應(yīng)用，2009，26(3):233-237.

[8] 武維，衛(wèi)軍胡，管曉宏.一種求解QAP問題的混合嵌套分區(qū)優(yōu)化算法[J].控制與決策，2010，25(6):889-893.

[9] 宋建強(qiáng)，馬良.基于禁忌搜索的復(fù)合嵌套分割算法[J].計算機(jī)應(yīng)用研究，2011，28(4):1260-1262.

[10] 劉曉娟，鄧子淵.改進(jìn)的嵌套分割算法及其在節(jié)能惰行中的應(yīng)用[J].計算機(jī)工程與應(yīng)用，2013，49(10):239-242.

[11] 路曉偉，蔣馥.基于模擬退火的復(fù)合嵌套分割算法[J].系統(tǒng)工程與電子技術(shù)，2004，26(1):99-102.

[12] 宗德才，王康康.改進(jìn)的嵌套分區(qū)算法求解旅行商問題[J].計算機(jī)工程與應(yīng)用，2011，47(24):54-57.

[13] Lin Shen，Kernighan B W.An effective heuristic algorithm for the traveling salesman problem[J].Operations Research，1973，21(2):498-516.

[14] 田偉，田國會，張攀，等.考慮非對稱情形的一類揀選問題的改進(jìn) LK算法求解[J].中國工程科學(xué)，2004，6(11):47-52.

[15] 楊玉，李慧，戴紅偉.改進(jìn)量子交叉遺傳算法在TSP問題中的應(yīng)用[J].南京師范大學(xué)學(xué)報(工程技術(shù)版)，2012，12(3):43-48.

[16] 申鉉京，劉陽陽，黃永平，等.求解TSP問題的快速蟻群算法[J].吉林大學(xué)學(xué)報(工學(xué)版)，2013，43(1):147-151.

[17] 柳寅，馬良.模糊人工蜂群算法的旅行商問題求解[J].計算機(jī)應(yīng)用研究，2013，30(9):2694-2696.

[18] 盛虹平，馬良.求解大規(guī)模旅行商問題的改進(jìn)大洪水算法[J].小型微型計算機(jī)系統(tǒng)，2012，33(2):259-262.