劉永軍　孔佑琳

摘 要：旅行商問題（Traveling Saleman Problem，TSP）是一個典型的組合優(yōu)化問題，針對該問題主要采用動態(tài)規(guī)劃和智能優(yōu)化等算法。為了有效求解TSP問題，設(shè)計了一種帶鄰域操作的差異演化算法。為了克服差異演化算法容易收斂于局部最優(yōu)的弱點，通過引入簇和鄰域的概念，將種群中的個體歸入距離其最近的子種群，用個體的當(dāng)前鄰域極值替換群體的當(dāng)前最佳。同時，算法在進(jìn)化過程中動態(tài)調(diào)整鄰域大小。通過在多個TSP問題的上的仿真實驗表明，該算法在求解TSP問題時魯棒性強(qiáng)，求解精度高。

關(guān)鍵字：旅行商問題；差異演化；動態(tài)鄰域搜索；自適應(yīng)

中圖分類號：TP391 文獻(xiàn)標(biāo)識碼：A 文章編號：2095-2163（2015）06-

Abastract：Traveling Saleman Problem is a classical Combinatorial Optimization Problem. Dynamic design and intelligence optimization are usually used to solve it. In order to overcome the differential evolution algorithm converges to a local optimum easily weakness by introducing the concept of clusters and neighborhood， the population of individuals classified as its nearest sub-population groups， and replace the current individual neighborhood the most good.. At the same time with extreme values，the number of neighborhood is adjust from two to the size of population. Some experiments on classical TSP problem show that this improved DE algorithm is effective and robust to solve TSP and has higher precision.

Keywords：TSP； Differential Evolution； Dynamic Neighborhood Search； Self- adaptive

0引 言

旅行商問題（Traveling Salesman Problem，TSP）源于EULER提出的騎士旅行問題，在我國又被廣泛稱為“貨郎擔(dān)問題”、“郵遞員問題”等，是計算機(jī)科學(xué)、管理學(xué)、運(yùn)籌學(xué)中的一個重要內(nèi)容，屬于典型的組合優(yōu)化范疇。Gaery通過理論方法證明了該問題是一個典型的NP難問題。由于NP難問題具有一定的類歸屬和研究成果擴(kuò)展性，在TSP問題上取得的理論或者實驗成果，可以用于指導(dǎo)求解其它的NP難解問題，又由于TSP問題具有形式簡單、易于描述的特點，在組合優(yōu)化問題中具有一定的代表性，因此該算法經(jīng)常被用于作為研究組合優(yōu)化的典型實驗和驗證平臺，而獲得了學(xué)界多方廣泛且深入的研究。

TSP問題的研究具有非常廣泛的工程應(yīng)用背景和學(xué)術(shù)研究價值，在工程領(lǐng)域中非常多的工程問題其實質(zhì)就是TSP問題，亦或可以轉(zhuǎn)換為TSP問題，如：網(wǎng)絡(luò)通訊、電路板鉆孔、交通調(diào)度、管道鋪設(shè)、電網(wǎng)規(guī)劃等等，因此，快速、有效地實施對TSP問題的研發(fā)處理將會具有較高的實際應(yīng)用價值。

