鄧 健

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

1 意義和目標(biāo)

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

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

2 算法理論分析

2.1 局部鄰域搜索

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

2.2 TS原理

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

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

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

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

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

2.2.3 禁忌表

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

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

3 算法設(shè)計(jì)

3.1 初始化

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

3.2 選擇和破禁

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

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

更新禁忌表；

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

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

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

更新當(dāng)前解； \跳出局部搜索

END

4 實(shí)驗(yàn)分析

4.1 相關(guān)工作簡介

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

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

4.2 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)的運(yùn)行環(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，其標(biāo)號代表的具體城市見文獻(xiàn)，初始距離為19 616.01。

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

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

表1 禁忌表變化

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

最優(yōu)路徑標(biāo)號：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)路徑為：

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

5 結(jié)語

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

[參考文獻(xiàn)]

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

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

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