求解TSP問題的離散型差分進(jìn)化算法?

寧桂英 曹敦虔 周永權(quán)

（1.廣西科技大學(xué)鹿山學(xué)院 柳州 545616）（2.廣西民族大學(xué)理學(xué)院 南寧 530006）（3.廣西民族大學(xué)信息科學(xué)與工程學(xué)院 南寧 530006）

求解TSP問題的離散型差分進(jìn)化算法?

寧桂英1曹敦虔2周永權(quán)3

（1.廣西科技大學(xué)鹿山學(xué)院 柳州 545616）（2.廣西民族大學(xué)理學(xué)院 南寧 530006）（3.廣西民族大學(xué)信息科學(xué)與工程學(xué)院 南寧 530006）

針對(duì)旅行商（TSP）問題，提出了一種離散型差分進(jìn)化算法，在該算法中，一方面，采用一種新的編碼方法，把僅用于求解連續(xù)域上優(yōu)化問題的差分進(jìn)化算法推廣到能用于求解離散TSP問題；另一方面，引入了2-OPT算子，將全局搜索與局部搜索有機(jī)地結(jié)合，通過(guò)對(duì)經(jīng)典的TSP問題實(shí)例進(jìn)行了測(cè)試，仿真結(jié)果表明，論文提出的算法具有較強(qiáng)的穩(wěn)定性，是求解TSP問題的一種有效的方法。

差分進(jìn)化；旅行商；啟發(fā)式算法；適應(yīng)度；2-OPT

1 引言

旅行商問題（traveling salesman problem，簡(jiǎn)稱TSP）已被證明是一個(gè)典型的難以求解的NP-hand問題，它在生產(chǎn)線布局領(lǐng)域、庫(kù)存配送領(lǐng)域及工程優(yōu)化等領(lǐng)域有著廣泛的應(yīng)用，因此，尋找TSP問題的解具有重要的理論意義與實(shí)際應(yīng)用價(jià)值。對(duì)TSP求解問題，目前的方法主要分為兩大類：一類是精確算法（exact algorithms），如動(dòng)態(tài)規(guī)劃法、分支界限法、Dijkstra算法、Floyd算法、Bellman-Ford算法及改進(jìn)的SPFA算法等［1］。這些算法的思想比較容易理解，理論上也能得到最優(yōu)解，但在計(jì)算效率上不盡人意，難以解決大規(guī)模的問題；另一類是啟發(fā)式算法（heuristic algorithms），如遺傳算法（Genetic Algorithm，A）、模擬退火算法（Simulated Annealing，SA）、蟻群優(yōu)化算法（Ant Colony Optimization，ACO）、禁忌搜索算法（Tabu Search，TS），最近領(lǐng)域搜索（Nearest Neighbor，NN）［2］、分層協(xié)同進(jìn)化免疫算法（Hierarchical Co-evolution Immune Algorithm，HCIA）［3］、細(xì)菌覓食算法（Bacterial Foraging Algorithm）［4］及混合蛙跳算法（Shuffled Frog-Leaping Algorithm，SFLA）［5］等。這些算法雖不能保證在有限的時(shí)間內(nèi)一定能得到問題的最優(yōu)解，但通過(guò)大量的試驗(yàn)表明，這些啟發(fā)式算法最終得到的最優(yōu)解的誤差能達(dá)到令人滿意的程度。因此，啟發(fā)式的群優(yōu)化方法已成為目前人們求解TSP問題的一種有效方法。