為了有效求解TSP問題，文獻(xiàn)[1]針對螢火蟲算法的特點，提出了一種離散型螢火蟲算法，針對TSP問題專門設(shè)計了算法的更新方式、種群初始化方式、個體的編解碼方式，為了增強(qiáng)算法的局部搜索能力，加快其收斂速度， 在算法中使用了2-opt優(yōu)化算子。通過實驗顯示，該算法的求解要較自適應(yīng)螢火蟲算法具有更高的執(zhí)行精度；文獻(xiàn)[2]通過研究蟻群算法的特點，提出了蟻群算法求解TSP問題的方案，并令蟻群算法根據(jù)啟發(fā)函數(shù) 信息素進(jìn)行算法性能優(yōu)化，提高了算法的收斂速度；文獻(xiàn)[3]同樣利用蟻群算法來求解TSP問題。在該論文中，針對蟻群算法容易早熟的弱點，算法中引入“優(yōu)勝劣汰”的進(jìn)化策略，對每次迭代的隨機(jī)進(jìn)化因子大于進(jìn)化漂變閾值的路徑信息素進(jìn)行二次更新，加快算法的收斂速度；同時利用隨機(jī)進(jìn)化因子的增強(qiáng)算法跳出局部最優(yōu)解的概率基礎(chǔ)，得到相對優(yōu)化的問題求解；文獻(xiàn)[4]提出了應(yīng)用遺傳算法求解TSP的方案。初始種群使用貪婪機(jī)制來構(gòu)造，并使用融合輪盤賭方法和最佳保存策略進(jìn)行選擇操作，針對交叉操作則應(yīng)用兩點三段隨機(jī)交叉的方法。

文獻(xiàn)[5]采用遺傳算法和文獻(xiàn)[6]的基本鄰域機(jī)制以及文獻(xiàn)[7-8]的差分演化思想，為TSP問題求解提出了較好的思路和方法，為了更有效的求解TSP問題，本文設(shè)計一種基于動態(tài)鄰域機(jī)制的差異演化算法求解TSP問題。給出了差異演化算法的編碼機(jī)制，并定義了算法中個體之間的距離和鄰域等概念，通過在差異演化算法中引入個體鄰域的概念，用個體當(dāng)前的鄰域極值替換種群的全局極值，保證種群多樣性，提高算法全局收斂能力。

1 TSP模型和差異演化算法

定義1 存在n個結(jié)點 ，任意兩個結(jié)點之間都存在直接的路徑關(guān)聯(lián)，對于任意兩個結(jié)點 之間的消耗為 。假定從其中任意的某一個結(jié)點 出發(fā)，每一個結(jié)點只能經(jīng)過1次，在經(jīng)過全部的結(jié)點之后重新回到 ，消耗的費(fèi)用是 。問如何規(guī)劃一條合適的路徑 ，使 的值最小，并確定該最小值。

定義2.組合優(yōu)化問題 ，存在兩個決策向量 ，定義這兩個決策向量之間的距離為不同時屬于 和 的元素的個數(shù)，即：

2 求解TSP問題的動態(tài)鄰域差異演化算法

2.1個體編碼方式

根據(jù)TSP問題的描述，采用整數(shù)編碼機(jī)制。將魚群的個體設(shè)置為長度30的整數(shù)串，代表了一個循環(huán)長度。例如：某個體編碼為（3-20-18-9-0-1-2-5-……16），則代表從節(jié)點3開始依次經(jīng)過節(jié)點20、18、9、0、1、2、5…16，形成一條路徑。

2.2適應(yīng)度函數(shù)的設(shè)計

顯而易見，采用如下公式：

描述最短路徑是最直接的表達(dá)方式。TSP問題的目的就是求解公式（4）的最小值。

2.3種群初始化方式

鑒于所求問題為最短路徑，所以種群內(nèi)的個體模式表達(dá)兩個城市之間的距離越短，對于后續(xù)的尋優(yōu)工作就會更加有利。為此，本文依據(jù)兩個城市間的距離，利用輪盤賭的機(jī)制來初始化種群，這一方式使得種群中所包含的解已經(jīng)比較接近最優(yōu)解。

2.4 動態(tài)鄰域差異演化算法

由于差異演化算法的趨優(yōu)性，在后期個體往往容易聚集于局部最優(yōu)個體的周圍，使算法趨于早熟。為了克服原始差異演化算法的這一弱點，在運(yùn)算過程中有必要依據(jù)一定的標(biāo)準(zhǔn)對群體或部分個體進(jìn)行再組織，以維持種群的多樣性。文獻(xiàn)[3]中有Kennedy為粒子群算法提出了一種新的組織結(jié)構(gòu)，該結(jié)構(gòu)增加了空間鄰域和環(huán)形拓?fù)浞椒?，稱為social stereotyping，作者設(shè)計了確定搜索空間的粒子簇的方法，并通過實驗證實了如果使用該粒子所在簇中心值替換個體最優(yōu)值將會提高算法的性能。圍繞這一思想，同樣將鄰域機(jī)制引入差異演化算法，來指導(dǎo)差異演化算法的收斂過程。針對求解TSP問題，將差異演化算法中涉及的數(shù)個概念定義如下。

