張健龍　林榮霞　邱恩超　莫浩明　余澤煌

【摘 要】目前的網(wǎng)絡(luò)已經(jīng)十分龐大而鏈路更易發(fā)生變化但Dijkstra算法仍存在著慢收斂問題，從而影響了路由器的性能。本課題通過建立禁忌搜索算法求解最短路徑優(yōu)化問題的數(shù)學(xué)模型框架和各利用禁忌搜索算法的基本框架，設(shè)定禁忌表的大小，控制算法最大迭代次數(shù)范圍并經(jīng)過多組數(shù)據(jù)測試并驗證該算法。解決Dijkstra算法最短路徑的優(yōu)化問題，符合現(xiàn)代人工智能路由器發(fā)展的趨向。

【關(guān)鍵詞】禁忌搜索算法；最短路徑優(yōu)化算法；智能路由；Dijkstra算法

Improvement The Shorest-Path Algorithm Based on Tabu Search

ZHANG Jian-long LIN Rong-xia QIU En-chao MO Hao-ming YU Ze-huang

（Huali College，Guangdong University of Technology， Guangzhou Guangdong 511325， China）

【Abstract】The network is very large and link are more likely to change but the Dijkstra algorithm is still slow convergence problem， which affects the performance of the router.This topic through the establishment of the tabu search algorithm to solve the optimization problem of shortest path model framework and the basic frame of the tabu search algorithm， set the size of the tabu list， control algorithm of maximum number of iterations and through multiple sets of data to test and verify the algorithm. Solve the problem of Dijkstra algorithm of shortest path optimization， conforms to the tendency of the development of modern artificial intelligence router.

【Key words】Tabu search； The shortest path algorithm； Intelligent routing； Dijkstras algorithm

0 引言

計算機(jī)網(wǎng)絡(luò)的運行質(zhì)量與路由的選擇方法密切相關(guān)。不同的信息傳輸要求可以選擇和采用不同的路由選擇方法。目前的網(wǎng)絡(luò)已經(jīng)十分龐大，并且以后發(fā)展的趨勢會越來越大，傳統(tǒng)的互聯(lián)網(wǎng)絡(luò)路由協(xié)議會顯得有些力不從心，因此使用禁忌搜索算法對路由（鏈路-狀態(tài)路由選擇算法（Link-State Routing，L-S））進(jìn)行優(yōu)化，有著十分重要的作用。禁忌搜索算法是人工智能的一種體現(xiàn)，是局部領(lǐng)域搜索的一種擴(kuò)展。禁忌搜索最重要的思想是標(biāo)記對應(yīng)已搜索的局部最優(yōu)解的一些對象，并在進(jìn)一步的迭代搜索中盡量避開這些對象，從而保證對不同的有效搜索途徑的探索。該算法優(yōu)化最短路徑算法不僅能夠優(yōu)化路由的選路方式和選路速度，還能對路徑上Qos進(jìn)行優(yōu)化，使網(wǎng)絡(luò)發(fā)揮到最大的性能。

1 禁忌搜索算法求解最短路徑優(yōu)化問題的數(shù)學(xué)模型框架

假設(shè)：已知整個網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和各鏈路的長度，求網(wǎng)絡(luò)中任意2個給定節(jié)點之間的最短通路。若將已知的各鏈路的長度改為路由時延或其他參數(shù)，例如，帶寬，經(jīng)過的節(jié)點數(shù)，平均通信量，平均隊列長度等因素及其給組合，就相當(dāng)于求任意2個節(jié)點之間且有最小時延或最小代價的通路。因此，求最短通路的算法且有普遍意義。

輸入：圖G=（B（G），E（G））有一個源頂點s和一個匯頂點t，以及對所有的邊ij∈E（G）的非負(fù)邊長Cij。

輸出：G中從S到T的最短路徑的長度。

第0步：從對每個頂點做臨時標(biāo)記L開始，做法如下：L（S）=0，且對除S外所有的頂點L（I）=∞。

第1 步：找?guī)в凶钚∨R時標(biāo)記的頂點（如果有結(jié)，隨機(jī)地取一個）。使該標(biāo)記變成永久標(biāo)記，即該標(biāo)記不再改變。