差分進(jìn)化算法（Differential Evolution，簡(jiǎn)稱DE）是一種基于實(shí)數(shù)編碼的，用于求解連續(xù)域上優(yōu)化問題的智能優(yōu)化算法，它是1995年由Storn和Price提出的，此后憑借其穩(wěn)健性和強(qiáng)大的全局尋優(yōu)能力在眾多應(yīng)用領(lǐng)域取得成功［6～7］，如：圖像處理、最優(yōu)設(shè)計(jì)、參數(shù)識(shí)別等，盡管DE算法憑借其強(qiáng)有力的性能在連續(xù)優(yōu)化問題上取得了巨大成功，但是在離散優(yōu)化問題上應(yīng)用較少，鑒于此，本文提出用離散差分進(jìn)化算法（DDEA）求解TSP問題，該算法一方面結(jié)合TSP問題本身的特點(diǎn)，對(duì)DE算法提出了一種特殊的適用于求解離散問題的編碼方法，另一方面，為了增強(qiáng)算法的局部搜索能力，加快收斂速度，在DE算法中引入具有較強(qiáng)局部搜索能力的2OPT算子［8］，最后為了驗(yàn)證本文提出算法的性能，對(duì)14到200個(gè)經(jīng)典的TSP問題進(jìn)行了仿真，實(shí)驗(yàn)結(jié)果表明，本文提出的算法在解決中小規(guī)模的TSP問題中能夠以較快的速度得到問題的最優(yōu)解，驗(yàn)證了本文算法的有效性。

2 TSP問題概述

設(shè)某旅行商要拜訪n個(gè)城市，規(guī)定每個(gè)城市必需且只能拜訪一次，最后回到原出發(fā)城市，要求選擇一條路徑，使其沿著該路徑行走的路程為所有路徑中的最小值。

TSP模型可以表示為：設(shè)n個(gè)城市之間的距離矩陣為 D=(dij)n×n，其中dij代表城市i到城市 j的距離（i≠j），若i=j，定義 dij為一個(gè)足夠大的實(shí)數(shù)M ，設(shè) n（n＞3）個(gè)城市分別標(biāo)號(hào)為（1，2，…，n），一個(gè)TSP問題的可行解就是n個(gè)城市標(biāo)號(hào)的環(huán)狀排列，令π(n)為存放n個(gè)城市的任意排列的一維數(shù)組，則可行解的旅行總距離可表示為

一個(gè)TSP問題的最優(yōu)解是使 f(π)取得最小值的排列［9］。

3 求解TSP問題的離散型差分進(jìn)化算法

3.1 標(biāo)準(zhǔn)DE算法步驟

3.1.1 變異操作

變異是差分進(jìn)化算法用來(lái)產(chǎn)生新個(gè)體的一個(gè)關(guān)鍵步驟，變異操作主要通過(guò)下式進(jìn)行：

其中：xp1，xp2為任意選擇的兩個(gè)個(gè)體，p1，p2為［1，M］中任意選取的互不相等的隨機(jī)整數(shù)，F(xiàn)為變異因子，i=1，2，…，M.j=1，2，…，n。

3.1.2 交叉操作

DE算法的交叉操作是將變異后的新個(gè)體與當(dāng)前個(gè)體混合，然后按照以下規(guī)則選擇哪個(gè)個(gè)體將進(jìn)入下一代，交叉操作通常按下式進(jìn)行：

其中 pc為交叉因子，通常 pc?。?，1］之間的實(shí)數(shù)，randlij為［0，1］間隨機(jī)數(shù)。

3.1.3 選擇操作

為保證新生成的個(gè)體Ui是否進(jìn)入下一代中，DE算法在進(jìn)行交叉操作后，需要將新生成個(gè)體的適應(yīng)度與當(dāng)前種群中個(gè)體Xi的適應(yīng)度進(jìn)行比較。如果Ui的適應(yīng)度優(yōu)于 Xi，則選擇Ui進(jìn)入下一代；否則，直接讓舊個(gè)體Xi進(jìn)入下一代，具體操作為

3.2 編碼設(shè)計(jì)

