求解旅行商問題的動(dòng)態(tài)鄰域差異演化算法改進(jìn)研究

劉永軍　孔佑琳

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

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

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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ì)算機(jī)科學(xué)、管理學(xué)、運(yùn)籌學(xué)中的一個(gè)重要內(nèi)容，屬于典型的組合優(yōu)化范疇。Gaery通過理論方法證明了該問題是一個(gè)典型的NP難問題。由于NP難問題具有一定的類歸屬和研究成果擴(kuò)展性，在TSP問題上取得的理論或者實(shí)驗(yàn)成果，可以用于指導(dǎo)求解其它的NP難解問題，又由于TSP問題具有形式簡(jiǎn)單、易于描述的特點(diǎn)，在組合優(yōu)化問題中具有一定的代表性，因此該算法經(jīng)常被用于作為研究組合優(yōu)化的典型實(shí)驗(yàn)和驗(yàn)證平臺(tái)，而獲得了學(xué)界多方廣泛且深入的研究。

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

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

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

1 TSP模型和差異演化算法

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

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

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

2.1個(gè)體編碼方式

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

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

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

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

2.3種群初始化方式

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 仿真實(shí)驗(yàn)與分析

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

3.1仿真實(shí)驗(yàn)1

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

3.2仿真實(shí)驗(yàn)2

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

4 結(jié)束語

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

參考文獻(xiàn)：

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

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

[3] 吳華鋒，陳信強(qiáng)，毛奇凰等.基于自然選擇策略的蟻群算法求解TSP問題[J]，通信學(xué)報(bào)，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ì)算機(jī)工程，2013，39（5）：18-22.

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

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