第2步：對每個沒有永久標(biāo)記但是又帶有永久標(biāo)記的頂點相鄰的頂點 j，按如下方計算一個新的臨時標(biāo)記：L（j）=Min{L（i）+Cij}，求最小是對所有帶有永久標(biāo)記的頂點 i做的。

第3步：判斷最新永久頂點y與最新臨時頂點x是否相等，如果相等則標(biāo)記此路徑為冗余路徑：H=Dis{L（y）-L（x）}。再判斷頂點y，x延伸節(jié)點集合里是否分別存在x，y頂點.如果是則將之刪除。重復(fù)第2步和第3步，直到所有的頂點都打上了永久標(biāo)記為止。

2 禁忌搜索算法的基本框架

2.1 初始化階段

步驟1：加載問題相關(guān)數(shù)據(jù)，初始化變量，生成初始解x0∈X（X為可行解空間），清空禁忌表，設(shè)計數(shù)器為0。

2.2 搜索階段

步驟1：搜索不在禁忌表內(nèi)或滿足藐視法則的鄰域移動x*∈N（x0）？奐X，其中f（x*）≤f（x），？坌x∈N（x0），而N（x0）是x0的所有鄰域解。

步驟2：更新禁忌表T及目前最優(yōu)解的記錄，執(zhí)行鄰域移動x0←x*。

步驟3：判斷是否已達(dá)到終止條件。如過達(dá)到，則終止搜索并輸出最優(yōu)解；否則，計數(shù)器記錄累加1并返回此階段步驟1繼續(xù)執(zhí)行。

3 算法驗證

在此驗證測試中，通過設(shè)置不同的算法參數(shù)，分別對10個例題重復(fù)進(jìn)行求解，將得出的結(jié)果進(jìn)行統(tǒng)計分析，以獲得算法最優(yōu)參數(shù)設(shè)置的方法。

4 禁忌表的大小

禁忌表的長度過小會導(dǎo)致搜索迂回進(jìn)行，從而陷入局部最優(yōu)的狀態(tài)；而禁忌表長度過長，則會對搜索進(jìn)行過度的限制，從而導(dǎo)致可能會錯過獲得最優(yōu)解的機(jī)會。將禁忌表的長度設(shè)置為0.5n至3n之間，并且將該區(qū)域平均分為5個區(qū)間，區(qū)間的界限為（0.5+2.5/4 x）n， （x∈[0，4]）取整的結(jié)果，其中n為頂點數(shù)目，x為禁忌表長度系數(shù)。

5 算法最大迭代次數(shù)

在此參數(shù)的測試中，我會先給一個較大的迭代次數(shù)作為迭代上限，如頂點數(shù)目在50個以下的實例中設(shè)置為2000，頂點數(shù)目大于50的時候設(shè)置為4000。然后在算法執(zhí)行的時候記錄各個實例達(dá)到最優(yōu)解的時候經(jīng)歷的迭代次數(shù)，這個迭代次數(shù)稱為最優(yōu)迭代值，以所有例題中最大的最優(yōu)迭代值作為推薦使用的算法最大迭代次數(shù)值。這個方法能夠精確地測出各個實例達(dá)到最優(yōu)解時所需的迭代次數(shù)。

6 測試方法

本次測試中，使用10個例題進(jìn)行，每一個實例均使用上述5種禁忌長度及3種初始解構(gòu)建方法進(jìn)行測試。同時為了獲得更加準(zhǔn)確的數(shù)據(jù)，上述測試會重復(fù)5次。因此，在本次測試中會產(chǎn)生10×5×3×5=750組數(shù)據(jù)。

利用測試所獲得的數(shù)據(jù)制作了“禁忌表長度與初始解生成算法的相互作用下對各個例題的影響程度圖”（圖1）。橫軸代表了禁忌長度系數(shù)；縱軸則表示了與例題已知最優(yōu)解偏離百分比。偏離百分比的計算公式是ε=（C-C*）/C*×100%。其中，C為算法計算出的路徑總距離，C*為問題已知的最優(yōu)解的總距離。

根據(jù)圖1制作了“禁忌表長度系數(shù)及初始解生成算法的相互作用下對最終解的影響圖”（圖2）。我把橫軸設(shè)為各個初始解生成算法，而縱軸依然表示了與例題已知最優(yōu)解偏離百分比，圖表中的各條折線，表示了在各個禁忌表長度系數(shù)下不同的初始解生成算法的變化。

