一種基于鄰域搜索機(jī)制的旅行商問(wèn)題求解?

阮?yuàn)櫮?，陳俊風(fēng)，顧 菁，王思睿

（河海大學(xué)物聯(lián)網(wǎng)工程學(xué)院，常州213022）

一種基于鄰域搜索機(jī)制的旅行商問(wèn)題求解?

阮?yuàn)櫮龋惪★L(fēng)，顧 菁，王思睿

（河海大學(xué)物聯(lián)網(wǎng)工程學(xué)院，常州213022）

旅行商問(wèn)題是一個(gè)經(jīng)典的數(shù)學(xué)組合優(yōu)化問(wèn)題，其廣泛的工程應(yīng)用背景促進(jìn)了旅行商問(wèn)題求解方法的快速發(fā)展。針對(duì)旅行商問(wèn)題中最優(yōu)路徑的連接特點(diǎn)，提出了兩種鄰域搜索方法：鄰域隨機(jī)性搜索法和鄰域概率性搜索法。這兩種鄰域搜索法對(duì)旅行商問(wèn)題解的質(zhì)量具有一定的提高能力，其中，為了加快搜索速度，在算法前期采用了循環(huán)倒置算子。實(shí)驗(yàn)結(jié)果表明算法在求解小規(guī)模旅行商問(wèn)題時(shí)具有良好的尋優(yōu)性能。最后將該算法與標(biāo)準(zhǔn)遺傳算法結(jié)合，并進(jìn)行了實(shí)驗(yàn)結(jié)果對(duì)比。實(shí)驗(yàn)數(shù)據(jù)顯示結(jié)合后的算法搜索性能優(yōu)于單一的兩種優(yōu)化算法，提高了算法搜索解的能力。

旅行商問(wèn)題；鄰域；隨機(jī)搜索；概率搜索；循環(huán)倒置；最優(yōu)路徑

1 引 言

旅行商問(wèn)題（Traveling Salesman Problem，TSP）是組合優(yōu)化［1］中一個(gè)易于描述但至今尚未徹底解決的古老而又困難的問(wèn)題，是著名的NP－h(huán)ard［2］問(wèn)題。旅行商問(wèn)題在工程上具有廣泛的實(shí)際應(yīng)用背景，最早應(yīng)用于校車路線的優(yōu)化。目前旅行商問(wèn)題已廣泛應(yīng)用于電路板設(shè)計(jì)、城市規(guī)劃、交通運(yùn)輸、物流配送等領(lǐng)域。因此，對(duì)旅行商問(wèn)題進(jìn)行研究具有重要意義，一直以來(lái)受到學(xué)者們的大量關(guān)注，是組合優(yōu)化領(lǐng)域中的研究熱點(diǎn)。

針對(duì)目前不同的實(shí)際應(yīng)用背景衍生出了多種不同類型的旅行商問(wèn)題，如非對(duì)稱旅行商問(wèn)題、多旅行商問(wèn)題、多目標(biāo)旅行商問(wèn)題、黑白旅行商問(wèn)題等，它們都可以轉(zhuǎn)換成旅行商問(wèn)題進(jìn)行求解。旅行商問(wèn)題的求解方法主要分為以線性規(guī)劃法、分支定界法為代表的精確算法［3－4］和以啟發(fā)式算法為代表的近似算法［5－6］。近似算法求解性能優(yōu)于精確算法，應(yīng)用性也比精確算法廣。通過(guò)觀察旅行商問(wèn)題中最優(yōu)路徑圖的每個(gè)城市連接特性后發(fā)現(xiàn)，利用鄰域搜索機(jī)制、對(duì)各個(gè)城市的鄰域進(jìn)行深度尋優(yōu)的思想對(duì)旅行商問(wèn)題的求解找到了一個(gè)合適的近似算法。

2 TSP描述

TSP最早可追溯到18世紀(jì)騎士周游問(wèn)題，又稱旅行推銷員問(wèn)題［7］。

TSP可描述為：推銷員打算到n個(gè)城市進(jìn)行產(chǎn)品推銷，從其中一個(gè)城市出發(fā)，要求找到一條通過(guò)所有城市再回到起點(diǎn)的最短路徑，每座城市必須且只能訪問(wèn)一次。