變異操作是DE算法的主要操作，但這種操作是基于實(shí)數(shù)域上的四則運(yùn)算，因此適用于連續(xù)域上的優(yōu)化問題，而對(duì)于離散域上的組合優(yōu)化問題的解是自然數(shù)的情況已不能滿足要求。為了既保留DE算法變異算子的功能，又能解決離散域上的優(yōu)化問題，本文提出一種特殊的編碼方式。對(duì)包含n個(gè)城市的一個(gè)TSP問題，一個(gè)可行的編碼是1到n上的隨機(jī)整數(shù)構(gòu)成的一個(gè)序列，如：序列（3，2，4，1，5）表示編號(hào)為3的城市在1號(hào)位置，編號(hào)為2的城市在2號(hào)位置，編號(hào)為4的城市在3號(hào)位置，編號(hào)為1的城市在4號(hào)位置，編號(hào)為5的城市在5號(hào)位置。通過(guò)DE變異算子之后，整數(shù)的運(yùn)算不再滿足封閉性，但是實(shí)數(shù)是有大小之分的，因此，可通過(guò)對(duì)變異后的實(shí)數(shù)按由小到大排序后再找出原來(lái)的數(shù)在新序中的位置這一方法來(lái)解決離散域上的優(yōu)化問題。下面給出這一編碼的定義。

定義1：設(shè) Xi(t)=(xi1(t)，xi2(t)，…，xin(t))為DE算法第t代的一個(gè)基本個(gè)體，X'i(t)=(xi1'(t)，xi2'(t)，…，(t))為 Xi(t)按由小到大排序后的新個(gè)體，若xij(t)?x'im(t)，則稱個(gè)體分量xij(t)經(jīng)變異后對(duì)應(yīng)分量為m。

如基本個(gè)體（-2.3，4.1，3.2，-1.5，2.4），升序排列后的個(gè)體為（-2.3，-1.5，2.4，3.2，4.1），對(duì)應(yīng)的編碼為（1，5，4，2，3）。

據(jù)定義1，通過(guò)DE算法的變異算子之后的任何個(gè)體均有一組對(duì)應(yīng)的整數(shù)編碼與之對(duì)應(yīng)，因此，通過(guò)這種編碼方法可以解決離散域上的TSP問題。

3.3 局部路徑優(yōu)化設(shè)計(jì)

盡管已有大量實(shí)驗(yàn)證明DE算法具有較強(qiáng)的穩(wěn)定性和全局搜索能力，但與其它優(yōu)化算法一樣，標(biāo)準(zhǔn)DE算法也會(huì)存在收斂速度慢，易陷入局部極優(yōu)等不足。因此，在求解TSP這一NP-hard問題時(shí)，考慮引入具有全局搜索能力的優(yōu)化策略。已有文獻(xiàn)表明，求解TSP問題的算法分為兩大類型：一種是局部啟發(fā)式搜索算法；一種是獨(dú)立于問題的經(jīng)典優(yōu)化算法。常見的局部啟發(fā)式優(yōu)化算法有2-OPT，3-OPT和Lin-Kernighan（LK）等［8，10］。實(shí)驗(yàn)證明，在這些算法中，用2-OPT算子優(yōu)化路徑對(duì)求解TSP問題的局部最優(yōu)解非常有效。但僅靠2-OPT算子本身的特性也會(huì)使問題陷于局部最優(yōu)，因此，本文考慮首次將將具有較強(qiáng)全局搜索能力的DE智能算法與具有局部?jī)?yōu)化能力的2-OPT算子相結(jié)合，在進(jìn)化前期用具有較強(qiáng)搜索能力的DE算法進(jìn)行全面搜索，以增強(qiáng)群體的多樣性，到后期對(duì)得到的路徑再用2-OPT算子進(jìn)行局部?jī)?yōu)化，以提高收斂速度和精度。

3.4 Complete 2-Opt（C2Opt）算子

在本文的算法中，先用DE算法對(duì)群體進(jìn)行優(yōu)化后，再對(duì)所有構(gòu)成路徑用C2OPT算子進(jìn)行局部?jī)?yōu)化。

設(shè)ck為城市所在頂點(diǎn)，d(ci，cj)表示任意兩個(gè)城市i與 j之間的距離，C2OPT算子的具體步驟如下［8］：

Step 1：選 取 一 條 路 徑 c={c1，…，ci，ci+1，…，cj，cj+1，…，cn-1}，并令 i=j=0 ；