圖2可以總結(jié)出，當(dāng)禁忌表長度系數(shù)為3（即禁忌表長度為頂點數(shù)目的2.375倍）時，并且使用任意內(nèi)接法作為初始解生成方法，所獲得的最終解與目前已知最優(yōu)解之間的平均偏離百分比是最低的（0.67%）。

當(dāng)兩個參數(shù)的組合達(dá)到較低的偏離百分比時，我們希望能通過最少的迭代次數(shù)來獲得較低的偏離百分比，所以，平均最低的最優(yōu)迭代值是各個例題的最優(yōu)參數(shù)的組合。

圖1 參數(shù)相互作用下對各個例題的影響程度圖

圖2 禁忌表長度系數(shù)及初始解生成算法的相互作用下

對最終解的影響圖

至于算法最大迭代次數(shù)的測試方法，我先對表1中的十個最短路徑問題按頂點數(shù)量分成兩組，分別為“頂點數(shù)目不大于50”及“頂點數(shù)目在50以上”。然后分別對兩組中各例題的最優(yōu)迭代值進(jìn)行比較，從中選出最大的最優(yōu)迭代值作為該組的算法最大迭代次數(shù)。測試的數(shù)據(jù)和各組的最優(yōu)迭代值在表1中。

表1 兩組頂點的最優(yōu)迭代值分析表

注：表中的數(shù)據(jù)是在禁忌表長度為3、使用任意內(nèi)接法生成初始解的情況下獲得的.

從表1中可以獲悉當(dāng)頂點數(shù)目不大于50時，用任意內(nèi)接法生成初始解，且禁忌表長度系數(shù)為3時，若要獲得質(zhì)量較佳的解算法所需的最大迭代次數(shù)至少為1306次；同樣道理，當(dāng)頂點數(shù)目大于50時，若要獲得質(zhì)量較佳的解算法所需的最大迭代次數(shù)至少為3590次。由此，我建議當(dāng)頂點數(shù)目不大于50時，算法最大迭代次數(shù)應(yīng)設(shè)為2000次；當(dāng)頂點數(shù)目大于50時，算法最大迭代次數(shù)應(yīng)設(shè)為4000次。

編譯環(huán)境及所描述的測試環(huán)境，均在同一臺機(jī)器上執(zhí)行。機(jī)器的硬件如下，處理器為Intel Core i7-2610UE Processor （1.5 GHz）、內(nèi)存4GB。值得一提的是，此程序在運行時，中央處理器并不是滿負(fù)載運行，故處理器的時鐘頻率不能用來計算程序執(zhí)行的時間及效率。

7 測試小結(jié)

雖然課題并未通過大規(guī)模的測試來獲得算法參數(shù)的精確設(shè)定方法，但通過前面幾個小節(jié)的測試和分析，可以總結(jié)出以下結(jié)論：

（1）參數(shù)的設(shè)置會因問題的實例不同而有所差異；

（2）總的來說，初始解的生成算法對最終解的質(zhì)量并無明顯的影響，但建議使用任意內(nèi)接法；

（3）禁忌表長度對最終解的質(zhì)量有明顯的影響，當(dāng)禁忌表長度系數(shù)為3（即禁忌表長度為頂點數(shù)目的2.375倍）時，所獲得的最終解的偏離值是最低的；

（4）當(dāng)頂點數(shù)目不大于50時，最大迭代次數(shù)設(shè)為2000；當(dāng)頂點數(shù)目大于50時，最大迭代次數(shù)應(yīng)設(shè)為4000。

8 總結(jié)

在實際應(yīng)用中，沒有一種算法對任何問題都是有效的，不同的算法有不同的適用領(lǐng)域，也有它不適合求解的問題類型。因此，算法的混合就成為了擴(kuò)展算法的適用范圍、提高算法的效率的有效途徑。針對本文的研究結(jié)果，以下幾點是在未來我研究的主要方向：

（1）在本文中的禁忌搜索算法主要使用了全鄰域搜索，所以當(dāng)頂點數(shù)目增加時，算法的搜索速度會變得較慢，在未來的研究，我會嘗試使用各種算法縮小鄰域的搜索范圍，以增加搜索速度。