設(shè)n個(gè)城市集合為

城市之間的距離為

則上述問(wèn)題轉(zhuǎn)化為如下優(yōu)化問(wèn)題：

其中kij為

圖論語(yǔ)言描述則為：一個(gè)帶權(quán)圖G＝（V，E），V＝｛1，2，…，n｝表示頂點(diǎn)集，E＝｛eij＝（i，j），i，j∈V，i≠j｝表示邊集，尋求G的一個(gè)使邊長(zhǎng)最小即權(quán)值最小的Hamilton回路［8］。

3 鄰域搜索

通過(guò)對(duì)最優(yōu)路徑圖研究后發(fā)現(xiàn)，依據(jù)總體路徑最短的特征，每個(gè)城市在離自己距離較近的多個(gè)城市內(nèi)選擇合適的城市進(jìn)行連接。并非所有城市都與自己的最近鄰城市連接。若所有城市選擇與最近鄰的城市相連，路徑很容易陷入局部最優(yōu)。因此本文根據(jù)最優(yōu)路徑各城市的這種連接特點(diǎn)，提出兩種新的鄰域搜索法，避免算法過(guò)早陷入局部最優(yōu)。

3.1 鄰域范圍內(nèi)隨機(jī)搜索

當(dāng)前所有N個(gè)個(gè)體的集合記為U＝｛u1，u2，……，uN｝，對(duì)每個(gè)城市找出與其相鄰比較近的n個(gè)城市作為一個(gè)集合C＝｛c1，c2，……，cn｝，n的個(gè)數(shù)選擇對(duì)最優(yōu)解的尋找有很大影響。針對(duì)當(dāng)前城市i，在由n個(gè)城市組成的鄰域范圍內(nèi)利用隨機(jī)選擇方式進(jìn)行下個(gè)城市j的選擇。若C中所有城市都已被遍歷過(guò)，則選擇不包含在C內(nèi)、并離i最近的城市j作為下個(gè)城市訪問(wèn)點(diǎn)，避免城市連線出現(xiàn)交叉現(xiàn)象。

3.2 鄰域范圍內(nèi)概率搜索

對(duì)于每個(gè)城市，找出與其相鄰較近的n個(gè)城市作為一個(gè)集合C，同時(shí)計(jì)算整體U的平均路徑長(zhǎng)度。為了防止路徑過(guò)大的個(gè)體影響整體的平均值，在計(jì)算平均值時(shí)去除路徑最大的個(gè)體。統(tǒng)計(jì)路徑長(zhǎng)度小于平均值的個(gè)體總數(shù)k。對(duì)于路徑長(zhǎng)度小于均值的k個(gè)個(gè)體，統(tǒng)計(jì)與城市i相鄰的集合C中每個(gè)城市出現(xiàn)的次數(shù)m，計(jì)算C中每個(gè)城市出現(xiàn)的概率p＝m/k，根據(jù)輪盤賭選擇方式選擇下一個(gè)訪問(wèn)城市。若下個(gè)訪問(wèn)城市的概率為0，則對(duì)為0的城市概率做歸一化處理，保證每個(gè)城市都可能被訪問(wèn)到，防止最優(yōu)解被丟失。

4 循環(huán)倒置算子

為了加快前期尋找最優(yōu)解的速度，在算法初期采用了倒置算子［9］，即隨機(jī)選取個(gè)體中的城市片段進(jìn)行倒置，若倒置后個(gè)體的距離小于原先個(gè)體，則用新個(gè)體替換原先個(gè)體。為了不失去統(tǒng)一性，將個(gè)體中所有城市構(gòu)成一個(gè)循環(huán)圈，首尾附近的城市片段也可參與倒置操作，避免局部最優(yōu)城市片段的丟失，增加搜索到最優(yōu)解的概率。

5 算法結(jié)構(gòu)

根據(jù)以上描述，本文算法的基本結(jié)構(gòu)如下：

