基于流水算法的旅行商問題求解

,

(1.天津商業大學 商學院，天津 300134； 2.天津商業大學 管理創新與評價研究中心，天津 300134)

1 引言

旅行商問題(Traveling Salesman Problem，簡稱TSP)又稱為旅行推銷員問題、貨郎擔問題，最早于1859年由威廉·漢密爾頓首次提出，屬于運籌學中經典的組合優化難題。該問題是單一旅行者由起點出發，不重復地走完其余地點并回到原出發點，在所有可能的路徑中求出路徑長度最短的一條。旅行商問題屬于組合優化范疇，是NP-hard問題，具有組合優化問題的典型特征，并且問題描述簡單，因此很多學者將旅行商問題算例作為算法研究的公共實例。同時，旅行商問題有著廣泛的實際應用背景，如物流配送、調度排班、道路交通、計算機網絡節點配置、生產調度、組合優化求極值等問題。所以，旅行商問題成為優化領域里的研究熱點，吸引了管理優化、運籌學、數學、物理、生物和人工智能等領域的研究者的關注。

TSP問題的解空間是多維、多局部極值、復雜的解空間。這個解空間類似一個無窮大的丘陵地帶，山峰、山谷連綿起伏，其中的山谷就代表局部極低值，最低的山谷代表最短路徑，對應的方案就是最佳旅行方案。旅行商問題的求解方法大體可以分為兩類：精確求解法和近似求解法。精確求解法主要是通過解析方法求得最優解，包括枚舉法、分枝定界法、動態規劃等。旅行商問題描述雖然非常簡單，但隨著需要訪問城市數目的增加，會出現所謂的“組合爆炸”現象，在多項式時間內無法精確求解。所以，人們提出了以獲得次優解為目標的近似啟發式求解算法。受到自然界的啟發，人們提出各種各樣的元啟發式算法(Meta-Heuristics)用于優化求解，如遺傳算法[1]、模擬退火[2]、禁忌搜索算法[3]、蟻群算法[4～6]、粒子群優化算法[7]等。這些智能算法被廣泛地應用于TSP問題求解，雖然不能保證獲取最優解，但當問題規模較大時，保證在可行時間內找到滿意的解。求解TSP問題的近似求解算法又可分為環路構造算法和環路改進算法兩類[8]。前者從某個非法解開始,通過某種增廣策略逐步改變該解，直到得到一個合法解為止，這類算法包括最近鄰算法、貪心算法、Clarke-Wright算法和Christofides算法等。環路改進算法則在給定初始的合法解后使用某種策略來改進初始解。這些策略更多的是元啟發式算法，包括遺傳算法[9～12]、模擬退火[13]、禁忌搜索算法[14]、蟻群算法[15,16]、粒子群優化算法[17,18]等。旅行商問題的本質是根據旅行商問題的解空間特征，研究局部最優解、全局最優解和鄰域結構之間的關系，具體包括：一種鄰域結構的局部最優解和另一種鄰域結構的局部最優解之間的關系；全局最優解和所有鄰域結構的局部最優解之間的關系。所以，提出一種更能協調上述關系的啟發式算法是組合優化領域學者長期追求的目標。

2 旅行商問題數學模型

旅行商問題是典型的組合優化問題，該問題可以表述為:給定n個城市vi(i=1,2,…,n)，形成一個完全無向帶權圖G=(V,E)；其中V(G)={v1,v2,…,vn}稱為圖G的城市集，E(G)={eij}(i,j∈(1,2,…,n),i≠j)稱為圖G的邊集，eij表示每兩個城市i和j之間的邊，并且已知邊eij的距離為dij。一個旅行商經過所有的城市，每個城市經過一次，且僅經過一次，求出在所有可能的旅游路線中路線長度最短的一條。旅行商問題的數學模型為

(1)

其中xij表示是否由城市i經過邊eij到城市j，如果是則賦值為1，否則為0。

3 流水算法原理

現代元啟發式算法成為近似求解大規模復雜的旅行商問題的研究熱點。研究者從生物系統的進化和大自然中自適應性現象得到靈感,提出了一些以搜索近優解為目標的仿生元啟發式算法，如遺傳算法、蟻群優化算法、粒子群優化算法等。仿生優化算法是一類模擬自然生物進化或者群體社會行為的隨機搜索方法的統稱。借鑒自然和社會的各種現象，提出并設計優化算法成為一個重要的求解途徑。本文正是在這樣的背景下，基于旅行商問題的解空間類似一個無窮大的丘陵地帶特點，受到自然現象“水無常形，水往低處流，水流千里歸大海”的啟發，設計新型的求解旅行商問題的元啟發式算法—流水算法。