（2）對算法加入多樣性和集中性策略，以加快跳出局部最優(yōu)的能力。

（3）將禁忌搜索算法與算法進(jìn)行混合，拓展算法的適用域，提高算法的性能。

以上幾點將會作為我對禁忌搜索算法的進(jìn)一步的研究，希望能在不久的將來，能把該算法改進(jìn)以更好地解決最短路徑優(yōu)化問題。

【參考文獻(xiàn)】

[1]鄧俊輝.數(shù)據(jù)結(jié)構(gòu)（C++語言版）[D].3版.清華大學(xué)，2013.

[2]M.HAlsuwaiyel.Algorithms Design Techniques and A nalysis（英文版）[M].電子工業(yè)出版社，2013.

[3]阮曉青，周義倉.數(shù)學(xué)建模引論[M].高等教育出版社，2007.

[4]趙鶴群，王鵬宇，李磊.禁忌搜索算法的參數(shù)選擇及其收斂特性分析[D].91550部隊，2013.

[5]歐雪雯.智能路由器：下一個超級入口[N].中國文化報，2013-8-13.

[6]關(guān)德新，王偉.一種用于鏈路狀態(tài)路由算法的新型數(shù)據(jù)結(jié)構(gòu)[D].北京航空航天大學(xué)，2002.

[7]陳文蘭，戴樹貴.旅行商題算法研究綜述[D].滁州學(xué)院，2006.

[8]Frank R.Giordano William P.Fox.A First Course in Mathematical Modeling[M].機(jī)械工業(yè)出版社，2009.

[9]Glover F. Tabu search： a tutorial[J]. Interfaces，1990（20）：74-94.

[10]Glover F. Tabu search： Part I[J]. ORSA Journal on Computing，1989（1）：190-206.

[11]Glover F. Tabu search： Part II[J]. ORSA Journal on Computing，1990（2）：4-32.

[12]郭娜，曹曉東.基于節(jié)約算法和移動方向的禁忌搜索算法[D].大連理工大學(xué)，2009.

[13]董宗然，周慧.禁忌搜索算法評述[J].軟件工程師，2010（2）：96-98.

[14]顏鶴.局部搜索算法的改進(jìn)及其應(yīng)用[D].上海大學(xué)，2004.

[15]鄭列，朱永松.數(shù)學(xué)模型[M].科學(xué)出版社，2013.

[責(zé)任編輯：湯靜]

3 算法驗證

在此驗證測試中，通過設(shè)置不同的算法參數(shù)，分別對10個例題重復(fù)進(jìn)行求解，將得出的結(jié)果進(jìn)行統(tǒng)計分析，以獲得算法最優(yōu)參數(shù)設(shè)置的方法。

4 禁忌表的大小

禁忌表的長度過小會導(dǎo)致搜索迂回進(jìn)行，從而陷入局部最優(yōu)的狀態(tài)；而禁忌表長度過長，則會對搜索進(jìn)行過度的限制，從而導(dǎo)致可能會錯過獲得最優(yōu)解的機(jī)會。將禁忌表的長度設(shè)置為0.5n至3n之間，并且將該區(qū)域平均分為5個區(qū)間，區(qū)間的界限為（0.5+2.5/4 x）n， （x∈[0，4]）取整的結(jié)果，其中n為頂點數(shù)目，x為禁忌表長度系數(shù)。

5 算法最大迭代次數(shù)

在此參數(shù)的測試中，我會先給一個較大的迭代次數(shù)作為迭代上限，如頂點數(shù)目在50個以下的實例中設(shè)置為2000，頂點數(shù)目大于50的時候設(shè)置為4000。然后在算法執(zhí)行的時候記錄各個實例達(dá)到最優(yōu)解的時候經(jīng)歷的迭代次數(shù)，這個迭代次數(shù)稱為最優(yōu)迭代值，以所有例題中最大的最優(yōu)迭代值作為推薦使用的算法最大迭代次數(shù)值。這個方法能夠精確地測出各個實例達(dá)到最優(yōu)解時所需的迭代次數(shù)。

6 測試方法

