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

宗德才，王康康，丁 勇

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

0 引言

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

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

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

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

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

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

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

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

例如，對(duì)于10個(gè)城市的TSP問(wèn)題，有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 單解域。對(duì)于TSP問(wèn)題，只含有一條回路(一個(gè)單解)的區(qū)域稱為單解域。

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

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

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

圖1 嵌套分區(qū)算法求解TSP問(wèn)題的分區(qū)樹(shù)

對(duì)于n個(gè)城市的TSP問(wèn)題，分區(qū)樹(shù)的最大深度是n－1。

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

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

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

定義5 裙域[6]。設(shè)整個(gè)解區(qū)域?yàn)棣ǎ镁鶆蚍謪^(qū)方法分割區(qū)域σ(k)為Mσ(k)個(gè)子域，并將除區(qū)域σ(k)外的其他區(qū)域合并成一個(gè)區(qū)域Θσ(k)，區(qū)域Θσ(k)稱為裙域。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

End For

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

End For

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

2.2.1 子域交叉算子

對(duì)于子區(qū)域regionk(region(1)，region(2)，…，region(k))加權(quán)抽樣法得到的初始解為 P1、P2、…、Pm1(m1為抽樣個(gè)數(shù))，選擇2個(gè)個(gè)體 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交叉操作后所得的子個(gè)體也屬于子區(qū)域 regionk(region(1)，region(2)，…，region(k))的方法如下:

1)在父體Pj中隨機(jī)選擇一個(gè)參考城市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)，得到新的個(gè)體Pi1;

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

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

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

2.2.2 子域變異算子

1)倒置變異。

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

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

a)隨機(jī)選擇2個(gè)不同的城市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鄰域算法，其基本過(guò)程是:設(shè)T是一條初始回路，產(chǎn)生3個(gè)隨機(jī)位置t1、t3、t5，它們的下一個(gè)節(jié)點(diǎn)分別記為 t2、t4、t6，對(duì)應(yīng)的 3 條邊的集合記為{(t1，t2)，(t3，t4)，(t5，t6)}，該算法斷開(kāi)這3條邊試圖找到另一個(gè)邊的集合{a，b，c}，使得新產(chǎn)生的回路長(zhǎng)度變小。這里是3條邊則稱為3-opt，如圖3(a)所示。如果是2條邊則稱為2-opt，如圖3(b)所示。對(duì)于k-opt(k≥2)，最后一個(gè)節(jié)點(diǎn)必須與第一個(gè)節(jié)點(diǎn)重合。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

[1] 張家善，王志宏，陳應(yīng)顯，等.一種求解旅行商問(wèn)題的改進(jìn)遺傳算法[J].計(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)軍胡，等.嵌套分割算法在旅行商問(wèn)題上的應(yīng)用[J].系統(tǒng)仿真學(xué)報(bào)，2008，20(24):6858-6861.

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

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

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

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

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

[12] 宗德才，王康康.改進(jìn)的嵌套分區(qū)算法求解旅行商問(wèn)題[J].計(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] 田偉，田國(guó)會(huì)，張攀，等.考慮非對(duì)稱情形的一類揀選問(wèn)題的改進(jìn) LK算法求解[J].中國(guó)工程科學(xué)，2004，6(11):47-52.

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

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

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

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