3.1 流水的啟示

總啟示：“水無常形，水往低處流，水流千里歸大海”是眾多流水全局尋優，求極值(地勢最小)的過程。如圖1所示，一個流水從初始位置A，流經B、C、D等錨點位置(局部極小)最終到達最低點E(全局最小)。流水的位置與旅行商問題可行域具體解的編碼相互映射。

圖1 流水的三維示意圖

流水的具體啟示及分析如下：

(1)流水局部搜索啟示：“水無常形，水往低處流” 是一個流水根據地勢狀況局部搜索更低點，并向著下一個局部更低位置流動的過程，在這個過程中流水總是盡可能選擇并流經最短路徑到達最低點。并且，流水不可能倒著流動，具有禁忌搜索的特點。

(2)水漫溢出的啟示：當流水流到一個局部最低的位置，會出現停滯(如圖1中位置B)；但隨著水量增加，水位上升到一定高度，流水從一個局部次優的位置溢出，并由此繼續向下流動，跳出局部收斂。從優化算法的角度，流水的這種特點具有突破局部收斂的能力，即當流水若干代不變后，強行更換位置到局部次優的位置，從而繼續進行局部搜索。

(3)流水鑿洞的啟示：流水向著下一個更低、更好位置流動時，落差越大，流水沖擊慣性越大，就會對周圍的泥土或巖石進行磨損，甚至可以鑿洞突破當前位置的限制，向著比當前位置好的附近點流動(向著局部較優解方向搜索)，向著最低點流動(向著全局最優解方向搜索)。并且，在現實中往往可以通過人工鑿洞方式，讓水流到更低位置，并且路徑較短。從優化算法的角度，流水的這種特點具有突破局部收斂、向著全局最優解收斂的優點。

(4)蒸發-下雨的啟示：在自然界中，位置高、水量少的流水容易被蒸發掉形成水蒸氣；相應水蒸氣會在一定的氣候影響下隨機下雨，形成相對應數量的流水。從優化算法的角度，“蒸發”具有“優勝劣汰”優點；“下雨”具有多樣化群體，具備隨機全局尋優的優點。

(5)涓涓細流匯成江河的啟示：在自然界中涓涓流水總是匯集到更低更短的路徑上，集聚成江河，最后流歸到大海。從流量的角度解釋，只有更低、更短的路徑才能吸引更多的涓涓細流，使得這些更低更短路徑上的水量得到不斷的增加。流水的這一特征表現為很強的流量正反饋機制，引導流水在進行路徑選擇時，傾向流經水量大的路徑(具有位置更低、路徑更短的特征)，從而使得整個流水系統向最佳路徑的方向進化。

3.2 流水算法的提出

全局尋優、局部尋優和計算時間的矛盾一直是困惑旅行商問題求解的難題。本文借用大自然“水無常形，水往低處流，水流千里歸大海”的規律，設計新型的求解算法“流水算法”對旅行商問題進行尋優求解。流水算法簡單流程如圖2所示，具體設計和相關主要操作如下。

圖2 流水算法簡單流程圖

(1)編碼

在流水算法中，一個可行解可以用編碼表達，對應流水所流經的一個當前位置，具體的編碼形式因具體的優化問題而異。在求解旅行商問題中，編碼形式具體體現為旅行路線的所有城市排列順序，如圖3所示。

圖3 交換節點位置進行局部搜索示意圖

(2)初始化流水群

流水算法是群體并行協作尋優的算法機制，所以算法開始首先要初始化流水群。本文采用隨機式和啟發式兩種方式按照特定比例產生流水群，即旅行商問題的可行解群。隨機式是指沒有任何規則的隨機產生解群，可以保證初始解群的多樣性和隨機性；啟發式是指依據距離短規則和流量大規則啟引導產生解群(詳見3.3節)，保證初始解群一定程度的良好。

(3)流水局部搜索操作

流水局部搜索操作基本思想是在搜索過程中系統地改變鄰域結構集來拓展搜索范圍，獲得局部最優解。一個解在當前位置隨機按照一定方式搜索一定步長進行局部搜索，向著下一個更好位置流動；如果沒有更好位置則更新步長繼續搜索。并且，解不可能倒著搜索，具有禁忌搜索特點。如圖3所示，城市編碼的排序對應的就是一個解，其中每個排列位置上的編碼代表一個城市，如a、b。在具體的應用中，存在著許多種局部搜索方式，本文按照步長距離交換兩個節點位置進行局部搜索，例如圖3中，原始解中城市a與一個步長距離的城市b進行交換，形成一個新解。流水局部搜索操作的具體流程見圖4。

