程　航，張　磊

(1.蘭州交通大學(xué) 交通運輸學(xué)院，甘肅 蘭州 730070；2.中國港灣工程有限責(zé)任公司，北京 100027)

禁忌搜索算法Tabu Search是一種成熟的智能優(yōu)化算法，該算法最初是一種局部搜索技術(shù)，算法原理為：通過模擬人類記憶能力，在搜索過程中防止陷入某一個最優(yōu)解，設(shè)計禁忌表將其禁忌，為防止迭代過程中將最優(yōu)解禁忌不能正常找到，故又加入了特赦規(guī)則，使得某些局部較優(yōu)的解在加入禁忌表之后，又能夠被“特赦”不至丟失，從而找到問題的全局最優(yōu)解。禁忌搜索算法在線性與非線性問題中大量使用，尤其是在問題規(guī)模較為龐大、傳統(tǒng)優(yōu)化方法不能在較短時間內(nèi)求得問題的最優(yōu)解，禁忌搜索算法的優(yōu)勢更加明顯。禁忌搜索算法有非常豐富的應(yīng)用場景，以其廣泛的適應(yīng)性在工程優(yōu)化問題中得到了大量使用。余麗等[1]，將禁忌搜索算法與遺傳算法相結(jié)合，求解旅行商路徑優(yōu)化問題，并通過實際案例和不同規(guī)模的網(wǎng)絡(luò)節(jié)點驗證得到很好的效果。李進等[2]，將車輛路徑問題使用禁忌搜索算法解決，該路徑算法結(jié)合了一種路徑編碼與WSS解碼算法，采用了3種鄰域搜索策略，對節(jié)能減排的路徑問題進行求解。宋曉宇等[3]，對解決Job Shop調(diào)度問題的禁忌搜索求解算法進行改進，主要體現(xiàn)在對鄰域解的構(gòu)造上，利用多點搜索，將搜索速度提到了新水平，最后將該算法應(yīng)用到benchmarks問題上，得到的結(jié)果都較為滿意。

最短路徑問題是圖論學(xué)中的經(jīng)典問題，其問題基本描述是從網(wǎng)絡(luò)中某一頂點出發(fā)，在網(wǎng)絡(luò)(或圖)中尋求一條路徑使得該點到達終點的路徑時間、距離或費用等加和最短(少)。最短路徑問題以其豐富的變化，在諸多方面得到了應(yīng)用，如城市網(wǎng)絡(luò)規(guī)劃、道路交通誘導(dǎo)系統(tǒng)、網(wǎng)絡(luò)節(jié)點路由、網(wǎng)絡(luò)布線、廠區(qū)選址等。曹旭等[4]，將旅游線路徑的優(yōu)化設(shè)計問題歸結(jié)為最短路問題，并使用Floyd算法進行求解，選擇甘肅及周邊旅游景點作為案例，求得了從任意景點出發(fā)到下一個任意景點的最短路徑。顏佑啟等[5]，將基于最短路的交通流分配方法與公路最大流結(jié)合，給出了基于最短路的最大流交通分配計算方法，從而確定更加合理的公路網(wǎng)各路段交通量。

本文在對最短路問題建模分析的基礎(chǔ)上，對最短路徑問題提出一種改進禁忌搜索算法，給出算法實現(xiàn)的關(guān)鍵步驟及流程，并用案例驗證提出的算法與傳統(tǒng)的Dijkstra，比較計算結(jié)果驗證該算法的可靠性。

1　網(wǎng)絡(luò)定義

網(wǎng)絡(luò)G(N,A)，其中N{n1，n2，…，nn}表示頂點集合，A{a1，a2，…，am}表示弧的集合。鄰接點表示為

2　最短路徑問題(Short-Path Problem)的數(shù)學(xué)模型

假設(shè)網(wǎng)絡(luò)G，若i，j為G中的兩個頂點，那么，i到j(luò)的最短路徑數(shù)學(xué)模型可表示為

1)目標(biāo)函數(shù)

.

(1)

式中：wij為頂點i到頂點j的權(quán)值，可表示時間、距離等；xij為最優(yōu)路徑是否經(jīng)過弧Aij。

2)模型約束

(2)

(3)

3　禁忌搜索算法求解

3.1　基于頂點優(yōu)先權(quán)的最短路徑關(guān)鍵設(shè)計[6～14]

3.1.1編碼及初始解的構(gòu)造

本文采用實數(shù)編碼方式，即給每個頂點一個優(yōu)先權(quán)值，不考慮唯一性，使用隨機數(shù)生成器Random()產(chǎn)生0～10的隨機數(shù)，得到優(yōu)先權(quán)數(shù)組weights，其中的weights(i)為頂點權(quán)重。從頂點1出發(fā)找到網(wǎng)絡(luò)中優(yōu)先權(quán)的最大頂點i*，將它加入到路徑中，重復(fù)若干次，直到最后一個頂點n加入。即得到1～n的一條路徑。

