求解最短路問題的改進(jìn)禁忌搜索算法

程　航，張　磊

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

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

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

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

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

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

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

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

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

.

(1)

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

2)模型約束

(2)

(3)

3　禁忌搜索算法求解

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

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

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

3.1.2鄰域解的變化

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

3.1.3評價(jià)函數(shù)

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

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

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

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

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

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

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

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

3.2　禁忌搜索算法步驟

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

3.3　算法流程圖

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

表1　算法步驟

圖1　改進(jìn)禁忌搜索算法的流程圖

4　算例分析

4.1　初始化

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

表2　問題初始化舉例

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

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

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

最優(yōu)解為80；

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

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

圖2　兩種算法比較

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

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

5　結(jié)　論

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

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

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

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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