基于TS的旅行商問題研究

鄧 健

（湖南科技學院 電子與信息工程學院，湖南 永州 425199）

1 意義和目標

在組合優(yōu)化算法上，禁忌算法在解決問題的效果上是比較優(yōu)秀的。當然，禁忌搜索（Tabu Search，TS）算法在很多方面都取得了巨大的成功，包括神經(jīng)網(wǎng)絡、電路設計、組合優(yōu)化、機器學習、生產(chǎn)調(diào)度等應用。另外，禁忌算法在調(diào)度問題中，其組合優(yōu)化問題至今仍是其應用最廣泛而成功的一個領域。TS具有相比遺傳算法（Genetic Algorithm，GA），模擬退火（Simulated Algorithm，SA）等優(yōu)化算法更強的局部搜索能力，但它對初始解具有較強的依賴性，近年來仍有許多有關TS算法的改進方法相繼提出，因而對基于TS的TSP問題的研究仍然有一定的意義。

本文利用啟發(fā)式信息求得一個較好的初始解，然后實現(xiàn)基本的TS算法，加深對TS算法的理解，并對其改進方向進行探討。

2 算法理論分析

2.1 局部鄰域搜索

局部搜索算法的提出，最基本的思想是在貪心算法的基礎上，采用爬山啟發(fā)式的思想。使用局部搜索算法解決問題，一般具有一個原始的解，從這個原始的解開始，可以把領域函數(shù)放到所謂的領域中進行不斷地查詢，直到查詢到比當前的解更好或更優(yōu)的解，那么就替換當前的解。這個過程是一個循環(huán)的過程，當要結束當下循環(huán)的時候，就以當下的解作為最后的解。由此可以看出，容易上手及容易推廣是局部搜索算法的最大的優(yōu)勢，而它最大的劣勢在于，求解的過程完全依賴于解的領域情況及其解的原始值，所以，一旦當領域情況失真或者原始的值出問題了，局部搜索算法為了實現(xiàn)獲得最終的解，必須采用TS的方式從而逃離局部最優(yōu)獲得全局的最優(yōu)解。

2.2 TS原理

TS的基本原理需要從幾個基本文字出發(fā)進行理解，這些基本文字主要是指：原始值、破禁算法、鄰域、禁忌表、選擇策略、候選解、適配值算法等。禁忌搜索方法是從一個問題的最上層的解決方案出發(fā)提出的，用什么樣的參數(shù)是由場景決定的。

2.2.1 初始解和適值函數(shù)的構造

初始解可以隨機給出，也可以事先使用其他啟發(fā)式等算法給出一個較好的初始解，由于禁忌搜索算法主要是基于鄰域搜索的，初始解的好壞對搜索的性能影響很大，所以應該采用啟發(fā)式信息或其他方法找出一個可行解作為初始解。本文中采用啟發(fā)式算法求得較好的初始解，即從第一個城市出發(fā)找與其距離最短的城市，然后繼續(xù)找與第二個城市距離最短的城市，依此尋找下去且滿足各城市只尋訪一遍，最終回到城市1。

2.2.2 鄰域函數(shù)和鄰域移動

鄰域移動是從一個解產(chǎn)生另一個解的途徑。它是保證產(chǎn)生好的解和算法搜索速度的最重要因素之一。鄰域移動定義的方法很多，適當?shù)囊苿右?guī)則的設計，是取得高效的搜索算法的關鍵，對于不同的問題應采用不同的定義方法。通過移動，目標函數(shù)值將產(chǎn)生變化，移動前后的目標函數(shù)值之差，稱之為移動值。在本文中使用的鄰域函數(shù)是交換兩個城市的位置得到交換后路徑長度，移動值是負的，則稱此移動為改進移動，否則稱作非改進移動。最好的移動不一定是改進移動，也可能是非改進移動，這一點就保證搜索陷入局部最優(yōu)時，禁忌搜索算法能自動把它跳出局部最優(yōu)。

2.2.3 禁忌表

禁忌表在記錄位置變化的方法上，一般來說，有3種形式：首先，狀態(tài)的基本參數(shù)和狀態(tài)的前后規(guī)律是需要記錄下來的；其次，位置的狀態(tài)分量及其狀態(tài)分量的變化也是需要記錄下來的；最后禁忌表中的最后終值也是需要記錄下來的。

禁忌表另一個作用是通過調(diào)整禁忌表的大小使搜索發(fā)散或收斂。初始搜索時，為提高解的分散性，擴大搜索區(qū)域，使搜索路徑多樣化，經(jīng)常希望禁忌表長度小。相反當搜索過程接近最優(yōu)解時，為提離解的集中性，減少分散，縮小搜索區(qū)域，這時通常希望禁忌表長度大。為達到這樣的目的，最近越來越多的人允許禁忌表的大小和結構隨搜索過程發(fā)生改變，即使用動態(tài)禁忌表，實驗結果表明了動態(tài)禁忌表往往比固定禁忌表能獲得更好的解。本文仍然使用長度固定不變的禁忌表。

3 算法設計

3.1 初始化