3.1.2鄰域解的變化

禁忌搜索算法的迭代過程就是不斷地從當(dāng)前解出發(fā)找到鄰域中的其他解，鄰域解的產(chǎn)生過程就是解的變化，也叫鄰域變化。本文考慮從路徑的頂點s出發(fā)，找到頂點優(yōu)先權(quán)最大且不在路徑中的頂點，加入路徑然后繼續(xù)搜索，直到找到頂點t，計算該路徑的總長度，同理再找到4條路徑，比較得出當(dāng)前最短路徑。鄰域解就是對換各個頂點的優(yōu)先權(quán)，然后重新搜索。

3.1.3評價函數(shù)

從前面的說明可以發(fā)現(xiàn)，當(dāng)一條路徑確定后，該路徑對應(yīng)的距離L就能確定，所以本文采用目標(biāo)函數(shù)為其評價函數(shù)。

3.1.4禁忌規(guī)則、禁忌長度、終止規(guī)則和特赦規(guī)則

1)禁忌對象：禁忌對象的選取有助于算法跳出局部最優(yōu)解，本文將2-opt中的解作為禁忌對象。

2)禁忌規(guī)則：當(dāng)某一個解z是N(z)當(dāng)前的局部最優(yōu)解(較優(yōu)解)時，首先判斷是否在禁忌表中。如果是，則選擇次優(yōu)解繼續(xù)判斷是否在禁忌表中；如果否，則將其作為本次迭代的局部最優(yōu)解，再將z禁忌加入到禁忌表中。

3)禁忌長度：禁忌長度就是被禁忌的對象不被允許選取的迭代步數(shù)。 本文取禁忌長度為一個常數(shù)，其值應(yīng)根據(jù)問題的規(guī)模大小而確定。

4)候選集合的確定：本文將從當(dāng)前解的鄰域中選擇頂點優(yōu)先權(quán)最大的若干個鄰居作為候選集合。

5)終止準(zhǔn)則：本文采用最大迭代步數(shù)作為算法的終止準(zhǔn)則。

6)特赦規(guī)則：在算法迭代產(chǎn)生解的同時，記錄該解的評價函數(shù)值和出現(xiàn)次數(shù)。當(dāng)某一個解較優(yōu)且優(yōu)于當(dāng)前問題的最優(yōu)解時，將其從禁忌表中特赦。

3.2　禁忌搜索算法步驟

禁忌搜索算法尋優(yōu)過程的實現(xiàn)得益于領(lǐng)域解的產(chǎn)生和候選解的選擇等一系列步驟，表1是對算法具體實施步驟及關(guān)鍵技術(shù)實現(xiàn)的詳細說明。

3.3　算法流程圖

改進的禁忌搜索算法求解最短路徑問題的關(guān)鍵：定義算法在何種情況下進行何種操作，如：算法在選擇到較優(yōu)解后應(yīng)該先判斷是否滿足禁忌規(guī)則，如果不滿足則將其作為候選解，并加入禁忌表；如果滿足則進行下一步判斷，看是否滿足特赦規(guī)則等。具體流程如圖1所示。

表1　算法步驟

圖1　改進禁忌搜索算法的流程圖

4　算例分析

4.1　初始化

本文以求解頂點數(shù)(規(guī)模)為30的網(wǎng)絡(luò)最短路問題為算例(即找到一條路徑，使得從頂點1到頂點30路徑距離最短)，其中網(wǎng)絡(luò)使用隨機數(shù)產(chǎn)生。隨機產(chǎn)生一個一維n列的向量weights作為頂點的優(yōu)先權(quán)值，表2是將設(shè)置問題的規(guī)模設(shè)為n=10，利用隨機發(fā)生器隨機產(chǎn)生網(wǎng)絡(luò)的不同邊權(quán)和頂點優(yōu)先權(quán)。那么，其具體初始化結(jié)果如表2所示。

表2　問題初始化舉例

4.2　實驗結(jié)果

本文使用C#語言編寫，并實現(xiàn)了該算法，分別采用本文提出的算法和Dijkstra算法進行求解，結(jié)果如下：

兩者均得到最優(yōu)路徑序列：12824252122232930；

最優(yōu)解為80；

改進禁忌搜索算法迭代到179次時，收斂到最優(yōu)解。

將兩種算法求解過程中，最優(yōu)解隨算法迭代時間長度的變化情況疊加，得到如圖2所示的結(jié)果?？梢园l(fā)現(xiàn)兩種算法都逐漸收斂到問題的最優(yōu)解，但傳統(tǒng)Dijkstra算法的收斂速度較慢，最優(yōu)解下落過程緩慢且初值較改進的禁忌搜索算法初值優(yōu)化程度較差。而改進后的禁忌搜索算法較傳統(tǒng)的Dijkstra算法，卻有初始解較優(yōu)、求解速度快等優(yōu)勢。

圖2　兩種算法比較