定義3個體距離 根據(jù)TSP問題的描述以及定義2，設(shè)圖 中具有頂點 個，則定義個體表達(dá)模式為 ，如果任意兩個結(jié)點 之間存在連接通路，則定義差異演化算法中個體之間的距離 為 之間互不相同的邊的數(shù)目。

據(jù)此定義，若存在三個個體 ，則可得到如下定理。

定義4 對于組合優(yōu)化問題 ，定義 為 的 鄰域， 稱為 的鄰居。

由以上定義3、4可對TSP問題搜索空間的鄰域得到相應(yīng)定義如下：

定義5.設(shè)差異演化算法中某個體 代表一個TSP問題的一個特定解，其 鄰域定義為 ，并且， 為大于或等于2的整數(shù)。由此可知，在求解TSP問題中，某個個體 的鄰域集合應(yīng)該是包含種群中所有與 互不相同的邊數(shù)小于或等于2r的個體。

定義6 對于TSP問題某個解 ，如果 且 ，則環(huán)路 是鄰域 的局部最優(yōu)解。

根據(jù)上述的簇定義和距離等的定義，可知在帶有鄰域操作的差異演化算法中，可將此時最佳使用群體中個體的當(dāng)前鄰域極值進(jìn)行替換。取鄰域值，在該鄰域內(nèi)隨機(jī)抽取一個解 ，使用鄰域差異演化算法搜索到問題的局部最優(yōu)解 ，則 ，若 ，將 更新為 ，重復(fù)此過程；若 ，說明尚未找到比 更優(yōu)解，重復(fù)搜索。

為了提高差異演化算法的搜索能力，參考文獻(xiàn)[9]，將其參數(shù)F、CR修改為自適應(yīng)調(diào)整方式，公式為（5）、（6）。

這里的 為均勻分布在[0，1]上的隨機(jī)數(shù)， 為其上界值， 為其初值。

算法2 動態(tài)鄰域差異演化算法（DNDE）

Step1 在解空間內(nèi)隨機(jī)初始化m個個體組成一個種群，并設(shè)定最大迭代次數(shù)為Maxiter；

Step2 設(shè)置算法的各個參數(shù)，個體當(dāng)前鄰域范圍 ；

Step3 計算全部個體的適應(yīng)度值；

Step4 對于種群中所有的個體 ，設(shè)其鄰域內(nèi)局部最優(yōu)為 ，如果 ，則用 更新 ；

Step5 設(shè)當(dāng)前種群最佳 ，對于種群中所有的個體 ，如果 ，則用 更新 ；

Step6 根據(jù)定義動態(tài)改變鄰域范圍， ，至種群最大維數(shù)為止；

Step7 執(zhí)行交叉、變異、選擇操作；

Step8 利用公式（5）和（6）調(diào)整F和CR；

Step9 如果滿足結(jié)束條件，則輸出最終結(jié)果，結(jié)束程序；否則返回step3。

3 仿真實驗與分析

為了驗證算法的有效性，采用C語言進(jìn)行編程，并在開源軟件Code：：Block上進(jìn)行了實現(xiàn)。DNDE算法參數(shù)設(shè)置為：種群規(guī)模100， ， ，CR=0.6，選擇兩側(cè)的兩個相鄰個體為臨近個體。算法的最大迭代次數(shù)為3 000次。

3.1仿真實驗1