Step 2：任選一條邊，記為No.1：(ci，ci+1)，其中i＜n；

Step 3：任選另一條邊，記為No.2：(cj，cj+1)，其中i＜n；

Step 4：如 果 |j-(i+1)| ≥2 且 d(ci，cj)+d(ci+1，cj+1)＜ d(ci，ci+1)+d(cj，cj+1)，則用 2-Opt算子刪 除 邊 (ci，ci+1) 與 (cj，cj+1) ，并 連 接 邊 (ci，cj) 和(ci+1，cj+1)且 ci+1與 cj的指向相反；

Step 5：再以cj作為No.2邊下一個(gè)開始的城市，并令 j=j+1，重復(fù)Step 3～Step 4，直到 j=n-1，如果 j=n-1，令 j+1=0；

Step 6：以ci作為No.1邊下一個(gè)開始的城市，并 i=i+1令，重復(fù)Step 2～ Step 5，直到 i=n-1，如果i=n-1，令i+1=0；

Step 7：重復(fù)Step 2～Step 6直到 N 次，使 N 足夠大，直到所選取的路徑無(wú)交叉邊出現(xiàn)時(shí)終止。

圖1和圖2給出了使用C2OPT算子前和使用C2OPT算子后的示意圖。

圖1 使用C2OPT算子前

圖2 使用C2OPT算子后

3.5 適應(yīng)度函數(shù)選取

本文適應(yīng)度函數(shù)取優(yōu)化后對(duì)應(yīng)路徑長(zhǎng)度的最小值。

3.6 參數(shù)設(shè)計(jì)

變異和交叉操作是DE算法的主要操作，而變異因子和交叉因子選取的好壞直接影響算法的性能，到目前為止，還沒有一種選取方式能適合解決所有問題，據(jù)現(xiàn)有文獻(xiàn)給出的范圍，本文給出了變異算子F和交叉算子CR的最佳取值。以14個(gè)城市的TSP問題為例，此問題的已知的最優(yōu)路徑和為30.8785。

表1 不同參數(shù)運(yùn)行結(jié)果

表1中給出了參數(shù)不同取值后運(yùn)行10次所得平均結(jié)果。從表中可看出，求解TSP問題時(shí)，變異算子F和交叉算子CR的取值的不同對(duì)結(jié)果的影響很大，當(dāng)F=0.5，CR=0.2時(shí)優(yōu)化效果最好，從運(yùn)行10次的平均值來(lái)看，此時(shí)的結(jié)果與最優(yōu)值相當(dāng)。因此，在本文算法中設(shè)置F=0.5，CR=0.2。

3.7 求解TSP問題的離散型DE算法具體步驟：

Step 1.初始化。隨機(jī)生成1～n上的一個(gè)自然數(shù)序列，構(gòu)成一個(gè)個(gè)體，依次生成m個(gè)初始種群，設(shè)置最大進(jìn)化代數(shù)T，變異算子F和交叉算子CR；

Step 2.計(jì)算各個(gè)體的適應(yīng)度；

Step 3.利用式（1）進(jìn)行變異操作；

Step 4.對(duì)變異后的算子利用式定義1方法編碼；

Step 5.利用式（2）進(jìn)行交叉操作；

Step 6.對(duì)交叉后的個(gè)體利用2opt算子進(jìn)行局部?jī)?yōu)化，生成新個(gè)體；

Step 7.選擇操作；

Step 8.判斷是否達(dá)到迭代要求，若是，停止，并輸出路徑和的最優(yōu)結(jié)果，若否，則轉(zhuǎn)Step 3。

4 算法性能分析

對(duì)本文提出的算法，在線性能定義如下：

定義2：設(shè) f(t)為第t代群體的平均適應(yīng)度，T為進(jìn)化代數(shù)，則在同樣的環(huán)境下，稱為算法的在線性能。