（1）初始化：隨機(jī)生成N個(gè)個(gè)體，保持整體多樣性。設(shè)置最大進(jìn)化迭代次數(shù)。

（2）算法前期：采用循環(huán)倒置算子，使群體較快收斂到最優(yōu)值附近，實(shí)驗(yàn)中前期的代數(shù)設(shè)為最大進(jìn)化代數(shù)的1/5。

（3）算法中期：循環(huán)倒置算子和鄰域搜索法共同進(jìn)行，增加尋優(yōu)速度，提高尋優(yōu)概率。實(shí)驗(yàn)中中期的代數(shù)設(shè)為最大進(jìn)化代數(shù)的2/5。

（4）算法后期：利用鄰域搜索法在全局中逐步尋找最優(yōu)解。

（5）終止條件：當(dāng)達(dá)到最大迭代次數(shù)時(shí)算法停止，若沒有達(dá)到則返回到步驟（2）繼續(xù)迭代。

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

實(shí)驗(yàn)中用matlab.R2012a軟件實(shí)現(xiàn)算法對(duì)TSP的求解。初始化設(shè)置個(gè)體總個(gè)數(shù)為30，最大迭代次數(shù)400，TSP城市采用TSP數(shù)據(jù)庫(kù)中的burma14（最優(yōu)解為30.8785）。針對(duì)不同的鄰域城市個(gè)數(shù)n進(jìn)行多次測(cè)試，實(shí)驗(yàn)結(jié)果如表1所示。其中Ave表示程序運(yùn)行10次后得到的平均值，Opt表示10次中得到的最優(yōu)值，K表示10次中得到最優(yōu)值的次數(shù)。

表1 RSN和PSN在不同的n條件下得到的實(shí)驗(yàn)結(jié)果

由表1可知，鄰域搜索法在n為2到6時(shí)都可尋到最優(yōu)結(jié)果，但隨著鄰域個(gè)數(shù)的不同，得到的平均值不同，搜索到最優(yōu)值的次數(shù)也不相同。對(duì)于隨機(jī)性鄰域搜索，當(dāng)n＝5時(shí)尋優(yōu)效果最佳；對(duì)于概率性鄰域搜索，當(dāng)n＝4時(shí)尋優(yōu)效果最佳，并且概率性鄰域搜索成功率高于隨機(jī)性搜索成功率。

根據(jù)以上實(shí)驗(yàn)結(jié)果，對(duì)標(biāo)準(zhǔn)的30個(gè)城市（最優(yōu)解為423.7406）進(jìn)行了測(cè)試。鄰域城市個(gè)數(shù)n分別為4、5和6，個(gè)體個(gè)數(shù)仍為30，最大迭代次數(shù)為800。由于遺傳算法具有全局性，最后將該算法的兩種情況分別與標(biāo)準(zhǔn)遺傳算法（SGA）結(jié)合，設(shè)置SGA的變異概率為0.05，交叉概率為0.9，種群大小為30，最大迭代次數(shù)為800代。得到的實(shí)驗(yàn)結(jié)果如表2所示。

結(jié)合后得出的實(shí)驗(yàn)結(jié)果表2 不同n條件下RSN和PSN與SGA

由表2可知，鄰域隨機(jī)搜索比概率尋優(yōu)效率高，但算法單獨(dú)運(yùn)行時(shí)易陷入局部最優(yōu)。針對(duì)不同的城市規(guī)模應(yīng)設(shè)置不同的鄰域城市個(gè)數(shù)。該算法與SGA結(jié)合后在n＝5時(shí)尋到了最優(yōu)解，提高了算法搜索效率，使得解的質(zhì)量得到了相應(yīng)提高。

觀察表1和表2可知，此算法對(duì)于小規(guī)模的TSP搜索效果較好。與其它算法融合提高了算法搜索性能，增強(qiáng)了尋優(yōu)能力。但在實(shí)驗(yàn)過(guò)程中總運(yùn)行時(shí)間偏慢，因此該算法在運(yùn)行速度上有待進(jìn)一步加強(qiáng)。

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

