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

,

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

1 引言

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

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

2 旅行商問題數(shù)學模型

旅行商問題是典型的組合優(yōu)化問題，該問題可以表述為:給定n個城市vi(i=1,2,…,n)，形成一個完全無向帶權(quá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。一個旅行商經(jīng)過所有的城市，每個城市經(jīng)過一次，且僅經(jīng)過一次，求出在所有可能的旅游路線中路線長度最短的一條。旅行商問題的數(shù)學模型為

(1)

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

3 流水算法原理

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

3.1 流水的啟示

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

圖1 流水的三維示意圖

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

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

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

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

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

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

3.2 流水算法的提出

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

圖2 流水算法簡單流程圖

(1)編碼

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

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

(2)初始化流水群

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

(3)流水局部搜索操作

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

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

(4)水漫溢出操作

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

(5)流水鑿洞操作

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

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

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

(6)蒸發(fā)-下雨操作

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

3.3 路徑選擇

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

(2)

3.4 水流量更新規(guī)則

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

(3)

(4)

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

4 數(shù)值試驗

本文運用標準TSP測試算例Eil51(該算例需要旅游51個城市，目前最優(yōu)結(jié)果為426)對算法性能進行評估。相關參數(shù)如下：水源群數(shù)量m=100；迭代總數(shù)NC_max=100；蒸發(fā)下雨比例rain=0.7；鑿洞概率系數(shù)cave=0.2；水流量權(quán)重系數(shù)α=4；能見度權(quán)重系數(shù)β=1；水流量揮發(fā)系數(shù)ρ=0.1。在MATLAB平臺進行20次仿真實驗，最優(yōu)結(jié)果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)。上述最優(yōu)結(jié)果所對應的整個旅行路線簡約、緊湊、高效，不存在交叉、過多折返現(xiàn)象，旅行方案非常好。并且，流水算法在求解算例Eil51時候呈現(xiàn)出非常好的收斂性，其每一代的最佳解的值和解群的平均值都能快速地遞減收斂，收斂的代數(shù)很小。

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

5 結(jié)論

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

[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] 戚玉濤,焦李成,劉芳.基于并行人工免疫算法的大規(guī)模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] 蔡榮英，王李進，吳超，等.一種求解旅行商問題的迭代改進蟻群優(yōu)化算法[J].山東大學學報(工學版),2012,42(1):6-11.

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

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