在線性能表示算法在直到當(dāng)前為止的時(shí)間內(nèi)得到的所有性能的平均值，反映了算法的動(dòng)態(tài)性能，圖3給出了本文算法的在線性能曲線。

圖3 在線性能曲線圖

從圖3可以看出，本文提出的算法具有較強(qiáng)的穩(wěn)定性。

5 算例測(cè)試

由于Oliver30和Eil51經(jīng)常被用來(lái)測(cè)試各種算法的測(cè)試實(shí)例，因此本文首先測(cè)試了Burma14，坐標(biāo)為（16.47，96.10），（16.47，94.44），（20.09，92.54），（22.39，93.37），（25.23，97.24），（22，96.05），（20.47，97.02），（17.20，96.29），（16.30，97.38），（14.05，98.12），（16.53，97.38），（21.52，95.59），（19.41，97.13），（20.09，94.55）及Oliver30和Eil51的TSP問題，表2給出了本文算法的測(cè)試結(jié)果，并與文獻(xiàn)［12］DGSO算法和文獻(xiàn)［13］的SADPSO算法及文獻(xiàn)［14］的ACO算法的結(jié)果進(jìn)行了比較，從測(cè)試結(jié)果可以看出，四種算法對(duì)Burma14都能找到最優(yōu)解，而對(duì)于Oliver30問題，本文算法進(jìn)化200代就找到最優(yōu)解，而且進(jìn)化代數(shù)遠(yuǎn)比SADPSO少，收斂速度快，對(duì)Eil51問題，雖然與目前已知最優(yōu)解有些差值，差值為1.3，但與文獻(xiàn)相比都有所改進(jìn)，說(shuō)明本文算法的有效性。

表2 本文算法與相關(guān)文獻(xiàn)結(jié)果比較

圖4～圖7分別給出了Oliver30和Eil51問題的最優(yōu)路徑圖和進(jìn)化曲線圖。

圖4 本文算法優(yōu)化Oliver30算例的路徑圖

圖5 本文算法優(yōu)化Oliver30算例的進(jìn)化曲線圖

圖6 本文算法優(yōu)化Eil51算例的路徑圖

圖7 本文算法優(yōu)化Eil51算例的進(jìn)化曲線圖

為進(jìn)一步驗(yàn)證該算法的有效性，本文選自城市數(shù)量為 48～200 的 Att48、kroa100、bier127、pr144、kroa200幾個(gè)經(jīng)典TSP問題進(jìn)行了測(cè)試，這些測(cè)試實(shí)例選自國(guó)際通用的TSP標(biāo)準(zhǔn)庫(kù)TSPLIB［15］。TSPLIB是一個(gè)開放的網(wǎng)絡(luò)資源，其中收集了各種規(guī)模的TSP實(shí)例，并提供了所有實(shí)例的最優(yōu)解作參考。為降低誤差，本文與所給文獻(xiàn)的參數(shù)設(shè)置基本保持一致，本文對(duì)每個(gè)算例運(yùn)行10次，取其最優(yōu)解，最差解和平均解作比較，并給出了本文算法所得結(jié)果的偏差率。最大進(jìn)化代數(shù)為200，變異因子F=0.5，交叉因子CR=0.2，所得結(jié)果如表3所示。

從表3可以看出，對(duì)att48問題，本文算法每次都能找到問題的最優(yōu)解，偏差為0，對(duì)Kroa100問題，雖然比標(biāo)準(zhǔn)庫(kù)多出1，但是比文獻(xiàn)［16］的改進(jìn)的演化算法和文獻(xiàn)［18］的離散型細(xì)菌覓食算法及文獻(xiàn)［22］的多角色蟻群算法求解的結(jié)果好，而且進(jìn)化代數(shù)少，耗時(shí)短，對(duì)bier127和kroa200問題，本文進(jìn)化200代得到的最優(yōu)結(jié)果較文獻(xiàn)［20］的ACO&&SS算法進(jìn)化2000代的效果好，而且也明顯優(yōu)于文獻(xiàn)［21～22］，充分顯示本文算法的優(yōu)越性，對(duì)pr144問題，找到的最優(yōu)解比標(biāo)準(zhǔn)庫(kù)給出的少2，從整個(gè)計(jì)算結(jié)果來(lái)看，本文算法計(jì)算偏差率都很低，說(shuō)明該算法具有很強(qiáng)的穩(wěn)定性和魯棒性，能有效解決中小規(guī)模的TSP問題。

