一種基于鄰域搜索機制的旅行商問題求解?

阮姍娜，陳俊風，顧 菁，王思睿

（河海大學物聯網工程學院，常州213022）

一種基于鄰域搜索機制的旅行商問題求解?

阮姍娜，陳俊風，顧 菁，王思睿

（河海大學物聯網工程學院，常州213022）

旅行商問題是一個經典的數學組合優化問題，其廣泛的工程應用背景促進了旅行商問題求解方法的快速發展。針對旅行商問題中最優路徑的連接特點，提出了兩種鄰域搜索方法：鄰域隨機性搜索法和鄰域概率性搜索法。這兩種鄰域搜索法對旅行商問題解的質量具有一定的提高能力，其中，為了加快搜索速度，在算法前期采用了循環倒置算子。實驗結果表明算法在求解小規模旅行商問題時具有良好的尋優性能。最后將該算法與標準遺傳算法結合，并進行了實驗結果對比。實驗數據顯示結合后的算法搜索性能優于單一的兩種優化算法，提高了算法搜索解的能力。

旅行商問題；鄰域；隨機搜索；概率搜索；循環倒置；最優路徑

1 引 言

旅行商問題（Traveling Salesman Problem，TSP）是組合優化［1］中一個易于描述但至今尚未徹底解決的古老而又困難的問題，是著名的NP－hard［2］問題。旅行商問題在工程上具有廣泛的實際應用背景，最早應用于校車路線的優化。目前旅行商問題已廣泛應用于電路板設計、城市規劃、交通運輸、物流配送等領域。因此，對旅行商問題進行研究具有重要意義，一直以來受到學者們的大量關注，是組合優化領域中的研究熱點。

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

2 TSP描述

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

TSP可描述為：推銷員打算到n個城市進行產品推銷，從其中一個城市出發，要求找到一條通過所有城市再回到起點的最短路徑，每座城市必須且只能訪問一次。

設n個城市集合為

城市之間的距離為

則上述問題轉化為如下優化問題：

其中kij為

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

3 鄰域搜索

通過對最優路徑圖研究后發現，依據總體路徑最短的特征，每個城市在離自己距離較近的多個城市內選擇合適的城市進行連接。并非所有城市都與自己的最近鄰城市連接。若所有城市選擇與最近鄰的城市相連，路徑很容易陷入局部最優。因此本文根據最優路徑各城市的這種連接特點，提出兩種新的鄰域搜索法，避免算法過早陷入局部最優。

3.1 鄰域范圍內隨機搜索

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

3.2 鄰域范圍內概率搜索

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

4 循環倒置算子

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

5 算法結構

根據以上描述，本文算法的基本結構如下：

（1）初始化：隨機生成N個個體，保持整體多樣性。設置最大進化迭代次數。

（2）算法前期：采用循環倒置算子，使群體較快收斂到最優值附近，實驗中前期的代數設為最大進化代數的1/5。

（3）算法中期：循環倒置算子和鄰域搜索法共同進行，增加尋優速度，提高尋優概率。實驗中中期的代數設為最大進化代數的2/5。

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

（5）終止條件：當達到最大迭代次數時算法停止，若沒有達到則返回到步驟（2）繼續迭代。

6 實驗結果與分析

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

表1 RSN和PSN在不同的n條件下得到的實驗結果

由表1可知，鄰域搜索法在n為2到6時都可尋到最優結果，但隨著鄰域個數的不同，得到的平均值不同，搜索到最優值的次數也不相同。對于隨機性鄰域搜索，當n＝5時尋優效果最佳；對于概率性鄰域搜索，當n＝4時尋優效果最佳，并且概率性鄰域搜索成功率高于隨機性搜索成功率。

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

結合后得出的實驗結果表2 不同n條件下RSN和PSN與SGA

由表2可知，鄰域隨機搜索比概率尋優效率高，但算法單獨運行時易陷入局部最優。針對不同的城市規模應設置不同的鄰域城市個數。該算法與SGA結合后在n＝5時尋到了最優解，提高了算法搜索效率，使得解的質量得到了相應提高。

觀察表1和表2可知，此算法對于小規模的TSP搜索效果較好。與其它算法融合提高了算法搜索性能，增強了尋優能力。但在實驗過程中總運行時間偏慢，因此該算法在運行速度上有待進一步加強。

7 結束語

基于鄰域搜索機制的旅行商問題求解主要是針對TSP中最優解的城市連接規則，在鄰域范圍內根據隨機尋優和鄰域范圍內概率尋優的方法來求解TSP，實驗結果說明其具有一定的尋優能力，并且與其它智能優化算法的結合有助于算法性能的提高，因此本文方法與其它算法的融合將是下一步值得繼續研究的方向。

［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的動態規劃算法［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］ 周康，強小利.求解TSP算法［J］.計算機工程與應用，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］ 馬良.旅行推銷員問題的算法綜述［J］.數學的實踐與認識，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的遺傳算法優化研究［D］.大連：大連理工大學，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

國家自然科學基金（61403121）

阮姍娜（1990－），女，安徽省池州市人，碩士研究生，主研方向：智能信息處理。

2015－03－18