本次測試中，使用10個例題進(jìn)行，每一個實例均使用上述5種禁忌長度及3種初始解構(gòu)建方法進(jìn)行測試。同時為了獲得更加準(zhǔn)確的數(shù)據(jù)，上述測試會重復(fù)5次。因此，在本次測試中會產(chǎn)生10×5×3×5=750組數(shù)據(jù)。

利用測試所獲得的數(shù)據(jù)制作了“禁忌表長度與初始解生成算法的相互作用下對各個例題的影響程度圖”（圖1）。橫軸代表了禁忌長度系數(shù)；縱軸則表示了與例題已知最優(yōu)解偏離百分比。偏離百分比的計算公式是ε=（C-C*）/C*×100%。其中，C為算法計算出的路徑總距離，C*為問題已知的最優(yōu)解的總距離。

根據(jù)圖1制作了“禁忌表長度系數(shù)及初始解生成算法的相互作用下對最終解的影響圖”（圖2）。我把橫軸設(shè)為各個初始解生成算法，而縱軸依然表示了與例題已知最優(yōu)解偏離百分比，圖表中的各條折線，表示了在各個禁忌表長度系數(shù)下不同的初始解生成算法的變化。

圖2可以總結(jié)出，當(dāng)禁忌表長度系數(shù)為3（即禁忌表長度為頂點數(shù)目的2.375倍）時，并且使用任意內(nèi)接法作為初始解生成方法，所獲得的最終解與目前已知最優(yōu)解之間的平均偏離百分比是最低的（0.67%）。

當(dāng)兩個參數(shù)的組合達(dá)到較低的偏離百分比時，我們希望能通過最少的迭代次數(shù)來獲得較低的偏離百分比，所以，平均最低的最優(yōu)迭代值是各個例題的最優(yōu)參數(shù)的組合。

圖1 參數(shù)相互作用下對各個例題的影響程度圖

圖2 禁忌表長度系數(shù)及初始解生成算法的相互作用下

對最終解的影響圖

至于算法最大迭代次數(shù)的測試方法，我先對表1中的十個最短路徑問題按頂點數(shù)量分成兩組，分別為“頂點數(shù)目不大于50”及“頂點數(shù)目在50以上”。然后分別對兩組中各例題的最優(yōu)迭代值進(jìn)行比較，從中選出最大的最優(yōu)迭代值作為該組的算法最大迭代次數(shù)。測試的數(shù)據(jù)和各組的最優(yōu)迭代值在表1中。

表1 兩組頂點的最優(yōu)迭代值分析表

注：表中的數(shù)據(jù)是在禁忌表長度為3、使用任意內(nèi)接法生成初始解的情況下獲得的.

從表1中可以獲悉當(dāng)頂點數(shù)目不大于50時，用任意內(nèi)接法生成初始解，且禁忌表長度系數(shù)為3時，若要獲得質(zhì)量較佳的解算法所需的最大迭代次數(shù)至少為1306次；同樣道理，當(dāng)頂點數(shù)目大于50時，若要獲得質(zhì)量較佳的解算法所需的最大迭代次數(shù)至少為3590次。由此，我建議當(dāng)頂點數(shù)目不大于50時，算法最大迭代次數(shù)應(yīng)設(shè)為2000次；當(dāng)頂點數(shù)目大于50時，算法最大迭代次數(shù)應(yīng)設(shè)為4000次。

編譯環(huán)境及所描述的測試環(huán)境，均在同一臺機(jī)器上執(zhí)行。機(jī)器的硬件如下，處理器為Intel Core i7-2610UE Processor （1.5 GHz）、內(nèi)存4GB。值得一提的是，此程序在運行時，中央處理器并不是滿負(fù)載運行，故處理器的時鐘頻率不能用來計算程序執(zhí)行的時間及效率。

7 測試小結(jié)

雖然課題并未通過大規(guī)模的測試來獲得算法參數(shù)的精確設(shè)定方法，但通過前面幾個小節(jié)的測試和分析，可以總結(jié)出以下結(jié)論：

（1）參數(shù)的設(shè)置會因問題的實例不同而有所差異；

（2）總的來說，初始解的生成算法對最終解的質(zhì)量并無明顯的影響，但建議使用任意內(nèi)接法；

（3）禁忌表長度對最終解的質(zhì)量有明顯的影響，當(dāng)禁忌表長度系數(shù)為3（即禁忌表長度為頂點數(shù)目的2.375倍）時，所獲得的最終解的偏離值是最低的；