表3 本文算法計(jì)算結(jié)果與文獻(xiàn)結(jié)果對(duì)比

偏差率是體現(xiàn)計(jì)算結(jié)果與最優(yōu)解的偏離程度，偏差率越小，表明算法越穩(wěn)定。本文中提到的偏差率計(jì)算公式為

圖8 本文算法優(yōu)化Att48算例的路徑圖

圖9 本文算法優(yōu)化Kroa100算例的路徑圖

圖8～圖12給出了本文算例Att48、kroa100、bier127、pr144、kroa200的最優(yōu)路徑圖

圖10 本文算法優(yōu)化Bier127算例的路徑圖

圖11 本文算法優(yōu)化pr144算例的路徑圖

圖12 本文算法優(yōu)化Kroa200算例的路徑圖

6 結(jié)語(yǔ)

本文針對(duì)求解TSP問題，提出了一種求解TSP問題的離散型差分進(jìn)化算法，通過(guò)特殊的編碼方式和適當(dāng)?shù)膮?shù)測(cè)試設(shè)置，并首次將具有良好局部搜索能力的2-OPT算法與差分進(jìn)化算法相融合，將僅用于求解連續(xù)域上優(yōu)化問題算法拓展到用于解決離散組合優(yōu)化問題。并選取了TSPLIB標(biāo)準(zhǔn)庫(kù)中的幾個(gè)14～200的TSP問題進(jìn)行了測(cè)試仿真，仿真結(jié)果表明，在較少的進(jìn)化代數(shù)的條件下，本文提出的算法所得到的最優(yōu)解與TSPLIB中的最優(yōu)解的偏差率都很低，說(shuō)明本文算法在求解中小規(guī)模TSP問題時(shí)是有效可靠的。

今后的工作需將本算法進(jìn)一步改進(jìn)、優(yōu)化以解決大規(guī)模的TSP問題及其它離散域上的復(fù)雜組合優(yōu)化問題。

［1］李峰，莊東.運(yùn)籌學(xué)［M］.機(jī)械工業(yè)出版社，2014（4）：243-255.LI Feng，ZHUANG Dong.Qperations Research［M］.China Machine Press，2014，4：243-255.

［2］武妍，包建軍.一種新的求解TSP的混合量子進(jìn)化算法［J］.計(jì)算機(jī)應(yīng)用，2006，26（10）：2433-2436.WU Yan，BAO Jianjun.New mixed quantum-inspired evolutionary algorithm for TSP［J］.Computer Applications，2006，26（10）：2433-2436.

［3］吳建輝，張兢，張小剛，等.分層協(xié)同進(jìn)化免疫算法及其在 TSP 問題中的應(yīng)用［J］.電子學(xué)報(bào)，2011，39（2）：336-340.WU Jianhui，ZHANG Jing，ZHANG Xiaogang，et al.Hierarchical Co-Evolution Immune Algorithm and Its Application on TSP［J］.Acta Electronica Sinica，2011，39（2）：336-340.

［4］尤夢(mèng)麗，雷秀娟.改進(jìn)的細(xì)菌覓食算法求解TSP問題［J］.廣 西 大 學(xué) 學(xué) 報(bào) 自 然 科 學(xué) 版 ，2013，38（6）：1437-1439.YOU Mengli，LEI Xiujuan.An improved bacterial foraging algorithm for the traveling salesman problem［J］.Journal of Guangxi University（Natural Science Edition），2013，38（6）：1437-1439.