城市數(shù)量N，隨機給出一個初始解或者利用其他啟發(fā)式算法求得一個較好的初始解，本文利用后者，從距離矩陣左上角第一個城市出發(fā)選擇最短距離的城市，然后以該城市為出發(fā)點繼續(xù)尋找距離該城市最短的城市，直到所有城市都尋訪一遍后回到第一個城市，初始化禁忌表為空。

3.2 選擇和破禁

IF 候選解中最好解＞歷史最優(yōu)解

更新歷史最優(yōu)解和當前解；

更新禁忌表；

ELSEIF 候選解中最好解在禁忌表中且不滿足破禁函數(shù)

找不在禁忌表中的最優(yōu)解；

ELSE 不在禁忌表中且不滿足破禁函數(shù)

更新當前解； \跳出局部搜索

END

4 實驗分析

4.1 相關工作簡介

有學者提出C-TSP組合優(yōu)化問題，即我國31個省、市、自治區(qū)首府間的距離表和歸一化距離表后，國內(nèi)外學者對該問題進行了大量的研究。由于該問題屬于中大規(guī)模的組合優(yōu)化問題，因此，都用對該問題的解的情況來分析說明自己所提出的組合優(yōu)化方法的有效性，目前一些改進的算法求得的最優(yōu)解是15 404，以下列出幾種其他算法獲得的解以作對比：

（1）貪心算法最短巡回距離為17 102；（2）在Hopfield神經(jīng)網(wǎng)絡方法之上，加上三角形兩邊用一邊代替的約束條件，求得最短巡回距離為16 262；（3）幾何算法，最短巡回距離為15 492。

4.2 實驗結果

實驗的運行環(huán)境為:操作系統(tǒng)Windows XP，CPU為Intel（R）Pentium（R） 4 2.40 GHZ，1.00 GB內(nèi)存。

首先利用啟發(fā)式信息求得的初始解為：1→3→4→5→6→24→25→26→28→29→30→22→21→20→19→14→18→12→1 1→13→2→15→16→17→10→23→7→8→9→27→31→1，其標號代表的具體城市見文獻，初始距離為19 616.01。

其次對禁忌表長度和迭代次數(shù)兩參數(shù)的變化進行探討得到如表1所示的結果。

從表1中可以看出，當禁忌表長度不變時，一開始，隨著迭代次數(shù)的增加，最優(yōu)解有所改進，當?shù)螖?shù)達到某一值后，解就基本不變了，若繼續(xù)迭代下去解不變，這說明此時要么已經(jīng)達到最優(yōu)解，要么陷入了局部最優(yōu)而未能跳出局部鄰域。從表1中看出，當禁忌表的長度過短時，波動性較大，較難形成穩(wěn)定的最優(yōu)解，因而，開始時，隨著禁忌表的長度的增加可以改進解，但是到達一定值后過大則容易陷入局部最優(yōu)。

表1 禁忌表變化

通過上面的實驗深刻地體會到禁忌搜索算法對初始解的依賴性，禁忌表和迭代次數(shù)的調(diào)整都極為關鍵，本文算法最終獲得的最優(yōu)解值是15 497.54，顯然比以上所列的貪婪算法等要優(yōu)，最優(yōu)結果如下所示。

最優(yōu)路徑標號：1→6→24→23→25→26→27→31→28→3 0→29→22→21→20→19→18→14→15→16→13→2→11→12→17→5→4→10→3→7→8→9→1。

最優(yōu)路徑為：

北京→呼和浩特→銀川→西安→蘭州→西寧→烏魯木齊→拉薩→成都→昆明→貴陽→南寧→海口→廣州→長沙→武漢→南昌→福州→臺北→杭州→上海→南京→合肥→鄭州→太原→石家莊→濟南→天津→沈陽→長春→哈爾濱→北京。

5 結語

本文旨在理解基本禁忌搜索算法，在基本禁忌搜索算法上作了簡單的改進，利用啟發(fā)式信息得到一個較好的初始解，在候選解的產(chǎn)生上考慮到全部交換，對禁忌表長度和迭代次數(shù)的變化進行討論等，由于未作更大的改進，進而未能得到目前的最優(yōu)解，但是比傳統(tǒng)的一些基本算法要優(yōu)，后續(xù)工作筆者將對其進行改進，譬如利用啟發(fā)式信息獲得一個更好的初始解，利用更好的鄰域函數(shù)，限定迭代多少次解未得到改進便輸出等。另外，雖然禁忌搜索算法較為穩(wěn)定了，但是在面對大規(guī)模的數(shù)據(jù)集之下，運行效率低，這將是筆者下一步進行的研究工作。

[參考文獻]

[1]寧桂英，曹敦虔，周永權.求解TSP問題的離散型差分進化算法[J].計算機與數(shù)學工程，2017（11）：2136-2142.

[2]曹思聰，夏輝，孫可.基于蟻群算法的TSP問題分析[J].鞍山師范學院學報，2017（2）：49-53.

[3]汪定偉，王俊偉，王洪峰，等.智能優(yōu)化方法[M].北京：高等教育出版社，2008.