（4）當(dāng)頂點數(shù)目不大于50時，最大迭代次數(shù)設(shè)為2000；當(dāng)頂點數(shù)目大于50時，最大迭代次數(shù)應(yīng)設(shè)為4000。

8 總結(jié)

在實際應(yīng)用中，沒有一種算法對任何問題都是有效的，不同的算法有不同的適用領(lǐng)域，也有它不適合求解的問題類型。因此，算法的混合就成為了擴(kuò)展算法的適用范圍、提高算法的效率的有效途徑。針對本文的研究結(jié)果，以下幾點是在未來我研究的主要方向：

（1）在本文中的禁忌搜索算法主要使用了全鄰域搜索，所以當(dāng)頂點數(shù)目增加時，算法的搜索速度會變得較慢，在未來的研究，我會嘗試使用各種算法縮小鄰域的搜索范圍，以增加搜索速度。

（2）對算法加入多樣性和集中性策略，以加快跳出局部最優(yōu)的能力。

（3）將禁忌搜索算法與算法進(jìn)行混合，拓展算法的適用域，提高算法的性能。

以上幾點將會作為我對禁忌搜索算法的進(jìn)一步的研究，希望能在不久的將來，能把該算法改進(jìn)以更好地解決最短路徑優(yōu)化問題。

【參考文獻(xiàn)】

[1]鄧俊輝.數(shù)據(jù)結(jié)構(gòu)（C++語言版）[D].3版.清華大學(xué)，2013.

[2]M.HAlsuwaiyel.Algorithms Design Techniques and A nalysis（英文版）[M].電子工業(yè)出版社，2013.

[3]阮曉青，周義倉.數(shù)學(xué)建模引論[M].高等教育出版社，2007.

[4]趙鶴群，王鵬宇，李磊.禁忌搜索算法的參數(shù)選擇及其收斂特性分析[D].91550部隊，2013.

[5]歐雪雯.智能路由器：下一個超級入口[N].中國文化報，2013-8-13.

[6]關(guān)德新，王偉.一種用于鏈路狀態(tài)路由算法的新型數(shù)據(jù)結(jié)構(gòu)[D].北京航空航天大學(xué)，2002.

[7]陳文蘭，戴樹貴.旅行商題算法研究綜述[D].滁州學(xué)院，2006.

[8]Frank R.Giordano William P.Fox.A First Course in Mathematical Modeling[M].機(jī)械工業(yè)出版社，2009.

[9]Glover F. Tabu search： a tutorial[J]. Interfaces，1990（20）：74-94.

[10]Glover F. Tabu search： Part I[J]. ORSA Journal on Computing，1989（1）：190-206.

[11]Glover F. Tabu search： Part II[J]. ORSA Journal on Computing，1990（2）：4-32.

[12]郭娜，曹曉東.基于節(jié)約算法和移動方向的禁忌搜索算法[D].大連理工大學(xué)，2009.

[13]董宗然，周慧.禁忌搜索算法評述[J].軟件工程師，2010（2）：96-98.

[14]顏鶴.局部搜索算法的改進(jìn)及其應(yīng)用[D].上海大學(xué)，2004.

[15]鄭列，朱永松.數(shù)學(xué)模型[M].科學(xué)出版社，2013.

[責(zé)任編輯：湯靜]

3 算法驗證

在此驗證測試中，通過設(shè)置不同的算法參數(shù)，分別對10個例題重復(fù)進(jìn)行求解，將得出的結(jié)果進(jìn)行統(tǒng)計分析，以獲得算法最優(yōu)參數(shù)設(shè)置的方法。

4 禁忌表的大小

禁忌表的長度過小會導(dǎo)致搜索迂回進(jìn)行，從而陷入局部最優(yōu)的狀態(tài)；而禁忌表長度過長，則會對搜索進(jìn)行過度的限制，從而導(dǎo)致可能會錯過獲得最優(yōu)解的機(jī)會。將禁忌表的長度設(shè)置為0.5n至3n之間，并且將該區(qū)域平均分為5個區(qū)間，區(qū)間的界限為（0.5+2.5/4 x）n， （x∈[0，4]）取整的結(jié)果，其中n為頂點數(shù)目，x為禁忌表長度系數(shù)。