［5］張敬敏，馬麗，李媛媛.求解TSP問題的改進(jìn)混合蛙跳算法［J］.計(jì)算機(jī)工程與應(yīng)用，2012，48（11）：47-50.ZHANG Jingmin，MA Li，LI Yuanyuan.Improved shuffled frog-leaping algorithm for traveling salesman problem［J］.Computer Engineering and Applications，2012，48（11）：47-50.

［6］曾宇容，王林，富慶亮.基于DE和PSO的混合智能算法及其在模糊EOQ模型中的應(yīng)用［J］.計(jì)算機(jī)應(yīng)用研究，2012，29（2）：438-441.ZENG Yurong，WANG Lin，F(xiàn)U Qingliang.Hybrid intelligent algorithm based on differential evolution and particle swarm optimization algorithm and its application in fuzzy EOQ model［J］.Application Research of Computers，2012，29（2）：438-441.

［7］WANG Lin，HE Jing，WU De-sheng，et al.A novel differential evolution algorithm for joint replenishment problem under interdependence and its application［J］.International Journal of Production Economics，2012，135（1）：190-198.

［8］Lin S.Kernigham B W.An effective heuristic algorithm for the travelling salesman problem［J］.Operations Research，1973，21（2）：4982-5161.

［9］Dorigo M.Stutzle T.Ant Colony Optimization［M］.Massachusetts：MIT Press，London，England，2004：69-75.

［10］祝崇雋，劉民，吳澄，等.針對(duì)模糊需求的VRP的兩種2-OPT算法［J］.電子學(xué)報(bào)，2001，29（8）：1035-1037.ZHU Chongjun，LIU Min，WU Cheng，et al.Two kinds of 2-opt algorithm for VRP with Fuzzy demand［J］.Acta Electronica Sinica，2001，29（8）：1035-1037.

［11］Peng Gang，Ichiro Ilmura，Shigeru Nakayma.An Evolutionary Multiple Heuristic with Genetic Local Search for Solving TSP［J］.International Journal of Information Technology，2008，14（2）：1-11.

［12］周永權(quán)，黃正新，劉洪霞.求解TSP問題的離散型螢火蟲群優(yōu)化算法［J］.電子學(xué)報(bào)，2012，40（6）：1164-1170.ZHOU Yongquan，HUANG Zhengxin，LIU Hongxia.Discrete Glowworm Swarm Optimization Algorithm for TSP Problem［J］.Acta Electronica Sinica，2012，40（6）：1164-1170.

［13］張長(zhǎng)勝，孫吉貴，歐陽(yáng)丹彤.一種自適應(yīng)離散粒子群算法 及 其 應(yīng) 用 研 究［J］.電 子 學(xué) 報(bào) ，2009，37（2）：299-304.ZHANG Changsheng，SUN Jigui，OUYANG Dantong.A Self-Adaptive Discrete Particle Swarm Optimization Algorithm［J］.Acta Electronica Sinica，2009，37（2）：299-304.

［14］吳慶洪，張紀(jì)會(huì)，徐心和.具有變異特征的蟻群算法［J］.計(jì)算機(jī)研究與發(fā)展，1999，36（10）：1240-1245.WU Qinghong，ZHANG Jihui，XU Xinhe.An ant colony algorithm with mutation features［J］.Journal of Computer Research and Development，1999，36（10）：1240-1245.

［15］ TSP Library.http：//www.Iwr.uni-heideberg.de/iwr.compot/software/TSPLIB95/TSP.LIB.html.

［16］蔡之華，彭錦國(guó)，高偉，等.一種改進(jìn)的求解TSP問題的演化算法［J］.計(jì)算機(jī)學(xué)報(bào)，2005，28（5）：823-829.CAI Zhihua，PENG jinguo，GAO Wei，et al.An Improved Evolutionary Algorithm for the Traveling Salesman Problem［J］.Chinese Journal of Computers，2005，28（5）：823-829.

