求解旅行商問題的動態鄰域差異演化算法改進研究

劉永軍　孔佑琳

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

關鍵字：旅行商問題；差異演化；動態鄰域搜索；自適應

中圖分類號：TP391 文獻標識碼：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提出的騎士旅行問題，在我國又被廣泛稱為“貨郎擔問題”、“郵遞員問題”等，是計算機科學、管理學、運籌學中的一個重要內容，屬于典型的組合優化范疇。Gaery通過理論方法證明了該問題是一個典型的NP難問題。由于NP難問題具有一定的類歸屬和研究成果擴展性，在TSP問題上取得的理論或者實驗成果，可以用于指導求解其它的NP難解問題，又由于TSP問題具有形式簡單、易于描述的特點，在組合優化問題中具有一定的代表性，因此該算法經常被用于作為研究組合優化的典型實驗和驗證平臺，而獲得了學界多方廣泛且深入的研究。

TSP問題的研究具有非常廣泛的工程應用背景和學術研究價值，在工程領域中非常多的工程問題其實質就是TSP問題，亦或可以轉換為TSP問題，如：網絡通訊、電路板鉆孔、交通調度、管道鋪設、電網規劃等等，因此，快速、有效地實施對TSP問題的研發處理將會具有較高的實際應用價值。

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

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

1 TSP模型和差異演化算法

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

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

2 求解TSP問題的動態鄰域差異演化算法

2.1個體編碼方式

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

2.2適應度函數的設計

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

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

2.3種群初始化方式

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

2.4 動態鄰域差異演化算法

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

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

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

定義4 對于組合優化問題 ，定義 為 的 鄰域， 稱為 的鄰居。

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

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

定義6 對于TSP問題某個解 ，如果 且 ，則環路 是鄰域 的局部最優解。

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

為了提高差異演化算法的搜索能力，參考文獻[9]，將其參數F、CR修改為自適應調整方式，公式為（5）、（6）。

這里的 為均勻分布在[0，1]上的隨機數， 為其上界值， 為其初值。

算法2 動態鄰域差異演化算法（DNDE）

Step1 在解空間內隨機初始化m個個體組成一個種群，并設定最大迭代次數為Maxiter；

Step2 設置算法的各個參數，個體當前鄰域范圍 ；

Step3 計算全部個體的適應度值；

Step4 對于種群中所有的個體 ，設其鄰域內局部最優為 ，如果 ，則用 更新 ；

Step5 設當前種群最佳 ，對于種群中所有的個體 ，如果 ，則用 更新 ；

Step6 根據定義動態改變鄰域范圍， ，至種群最大維數為止；

Step7 執行交叉、變異、選擇操作；

Step8 利用公式（5）和（6）調整F和CR；

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

3 仿真實驗與分析

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

3.1仿真實驗1

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

3.2仿真實驗2

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

4 結束語

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

參考文獻：

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

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

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

[4] 周澤巖，張喜. 基于改進遺傳算法的TSP問題求解的研究[J].物流技術，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]，計算機工程，2013，39（5）：18-22.

[8] 王永皎.改進自適應差分進化算法求解大規模整數任務分配[J]，計算機應用，2012，32（ 8） ： 2165-2167.

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