圖4 流水局部搜索及水漫溢出操作

(4)水漫溢出操作

水漫溢出操作是指一個解在當前位置搜索既定步長(設定的閾值)停滯后，強制移動到局部次優的位置，跳出局部收斂。在具體操作時候，水漫溢出操作往往結合局部搜索操作，如圖4所示。在這里必須明確局部次優位置具有以下特征：來自流水當前的鄰域，并且是流水先前沒有經過的，同時從這個次優位置能實現局部搜索尋找到更好的位置(即流水從這個位置能繼續向低處流動)。

(5)流水鑿洞操作

經過不斷搜索，流水群中優秀解往往可能處于局部優位置，這個位置很有可能非常接近全局最優解，這些優秀的流水在自己的位置停滯的時間很久，并且，水漫溢出操作很難實現跳出局部收斂。這時候，本算法采用流水鑿洞方式使得當前位置向著當前種群最優解方向搜索，表現為向著全局尋優，具體方式有很多種。本文采取流水鑿洞操作的措施是：優秀的流水在當前局部優位置向著當前種群最優解定向搜索若干步長，進行局部搜索。理論上，按照這種定向搜索，優秀的流水一定會搜索到比當前位置更好的解。流水鑿洞操作具有跳出局部停滯，向著全局最優解收斂的優點。

具體來說，對比原始解和全局最優解，尋找二者編碼有差異的位置，原始解通過自身交換方式，換成與全局最優解中同樣位置所對應的編碼，直至找到一個更優解(理論上一定可以尋找到)。如圖5所示，原始解中某位置城市編號是b，全局最優解中對應位置城市編號是c，通過自身交換讓原始解中對應位置城市編號是c，形成新的更換解。

圖5 交換節點位置進行鑿洞操作示意圖

(6)蒸發-下雨操作

蒸發-下雨操作具體包括兩個子操作，其中“蒸發”操作是按照一定比率蒸發(消除)解群中不好的解，具有“優勝劣汰”的優點；“下雨”操作隨機生成先前被蒸發數量的新的解，保證群體多樣化，具有隨機全局尋優的優點。下雨操作具體根據“涓涓細流匯成江河”流量正反饋機制進行路徑選擇(具體見3.3節)，引導整個解群系統向最佳路徑(最優解)的方向進化。

3.3 路徑選擇

每一個新的流水(無論是初始化階段的流水群，還是迭代過程中隨機下雨階段的流水)都使用逐步決策方法進行路徑選擇，建立問題的解；具體就是隨機選擇初始城市，然后按照概率依次選擇所要旅游的城市。假如在第t次迭代時，一個新的流水k處于城市i，選擇城市j作為下一站要旅游的城市的概率

(2)

3.4 水流量更新規則

模仿現實中流水的匯集和揮發原理，每次迭代完后，算法要對路徑上水流量實施更新。在第t次迭代過程中，流水k在進行一次巡游后，根據(3)式進行所經過路徑上水流量更新

(3)

(4)

其中Lk(t)是流水k在第t次迭代時巡游路線長度。

4 數值試驗

本文運用標準TSP測試算例Eil51(該算例需要旅游51個城市，目前最優結果為426)對算法性能進行評估。相關參數如下：水源群數量m=100；迭代總數NC_max=100；蒸發下雨比例rain=0.7；鑿洞概率系數cave=0.2；水流量權重系數α=4；能見度權重系數β=1；水流量揮發系數ρ=0.1。在MATLAB平臺進行20次仿真實驗，最優結果val_best=428.9816471722069，非常接近426，其對應的旅行方案為R=(44,17,37,15,45,33,39,10,49,5,38,11,32,1,22,2,16,50,9,30,34,21,29,20,35,36,3,28,31,8,26,7,43,24,23,48,6,27,51,46,12,47,4,18,14,25,13,41,40,19,42)。上述最優結果所對應的整個旅行路線簡約、緊湊、高效，不存在交叉、過多折返現象，旅行方案非常好。并且，流水算法在求解算例Eil51時候呈現出非常好的收斂性，其每一代的最佳解的值和解群的平均值都能快速地遞減收斂，收斂的代數很小。

與文獻[18]中的蟻群算法、遺傳算法、模擬退火方法、禁忌搜索方法、粒子群算法等經典元啟發式算法相同條件的運算結果進行比較，如表1所示。很明顯本文提出的流水算法遠優于經典的蟻群算法、遺傳算法、模擬退火方法、禁忌搜索方法，所求最優解非常接近實例Eil51目前已知的最優解，求解精度高，迭代收斂的代數要明顯少于上述算法，并且具有很好的收斂性。