首先針對Burma14、Ol iver30、Ei l51三個算例進(jìn)行實驗對比，將DNDE算法運(yùn)行20次，并與文獻(xiàn)[1]提供的兩個算法DGSO與 SAPSO進(jìn)行對比，實驗結(jié)果列于表1。從表1 的實驗數(shù)據(jù)可以看出，對于14個點的TSP問題，DNDE算法與文獻(xiàn)[1]的兩個算法取得的結(jié)果是一樣的，20次全部得到最短的路徑。而對于30個結(jié)點的Oliver30問題，DNDE算法同樣能夠完整得到當(dāng)前已知的最佳解，與DGSO是一樣的，但比SADPSO的解要更加優(yōu)質(zhì)。而在51個結(jié)點的Eil51問題上的求解上，差異演化算法的高效性在此得意清晰展現(xiàn)，求得的結(jié)果與文獻(xiàn)[1]的算法相比則具有顯著優(yōu)越性。

3.2仿真實驗2

為了更好地驗證DNDE算法的計算效率，另外選取了其它的5個TSP問題，再將本算法運(yùn)行20次，并與文獻(xiàn)[2]提供的優(yōu)化ACO算法進(jìn)行對比，實驗結(jié)果列于表2。從實驗結(jié)果對比分析可以看出，本文所提出的NDDE算法在5個典型的TSP問題上，無論是最優(yōu)解、最差解還是平均解方面都明顯勝出于優(yōu)化的ACO算法。從表2列出的DNDE算法平均解可以看出，該算法的平均解更接近于最佳解，說明算法運(yùn)行20次所獲得解之間的離差比較小，算法穩(wěn)定性較高。

4 結(jié)束語

針對TSP問題的特點，定義了差異演化算法的編碼方式、適應(yīng)度函數(shù)以及種群距離等，提出了一種求解TSP問題的改進(jìn)差異演化算法。在此基礎(chǔ)上，為了提高該算法的全局收斂能力，引入了簇的概念和鄰域機(jī)制，從而使算法的后期仍然能夠較好的保持種群多樣性。本次研究和設(shè)計在多個典型TSP問題中的仿真實驗表明，該算法求解精度較高、魯棒性強(qiáng)。

參考文獻(xiàn)：

[1] 周永權(quán)，黃正新，劉洪霞.求解TSP問題的離散型螢火蟲群優(yōu)化算法[J]，電子學(xué)報，2012，40（6）：1164-1170.

[2] 夏小云，李云浩，汪峰. 基于蟻群優(yōu)化算法的TSP問題求解[J]， 江西理工大學(xué)學(xué)報，2009，4（8）：37-39.

[3] 吳華鋒，陳信強(qiáng)，毛奇凰等.基于自然選擇策略的蟻群算法求解TSP問題[J]，通信學(xué)報，2013，4（4）：165-170.

[4] 周澤巖，張喜. 基于改進(jìn)遺傳算法的TSP問題求解的研究[J].物流技術(shù)，2012，31（9）：220-223.

[5] ITOH H. The method of solving for travelling salesman problem using genetic algorithm with immune adjustment mechanism [A].Traveling Salesman Problem， Theory and Applications[C]. Switzerland：Intech Press， 2010：97- 112.

[6] DAS S，ABRAHAM A， et al.Differential evolution using a neighborhood- based mutation operator[J].IEEE Transactions on evolutionary computation，2009，13（ 3）： 526 -553.

[7] 張大斌，楊添柔，溫梅.基于差分進(jìn)化的魚群算法及其函數(shù)優(yōu)化應(yīng)用[J]，計算機(jī)工程，2013，39（5）：18-22.

[8] 王永皎.改進(jìn)自適應(yīng)差分進(jìn)化算法求解大規(guī)模整數(shù)任務(wù)分配[J]，計算機(jī)應(yīng)用，2012，32（ 8） ： 2165-2167.

[9] 王培崇，錢旭. 基于改進(jìn)魚群算法的路徑測試數(shù)據(jù)生成[J]，計算機(jī)應(yīng)用，2013，33（4）：1139-1141.