基于禁忌搜索算法的改進(jìn)最短路徑算法

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

【摘 要】目前的網(wǎng)絡(luò)已經(jīng)十分龐大而鏈路更易發(fā)生變化但Dijkstra算法仍存在著慢收斂問題，從而影響了路由器的性能。本課題通過(guò)建立禁忌搜索算法求解最短路徑優(yōu)化問題的數(shù)學(xué)模型框架和各利用禁忌搜索算法的基本框架，設(shè)定禁忌表的大小，控制算法最大迭代次數(shù)范圍并經(jīng)過(guò)多組數(shù)據(jù)測(cè)試并驗(yàn)證該算法。解決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ì)算機(jī)網(wǎng)絡(luò)的運(yùn)行質(zhì)量與路由的選擇方法密切相關(guān)。不同的信息傳輸要求可以選擇和采用不同的路由選擇方法。目前的網(wǎng)絡(luò)已經(jīng)十分龐大，并且以后發(fā)展的趨勢(shì)會(huì)越來(lái)越大，傳統(tǒng)的互聯(lián)網(wǎng)絡(luò)路由協(xié)議會(huì)顯得有些力不從心，因此使用禁忌搜索算法對(duì)路由（鏈路-狀態(tài)路由選擇算法（Link-State Routing，L-S））進(jìn)行優(yōu)化，有著十分重要的作用。禁忌搜索算法是人工智能的一種體現(xiàn)，是局部領(lǐng)域搜索的一種擴(kuò)展。禁忌搜索最重要的思想是標(biāo)記對(duì)應(yīng)已搜索的局部最優(yōu)解的一些對(duì)象，并在進(jìn)一步的迭代搜索中盡量避開這些對(duì)象，從而保證對(duì)不同的有效搜索途徑的探索。該算法優(yōu)化最短路徑算法不僅能夠優(yōu)化路由的選路方式和選路速度，還能對(duì)路徑上Qos進(jìn)行優(yōu)化，使網(wǎng)絡(luò)發(fā)揮到最大的性能。

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

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

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

輸出：G中從S到T的最短路徑的長(zhǎng)度。

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

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

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

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

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

2.1 初始化階段

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

2.2 搜索階段

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

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

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

3 算法驗(yàn)證

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

4 禁忌表的大小

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

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

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

6 測(cè)試方法

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

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

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

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

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

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

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

對(duì)最終解的影響圖

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

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

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

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

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

7 測(cè)試小結(jié)

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

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

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

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

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

8 總結(jié)

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

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

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

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

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

【參考文獻(xiàn)】

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

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

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

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

[5]歐雪雯.智能路由器：下一個(gè)超級(jí)入口[N].中國(guó)文化報(bào)，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òng)方向的禁忌搜索算法[D].大連理工大學(xué)，2009.

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

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

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

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

3 算法驗(yàn)證

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

4 禁忌表的大小

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

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

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

6 測(cè)試方法

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

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

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

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

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

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

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

對(duì)最終解的影響圖

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

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

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

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

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

7 測(cè)試小結(jié)

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

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

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

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

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

8 總結(jié)

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

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

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

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

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

【參考文獻(xiàn)】

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

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

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

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

[5]歐雪雯.智能路由器：下一個(gè)超級(jí)入口[N].中國(guó)文化報(bào)，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òng)方向的禁忌搜索算法[D].大連理工大學(xué)，2009.

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

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

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

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

3 算法驗(yàn)證

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

4 禁忌表的大小

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

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

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

6 測(cè)試方法

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

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

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

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

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

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

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

對(duì)最終解的影響圖

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

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

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

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

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

7 測(cè)試小結(jié)

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

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

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

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

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

8 總結(jié)

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

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

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

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

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

【參考文獻(xiàn)】

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

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

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

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

[5]歐雪雯.智能路由器：下一個(gè)超級(jí)入口[N].中國(guó)文化報(bào)，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òng)方向的禁忌搜索算法[D].大連理工大學(xué)，2009.

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

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

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

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