5 結論

本文受自然現象“水無常形，水往低處流，水流千里歸大海”的啟發，設計新型的旅行商問題的元啟發式算法，即流水算法。新算法主要包括流水局部搜索、水漫溢出、流水鑿洞、蒸發-下雨4個算子，具有很強的全局搜索和局部搜索能力，同時具有禁忌搜索、正反饋機制、優勝劣汰、群體并行尋優等特點，并且兼有跳出局部收斂加速全局收斂的能力。通過求解經典的標準TSP測試算例Eil51，對比于其他元啟發式算法，該算法具有明顯的優勢，求解精度高、迭代次數少、收斂速度快，為高效率解決大規模組合優化問題提供了新的思路。本文提出的流水算法研究處于初期，還有許多問題值得研究，如算法的時間復雜度、空間復雜度、穩定度、收斂性、參數變化對尋優的影響及敏感性規律等。從以往經典元啟發式算法的研究和應用經驗可以推斷，這種模仿自然現象的流水算法具有廣闊的實際應用前景，如物流配送、旅游路線、道路交通、員工調度排班、生產調度、組合優化求極值等領域。所以，從應用的角度看，更多深入細致的工作還有待于進一步展開。并且，流水算法豐富了中國本土學者原創性元啟發式算法的研究，已經被相關領域的專家所關注。

[1] Holland J H. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence[M]. Ann Arbor, MI: University of Michigan Press, 1975.

[2] Kirkpatrick S, Gelatt C D, Vecchi M P. Optimization by simulated annealing[J]. Science, 1983, 220(4598): 671-680.

[3] Glover F. Future paths for integer programming and links to artificial intelligence[J]. Coputers and Operations Research, 1986, 13: 533-549.

[4] Colorni A, Dorigo M, Maniezzo V. Distributed optimization by ant colonies[A]. Processings of the First European Conference on Artificial Life[C]. Amsterdam: Elsevier, 1992. 134-142.

[5] Colorni A, Dorigo M, Maniezzo V. An investigation of some properties of an ant algorithm[A]. Processings of the Parallel Problem Solving from Nature Conference[C]. Amsterdam: Elsevier, 1992. 509-520.

[6] Dorigo M, Maniezzo V, Colorni A. Ant system: optimization by a colony of cooperating agents[J]. IEEE Transactions on System, Man, and Cybernetics Part-B: Cybernetics, 1996, 26(1): 29-41.

[7] Kennedy J, Eberhart R C. Particle swarm optimization[A]. Proceedings of the 1995 IEEE International Conference on Neural Networks[C]. Piscataway, New Jersey, 1995. 1942-1948.

[8] 戚玉濤,焦李成,劉芳.基于并行人工免疫算法的大規模TSP問題求解[J].電子學報，2008,36(8):1552-1558.

[9] 唐立新.旅行商問題的改進遺傳算法[J].東北大學學報，1999，20(1):40-42.

[10] Chang P C, Huang W S, Ting C J. Dynamic diversity control in genetic algorithm for mining unsearched solution space in TSP problems[J]. Expert Systems with Applications, 2010, 37(3): 1863-1878.

[11] Albayrak M, Allahverdi N. Development a new mutation operator to solve the traveling salesman problem by aid of genetic algorithms[J]. Expert Systems with Applications, 2011, 38: 1313-1320.

[12] Nagata Y, Soler D. A new genetic algorithm for the asymmetric traveling salesman problem[J]. Expert Systems with Applications, 2012, 39: 8947-8953.

[13] Geng X, Chen Z, Yang W. et al.. Solving the traveling salesman problem based on an adaptive simulated annealing algorithm with greedy search[J]. Applied Soft Computing, 2011, 11: 3680-3689.

[14] 劉于江，喻澤峰.一種求解旅行商問題的禁忌搜索算法[J].江西理工大學學報,2006,27(4):38-40.

[15] Manfrin M, Birattari M, Stützle T, et al.. Parallel ant colony optimization for the traveling salesman problem[J]. Lecture Notes in Computer Science, 2006, 4150: 224-234.

[16] 蔡榮英，王李進，吳超，等.一種求解旅行商問題的迭代改進蟻群優化算法[J].山東大學學報(工學版),2012,42(1):6-11.

[17] 郭崇慧,谷超，江賀.求解旅行商問題的一種改進粒子群算法[J].運籌與管理,2010,19(5):20-26.

[18] 沈繼紅,王侃.求解旅行商問題的混合粒子群優化算法[J].智能系統學報,2012,7(2):174-182.