,

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

1 引言

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

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

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

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

(1)

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

3 流水算法原理

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

3.1 流水的啟示

總啟示：“水無常形，水往低處流，水流千里歸大?！笔潜姸嗔魉謱?yōu)，求極值(地勢最小)的過程。如圖1所示，一個(gè)流水從初始位置A，流經(jīng)B、C、D等錨點(diǎn)位置(局部極小)最終到達(dá)最低點(diǎn)E(全局最小)。流水的位置與旅行商問題可行域具體解的編碼相互映射。

圖1 流水的三維示意圖

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

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

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

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

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

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

3.2 流水算法的提出

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

圖2 流水算法簡單流程圖

(1)編碼

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

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

(2)初始化流水群

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

(3)流水局部搜索操作

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

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

(4)水漫溢出操作

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

(5)流水鑿洞操作

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

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

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

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

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

3.3 路徑選擇

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

(2)

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

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

(3)

(4)

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

4 數(shù)值試驗(yàn)

本文運(yùn)用標(biāo)準(zhǔn)TSP測試算例Eil51(該算例需要旅游51個(gè)城市，目前最優(yōu)結(jié)果為426)對算法性能進(jìn)行評估。相關(guān)參數(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平臺進(jìn)行20次仿真實(shí)驗(yàn)，最優(yōu)結(jié)果val_best=428.9816471722069，非常接近426，其對應(yīng)的旅行方案為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é)果所對應(yīng)的整個(gè)旅行路線簡約、緊湊、高效，不存在交叉、過多折返現(xiàn)象，旅行方案非常好。并且，流水算法在求解算例Eil51時(shí)候呈現(xiàn)出非常好的收斂性，其每一代的最佳解的值和解群的平均值都能快速地遞減收斂，收斂的代數(shù)很小。

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

5 結(jié)論

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

[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].電子學(xué)報(bào)，2008,36(8):1552-1558.

[9] 唐立新.旅行商問題的改進(jìn)遺傳算法[J].東北大學(xué)學(xué)報(bào)，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].江西理工大學(xué)學(xué)報(bào),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ìn)，吳超，等.一種求解旅行商問題的迭代改進(jìn)蟻群優(yōu)化算法[J].山東大學(xué)學(xué)報(bào)(工學(xué)版),2012,42(1):6-11.

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

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