5 算法最大迭代次數(shù)

在此參數(shù)的測試中，我會先給一個較大的迭代次數(shù)作為迭代上限，如頂點數(shù)目在50個以下的實例中設(shè)置為2000，頂點數(shù)目大于50的時候設(shè)置為4000。然后在算法執(zhí)行的時候記錄各個實例達(dá)到最優(yōu)解的時候經(jīng)歷的迭代次數(shù)，這個迭代次數(shù)稱為最優(yōu)迭代值，以所有例題中最大的最優(yōu)迭代值作為推薦使用的算法最大迭代次數(shù)值。這個方法能夠精確地測出各個實例達(dá)到最優(yōu)解時所需的迭代次數(shù)。

6 測試方法

本次測試中，使用10個例題進(jìn)行，每一個實例均使用上述5種禁忌長度及3種初始解構(gòu)建方法進(jìn)行測試。同時為了獲得更加準(zhǔn)確的數(shù)據(jù)，上述測試會重復(fù)5次。因此，在本次測試中會產(chǎn)生10×5×3×5=750組數(shù)據(jù)。

利用測試所獲得的數(shù)據(jù)制作了“禁忌表長度與初始解生成算法的相互作用下對各個例題的影響程度圖”（圖1）。橫軸代表了禁忌長度系數(shù)；縱軸則表示了與例題已知最優(yōu)解偏離百分比。偏離百分比的計算公式是ε=（C-C*）/C*×100%。其中，C為算法計算出的路徑總距離，C*為問題已知的最優(yōu)解的總距離。

根據(jù)圖1制作了“禁忌表長度系數(shù)及初始解生成算法的相互作用下對最終解的影響圖”（圖2）。我把橫軸設(shè)為各個初始解生成算法，而縱軸依然表示了與例題已知最優(yōu)解偏離百分比，圖表中的各條折線，表示了在各個禁忌表長度系數(shù)下不同的初始解生成算法的變化。

圖2可以總結(jié)出，當(dāng)禁忌表長度系數(shù)為3（即禁忌表長度為頂點數(shù)目的2.375倍）時，并且使用任意內(nèi)接法作為初始解生成方法，所獲得的最終解與目前已知最優(yōu)解之間的平均偏離百分比是最低的（0.67%）。

當(dāng)兩個參數(shù)的組合達(dá)到較低的偏離百分比時，我們希望能通過最少的迭代次數(shù)來獲得較低的偏離百分比，所以，平均最低的最優(yōu)迭代值是各個例題的最優(yōu)參數(shù)的組合。

圖1 參數(shù)相互作用下對各個例題的影響程度圖

圖2 禁忌表長度系數(shù)及初始解生成算法的相互作用下

對最終解的影響圖

至于算法最大迭代次數(shù)的測試方法，我先對表1中的十個最短路徑問題按頂點數(shù)量分成兩組，分別為“頂點數(shù)目不大于50”及“頂點數(shù)目在50以上”。然后分別對兩組中各例題的最優(yōu)迭代值進(jìn)行比較，從中選出最大的最優(yōu)迭代值作為該組的算法最大迭代次數(shù)。測試的數(shù)據(jù)和各組的最優(yōu)迭代值在表1中。

表1 兩組頂點的最優(yōu)迭代值分析表

注：表中的數(shù)據(jù)是在禁忌表長度為3、使用任意內(nèi)接法生成初始解的情況下獲得的.

從表1中可以獲悉當(dāng)頂點數(shù)目不大于50時，用任意內(nèi)接法生成初始解，且禁忌表長度系數(shù)為3時，若要獲得質(zhì)量較佳的解算法所需的最大迭代次數(shù)至少為1306次；同樣道理，當(dāng)頂點數(shù)目大于50時，若要獲得質(zhì)量較佳的解算法所需的最大迭代次數(shù)至少為3590次。由此，我建議當(dāng)頂點數(shù)目不大于50時，算法最大迭代次數(shù)應(yīng)設(shè)為2000次；當(dāng)頂點數(shù)目大于50時，算法最大迭代次數(shù)應(yīng)設(shè)為4000次。