在對本算例使用兩種算法計算結(jié)束后，可清楚地得到問題最優(yōu)解、計算耗時等關(guān)鍵信息，具體如表3所示。

表3　計算結(jié)果對比

5　結(jié)　論

1)本文在對最短路問題簡單描述的基礎(chǔ)上，給出了問題的數(shù)學(xué)模型，基于頂點的優(yōu)先權(quán)，構(gòu)造初始解，進而優(yōu)先權(quán)構(gòu)造當(dāng)前最優(yōu)解的鄰域，設(shè)計一種求解最短路徑問題的禁忌搜索算法。

2)通過算例演算，上述計算結(jié)果表明，使用本文提出的改進禁忌搜索算法求解最短路問題的優(yōu)勢有兩方面：一是可以求得問題的全局最優(yōu)解(滿意解)，二是該算法收斂速度較迅速，計算效率高。由此，可以證明本文提出的改進禁忌搜索算法的優(yōu)化效果較好。

3)最短路徑問題目前被廣泛應(yīng)用到路徑導(dǎo)航、物流配送、交通誘導(dǎo)系統(tǒng)和無人駕駛等當(dāng)下熱點領(lǐng)域。仔細研究便會發(fā)現(xiàn)這些領(lǐng)域的研究要求時效性強，能夠快速的給出并反饋運輸方案結(jié)果[15-16]。本文對禁忌搜索算法的改進正是基于時間限制下要求快速求解這一要求提出的，通過不斷優(yōu)化算法參數(shù)(禁忌表長度、終止規(guī)則等)來降低算法求解的時間復(fù)雜度。

4)本文可以進一步研究的內(nèi)容：動態(tài)交通流分配[17]是目前交通運輸工程學(xué)科的熱點，也是較難解的問題。一般地，可以首先使用最短路徑算法求解出最短路徑、次短路徑、次次短路徑，然后通過懲罰系數(shù)的辦法將繞遠路加入到可行的分配路徑中，解決這類問題將是開展下一步研究方向。

參考文獻：

[1]余麗,陸鋒,楊林.交通網(wǎng)絡(luò)旅行商路徑優(yōu)化的遺傳禁忌搜索算法[J].測繪學(xué)報,2014,43(11):1197-1203.

[2]李佳,劉天琪,李興源，等.改進粒子群-禁忌搜索算法在多目標(biāo)無功優(yōu)化中的應(yīng)用[J].電力自動化設(shè)備,2014,34(8):71-77.

[3]宋曉宇,孟秋宏,曹陽.求解Job Shop調(diào)度問題的改進禁忌搜索算法[J].系統(tǒng)工程與電子技術(shù),2008(1):93-96.

[4]曹旭,張喆,馬少仙.最短路問題在旅游線路優(yōu)化中的應(yīng)用[J].科技廣場,2012(2):115-118.

[5]顏佑啟,歐陽建湘.最短路—最大流交通分配法[J].中國公路學(xué)報,2005(4):91-95.

[6]許谷聲， 陳逸群，王解先，等.結(jié)合交通信息的最佳路徑搜索[J].測繪工程,1999,8(4)：44-47.

[7]唐錢龍， 李央.基于多時段動態(tài)交通分配模型設(shè)計[J].交通科技與經(jīng)濟，2010,12(1)：18-20.

[8]俞晶菁.有限經(jīng)濟批量排產(chǎn)和運送問題的禁忌搜索算法[J].交通科技與經(jīng)濟，2012,14(1)：96-99.

[9]張健，張力鑫.帶軟時間窗車輛路徑問題及禁忌搜索算法[J].交通科技與經(jīng)濟，2010,12(6)：44-46.

[10] 李慶奎，呂志平，李昌貴.基于模糊理論的智能最優(yōu)路徑算法[J].測繪工程,2011，20(4):5-8.

[11] 邢文訓(xùn),謝金星.現(xiàn)代優(yōu)化計算方法[M].北京：清華大學(xué)出版社,1999.

[12] 賀一,劉光遠.禁忌搜索算法求解旅行商問題研究[J].西南師范大學(xué)學(xué)報,2002(3):41-45

[13] 彭茂.一種求解 TSP 問題的改進禁忌搜索算法[J].計算技術(shù)與自動化，2012(1):78-81.

[14] 王凌.智能優(yōu)化算法及其應(yīng)用[M].北京：清華大學(xué)出版社,2001.

[15] 李引珍,何瑞春,郭耀煌,等.多目標(biāo)網(wǎng)絡(luò)相異路徑的Pareto解及其遺傳算法[J].系統(tǒng)工程學(xué)報,2008,23(3):264-268.

[16] 何瑞春,李引珍.最佳相異度相異最短路徑的遺傳算法[J].蘭州交通大學(xué)學(xué)報,2005(3):116-119.

[17] 李引珍. 不確定環(huán)境下交通運輸網(wǎng)絡(luò)路徑求解方法及應(yīng)用研究[D].成都：西南交通大學(xué),2005.