［17］孫光福，李程俊，張冬梅，等.一種求解TSP問題的演化算法［J］.計(jì)算機(jī)工程，2011，37（11）：209-211.SUN Guangfu，LI Chengjun，ZHANG Dongmei，et al.Evolutionary Algorithm for Solving Traveling Salesman Problem［J］.Computer Engineering，2011，37（11）：209-211.

［18］王勇臻，陳燕，李桃迎.離散型細(xì)菌覓食算法求解TSP問題［J］.計(jì)算機(jī)應(yīng)用研究（網(wǎng)絡(luò)版），2014，31（12）：3642-3645.WANG Yongzhen，CHEN Yan，LI Taoying.Discrete bacteria foraging optimization algorithm for solving TSP［J］.Application Research of Computers，2014，31（12）：3642-3645.

［19］饒衛(wèi)振，金淳，黃英藝.求解TSP問題的最近領(lǐng)域與插入混合算法［J］.系統(tǒng)工程理論與實(shí)踐，2011，31（8）：1420-1426.RAO Weizhen，JIN Chun，HUANG Yingyi.Hybird algorithm，of the nearest neighbor and insertion for the traveling salesman problem［J］.Systems Engineering-Theory&Practice，2011，31（8）：1420-1426.

［20］張曉霞，唐立新.一種求解TSP問題的ACO&&SS算法設(shè)計(jì)［J］.控制與決策，2008，23（7）：765-766.ZHANG Xiaoxia，TANG Lixin.An ACO＆SS algorithm for traveling salesman problem［J］.Control and Decision，2008，23（7）：762-766.

［21］王忠英，白艷萍，邱利霞.經(jīng)過(guò)改進(jìn)的求解TSP問題的蟻群算法［J］.數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2012，42（4）：133-140.WANG Zhongying，BAI Yan-ping，YUE Lixia.An Improved Ant Colony Algorithm for Solving TSP Problems［J］.Mathematics in Practice and Theory，2012，42（4）：133-140.

［22］杜鵬楨，唐振民，孫研.一種面向?qū)ο蟮亩嘟巧伻核惴捌銽SP問題求解［J］.控制與決策，2014，10（29）：1733-1734.DU Pengzhen，TANG Zhenmin，SUN Yan.An object-oriented multi-role ant colony optimization algorithm for solving TSP problem［J］.Control and Decision，2014，10（29）：1733-1734.

A Discrete Differential Evolution Algorithm for TSP Problem

NING Guiying1CAO Dunqian2ZHOU Yongquan3
（1.Lushan College of Guangxi University Science and Technology，Liuzhou 545616）（2.College of Science，Guangxi University for Nationalities，Nanning 530006）（3.College of Information Science and Engineering，Guangxi University for Nationalities，Nanning 530006）

A discrete differential evolution algorithm is proposed for solving traveling salesman problem（TSP）in this article.In the algorithm，on the one hand，the differential evolution algorithm with a new coding method is used to solve a discrete TSP，which is often used to solve problems on a continuous domain.On the other hand，the 2-OPT algorithm is also introduced；the new algorithm combined the global search with the local search effectively.The classical TSP has been tested，the simulation results show that the proposed algorithm has strong stability and it is an effective method for solving TSP.

differential evolution，TSP，heuristic algorithm，fitness，2-OPT

TP183

10.3969/j.issn.1672-9722.2017.11.012

Class Number TP183

2017年5月9日，

2017年6月29日

國(guó)家自然科學(xué)基金項(xiàng)目（編號(hào)：61463007）；2015年度廣西高?？茖W(xué)技術(shù)研究項(xiàng)目（編號(hào)：KY2015YB521）；2015年度廣西教育廳科學(xué)研究項(xiàng)目（編號(hào)：KY2015YB081）資助。

寧桂英，女，碩士，講師，研究方向：進(jìn)化計(jì)算及應(yīng)用。曹敦虔，男，碩士，講師，研究方向：計(jì)算智能及多元樣條函數(shù)。周永權(quán)，男，博士，教授，博導(dǎo)，研究方向：計(jì)算智能、智能優(yōu)化、神經(jīng)網(wǎng)絡(luò)。