編譯環(huán)境及所描述的測試環(huán)境，均在同一臺機(jī)器上執(zhí)行。機(jī)器的硬件如下，處理器為Intel Core i7-2610UE Processor （1.5 GHz）、內(nèi)存4GB。值得一提的是，此程序在運行時，中央處理器并不是滿負(fù)載運行，故處理器的時鐘頻率不能用來計算程序執(zhí)行的時間及效率。

7 測試小結(jié)

雖然課題并未通過大規(guī)模的測試來獲得算法參數(shù)的精確設(shè)定方法，但通過前面幾個小節(jié)的測試和分析，可以總結(jié)出以下結(jié)論：

（1）參數(shù)的設(shè)置會因問題的實例不同而有所差異；

（2）總的來說，初始解的生成算法對最終解的質(zhì)量并無明顯的影響，但建議使用任意內(nèi)接法；

（3）禁忌表長度對最終解的質(zhì)量有明顯的影響，當(dāng)禁忌表長度系數(shù)為3（即禁忌表長度為頂點數(shù)目的2.375倍）時，所獲得的最終解的偏離值是最低的；

（4）當(dāng)頂點數(shù)目不大于50時，最大迭代次數(shù)設(shè)為2000；當(dāng)頂點數(shù)目大于50時，最大迭代次數(shù)應(yīng)設(shè)為4000。

8 總結(jié)

在實際應(yīng)用中，沒有一種算法對任何問題都是有效的，不同的算法有不同的適用領(lǐng)域，也有它不適合求解的問題類型。因此，算法的混合就成為了擴(kuò)展算法的適用范圍、提高算法的效率的有效途徑。針對本文的研究結(jié)果，以下幾點是在未來我研究的主要方向：

（1）在本文中的禁忌搜索算法主要使用了全鄰域搜索，所以當(dāng)頂點數(shù)目增加時，算法的搜索速度會變得較慢，在未來的研究，我會嘗試使用各種算法縮小鄰域的搜索范圍，以增加搜索速度。

（2）對算法加入多樣性和集中性策略，以加快跳出局部最優(yōu)的能力。

（3）將禁忌搜索算法與算法進(jìn)行混合，拓展算法的適用域，提高算法的性能。

以上幾點將會作為我對禁忌搜索算法的進(jìn)一步的研究，希望能在不久的將來，能把該算法改進(jìn)以更好地解決最短路徑優(yōu)化問題。

【參考文獻(xiàn)】

[1]鄧俊輝.數(shù)據(jù)結(jié)構(gòu)（C++語言版）[D].3版.清華大學(xué)，2013.

[2]M.HAlsuwaiyel.Algorithms Design Techniques and A nalysis（英文版）[M].電子工業(yè)出版社，2013.

[3]阮曉青，周義倉.數(shù)學(xué)建模引論[M].高等教育出版社，2007.

[4]趙鶴群，王鵬宇，李磊.禁忌搜索算法的參數(shù)選擇及其收斂特性分析[D].91550部隊，2013.

[5]歐雪雯.智能路由器：下一個超級入口[N].中國文化報，2013-8-13.

[6]關(guān)德新，王偉.一種用于鏈路狀態(tài)路由算法的新型數(shù)據(jù)結(jié)構(gòu)[D].北京航空航天大學(xué)，2002.

[7]陳文蘭，戴樹貴.旅行商題算法研究綜述[D].滁州學(xué)院，2006.

[8]Frank R.Giordano William P.Fox.A First Course in Mathematical Modeling[M].機(jī)械工業(yè)出版社，2009.

[9]Glover F. Tabu search： a tutorial[J]. Interfaces，1990（20）：74-94.

[10]Glover F. Tabu search： Part I[J]. ORSA Journal on Computing，1989（1）：190-206.

[11]Glover F. Tabu search： Part II[J]. ORSA Journal on Computing，1990（2）：4-32.

[12]郭娜，曹曉東.基于節(jié)約算法和移動方向的禁忌搜索算法[D].大連理工大學(xué)，2009.

[13]董宗然，周慧.禁忌搜索算法評述[J].軟件工程師，2010（2）：96-98.

[14]顏鶴.局部搜索算法的改進(jìn)及其應(yīng)用[D].上海大學(xué)，2004.

[15]鄭列，朱永松.數(shù)學(xué)模型[M].科學(xué)出版社，2013.

[責(zé)任編輯：湯靜]