基于鄰域搜索機(jī)制的旅行商問(wèn)題求解主要是針對(duì)TSP中最優(yōu)解的城市連接規(guī)則，在鄰域范圍內(nèi)根據(jù)隨機(jī)尋優(yōu)和鄰域范圍內(nèi)概率尋優(yōu)的方法來(lái)求解TSP，實(shí)驗(yàn)結(jié)果說(shuō)明其具有一定的尋優(yōu)能力，并且與其它智能優(yōu)化算法的結(jié)合有助于算法性能的提高，因此本文方法與其它算法的融合將是下一步值得繼續(xù)研究的方向。

［1］ Lenstra JK，Kan A H G R，Shmoys D B.The traveling salesman problem：a guided tour of combinatorial optimization［M］.New York：Wiley，1985.

［2］ Garey M R，Johnson D S.Computers and Intractability：a guide to the theory of NP－Completeness［M］.San Francisco：Freeman W H，1979.

［3］ 楊忠程，徐新黎，葉雙挺.基于組合拆分策略求解TSP的動(dòng)態(tài)規(guī)劃算法［J］.計(jì)算機(jī)工程，2012，13（38）：185－187.

YANG Zhong－cheng，XU Xin－li，YE Shuang－ting.Dynamic programming algorithm based on combination and Division Strategy for Solving TSP［J］.Computer Engineering，2012，13（38）：185－187.

［4］ 周康，強(qiáng)小利.求解TSP算法［J］.計(jì)算機(jī)工程與應(yīng)用，2007，43（29）：43－47.

Zhou Kang，Qiang Xiao－li，Tong Xiao－jun.Algorithm of TSP［J］.Computer Engineering and Applications，2007，43（29）：43－47.

［5］ Tang Q，Zeng J Y，Li H.A particle swarm optimization algorithm based on genetic selection strategy［M］.Springer Berlin Heidelberg：Advances in Neural Networks ISNN 2009，2009.

［6］ Gao S，Zhang Z Y，Cao C G.A novel ant colony genetic hybrid algorithm［J］.Journal of Software，2010，5（11）：1179－1186.

［7］ 馬良.旅行推銷員問(wèn)題的算法綜述［J］.數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2000，30（4）：156－165.

Ma Liang.Algorithmic review on the travelling salesman problem［J］.Mathematics in practice and theory，2000，30（4）：156－165.

［8］ Garey M R，Johnson D S，Tarjan R E.The planar Hamiltonian circuit problem is NP－complete［J］.SIAM Journal on Computing，1976，5（4）：704－714.

［9］ 朱林杰.基于TSP的遺傳算法優(yōu)化研究［D］.大連：大連理工大學(xué)，2007.

Zhu Lin－jie.The study of genetic algorithm optimization based on TSP［D］.Dalian：Dalian University of Technology，2007.

Solution to Traveling Salesman Problem Based on Neighborhood Search System

Ruan Shanna，Chen Junfeng，Gu Jing，Wang Sirui
（College of Internet of Things Engineering，Hohai University，Changzhou 213022，China）

Traveling salesman problem，as a classic mathematical optimization problem，with the extensive background of engineering application，promotes the development of the solution methods.For the connected characteristics of the optimal path of the traveling salesman problem，this paper puts forward two kinds of neighborhood search methods，i.e.the random search method in the neighborhood and probabilistic search method in the neighborhood，which improve the quality of the solutions.Among them，in order to speed up the search speed，loop inversion operator is used in the early process of the algorithm.The experimental results show that the algorithm has a good optimization performance when solving traveling salesman problem with small scale.Finally，the proposed algorithm is combined with the standard genetic algorithm and compared with the standard genetic algorithm.The experimental data shows that the combinational algorithm is better than the single optimization ones and improves the searching ability.

Traveling Salesman Problem；Neighborhood；Random search；Probabilistic search；Loop inversion；Optimal path

10.3969/j.issn.1002－2279.2015.06.012

TP301.6

A

1002－2279（2015）06－0044－03

國(guó)家自然科學(xué)基金（61403121）

阮?yuàn)櫮龋?990－），女，安徽省池州市人，碩士研究生，主研方向：智能信息處理。

2015－03－18