羅亦俊,劉小亮

(1.蘭州交通大學(xué) 交通運(yùn)輸學(xué)院，甘肅 蘭州 730070;2.西安科技大學(xué) 通信與信息工程學(xué)院，陜西 西安 710054)

作為網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)中的關(guān)鍵問題，最短路徑(Shortest Path ,SP)問題在求解通信網(wǎng)、交通網(wǎng)、電網(wǎng)以及項(xiàng)目運(yùn)籌網(wǎng)等網(wǎng)絡(luò)規(guī)劃和路徑?jīng)Q策中有著重要意義[1]。通常情況下，經(jīng)典的最短路徑問題僅僅考慮路徑的距離最短、時(shí)間最短或者費(fèi)用最少，屬于單目標(biāo)優(yōu)化，這就很難準(zhǔn)確描述實(shí)際網(wǎng)絡(luò)環(huán)境中的問題。在實(shí)際網(wǎng)絡(luò)優(yōu)化問題中的最短路徑問題經(jīng)常會(huì)和多目標(biāo)或多約束條件關(guān)聯(lián)到一起[2]。如通信網(wǎng)絡(luò)中的時(shí)延、分組掉包、帶寬、抖動(dòng)等約束條件，在多條件最短路徑問題中，往往并非某一條件的最優(yōu)解可以包攬這個(gè)多目標(biāo)條件的最優(yōu)解，因而針對(duì)某一目標(biāo)取得較優(yōu)解[3]。

作為網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)中的關(guān)鍵問題，最短路徑(Shortest Path ,SP)問題在求解通信網(wǎng)、交通網(wǎng)、電網(wǎng)以及項(xiàng)目運(yùn)籌網(wǎng)等網(wǎng)絡(luò)規(guī)劃和路徑?jīng)Q策中有著重要意義[1]。通常情況下，經(jīng)典的最短路徑問題僅僅考慮路徑的距離最短、時(shí)間最短或者費(fèi)用最少，屬于單目標(biāo)優(yōu)化，這就很難準(zhǔn)確描述實(shí)際網(wǎng)絡(luò)環(huán)境中的問題。在實(shí)際網(wǎng)絡(luò)優(yōu)化問題中的最短路徑問題經(jīng)常會(huì)和多目標(biāo)或多約束條件關(guān)聯(lián)到一起[2]。如通信網(wǎng)絡(luò)中的時(shí)延、分組掉包、帶寬、抖動(dòng)等約束條件，在多條件最短路徑問題中，往往并非某一條件的最優(yōu)解可以包攬這個(gè)多目標(biāo)條件的最優(yōu)解，因而針對(duì)某一目標(biāo)取得較優(yōu)解[3]。

基于上述幾點(diǎn)，本文提出一種基于禁忌搜索算法的改進(jìn)有向賦權(quán)網(wǎng)絡(luò)最短路徑的計(jì)算方法，此方法的目的是縮減計(jì)算有向賦權(quán)網(wǎng)絡(luò)最短路徑模型問題的時(shí)間和次數(shù)，提高計(jì)算效率。

1 有向賦權(quán)網(wǎng)絡(luò)最短路徑問題模型描述

本文基于現(xiàn)實(shí)通信和交通網(wǎng)絡(luò)基礎(chǔ)，構(gòu)建一個(gè)有向賦權(quán)網(wǎng)絡(luò)的最短路徑問題模型，該模型可以被描述成一個(gè)連通圖G=(V，E)。其中V(|V|=n)為結(jié)點(diǎn)集合，vi∈V是圖G的一個(gè)頂點(diǎn)，表示通信網(wǎng)絡(luò)中的路由器或者交通網(wǎng)絡(luò)中的道路交叉口等；在圖G=G(V，E)中，eij∈E是圖G中的一條邊，eij是vi到vj的一條道路或者一條鏈路。每條邊都賦有一個(gè)實(shí)數(shù)wij，表示實(shí)際網(wǎng)路中的距離，用鄰接矩陣distance存放圖G各結(jié)點(diǎn)對(duì)之間的特性，當(dāng)一個(gè)結(jié)點(diǎn)不能直接到達(dá)另一個(gè)結(jié)點(diǎn)時(shí)，將其wij設(shè)定為一個(gè)無窮大的數(shù)。從起點(diǎn)出發(fā)到達(dá)終點(diǎn)距離最短的那條路徑就為圖G的最短路徑。

1)鄰點(diǎn)

2)解的表示：給每一個(gè)頂點(diǎn)一個(gè)優(yōu)先權(quán)(不同的頂點(diǎn)權(quán)不同)。

3)頂點(diǎn)：v1，v2,…，vn。

4)優(yōu)先權(quán)：P(vi)=i，是指vi優(yōu)先權(quán)的值為i。令P(v1)=1，…,P(vn)=n。

5)鄰域搜索：隨機(jī)選擇若干頂點(diǎn)對(duì)，交換每對(duì)頂點(diǎn)的優(yōu)先權(quán)。

6)解碼：從原點(diǎn)開始，v1開始找到-(v)中優(yōu)先權(quán)最大的點(diǎn)v′，令v=v′，如此下去，直到v′=n(終點(diǎn))。

其中，從v1到vn節(jié)點(diǎn)的路徑Path1->n由路徑經(jīng)過的節(jié)點(diǎn)序列構(gòu)成：Path1->n=v1->vi->vj…vk->vn。

路徑的長度計(jì)算結(jié)果為Length1->n=w1,i(distance(1,i))+wi,j(distance(i,j))+…+wk,n(distance(k,n))。而該模型問題的最短路徑可以轉(zhuǎn)化成求Length1->n的最小值，即Min(Length1->n)=min(∑wij)。在該過程中，針對(duì)該模型與其他模型不同處是有向以及帶權(quán)值，其中權(quán)值的用法主要是對(duì)領(lǐng)域解的確定。

2 應(yīng)用TS算法求解設(shè)計(jì)思路

禁忌搜索(tabusearch TS)模擬人腦短期記憶功能，全局逐步尋找最優(yōu)解，為避免無效的循環(huán)計(jì)算，它使用禁忌準(zhǔn)則來實(shí)現(xiàn)。同時(shí)使用藐視準(zhǔn)則來接受較差解，用來確保對(duì)于不同范圍內(nèi)有效路徑的探測(cè)，在這方面禁忌搜索的局部搜索能力較強(qiáng)。

本文設(shè)計(jì)的有向賦權(quán)網(wǎng)絡(luò)問題的禁忌算法，首先設(shè)計(jì)一個(gè)合理的鄰接矩陣方法，根據(jù)起點(diǎn)獲取下一個(gè)可能到達(dá)的點(diǎn)的集合，然后在該集合中隨機(jī)取出其中一個(gè)有效點(diǎn)作為路徑達(dá)到的第二個(gè)點(diǎn)，依次循環(huán)獲取，直至達(dá)到終點(diǎn)位置結(jié)束，獲取的所有點(diǎn)的集合稱為初始解，然后計(jì)算其長度，再根據(jù)領(lǐng)域搜索原則，獲取領(lǐng)域解，據(jù)此獲取局部最優(yōu)解，最后加入到禁忌表中。當(dāng)整個(gè)運(yùn)算達(dá)到了某一規(guī)則后，停止搜索，根據(jù)禁忌表原則獲取其最短路徑。

該算法求解的設(shè)計(jì)思路主要包括以下6個(gè)部分。

1)領(lǐng)域：變換初始路徑中隨機(jī)選取點(diǎn)的優(yōu)先權(quán)，通過解碼原則獲取下一個(gè)點(diǎn)的位置，產(chǎn)生新的路徑集合稱為初始路徑領(lǐng)域。為更好地獲取有效領(lǐng)域路徑，本文采用了遞歸法，通過多次遞歸獲取領(lǐng)域路徑。

2)候選解集：初始路徑的鄰域子集。

3)禁忌表：用來存放禁忌對(duì)象的數(shù)據(jù)結(jié)構(gòu)。通常情況下，禁忌表中的對(duì)象是不能被選作產(chǎn)生鄰域的新解，這也是為了防止出現(xiàn)陷入局部最優(yōu)解和循環(huán)搜索的情況。

4)藐視準(zhǔn)則：如果候選解集中的最優(yōu)對(duì)象比以前歷史最優(yōu)解更優(yōu)時(shí)，就算該對(duì)象已經(jīng)被禁忌，但仍可以替代之前的最優(yōu)解，在下一次迭代過程作為初始解， 也就是特赦該禁忌對(duì)象。還有一種特赦情況是：如果候選解集中的全部對(duì)象都已經(jīng)被禁忌，那么特赦最優(yōu)候選解。

5)終止條件：如果算法已經(jīng)達(dá)到之前預(yù)設(shè)的迭代次數(shù)，或者在設(shè)置好的固定周期內(nèi)連續(xù)獲得的最優(yōu)解不發(fā)生變化，這兩種情況滿足其中一個(gè)就可以終止計(jì)算過程，將固定周期設(shè)置成算法總迭代次數(shù)的0.6倍。

3 算法的實(shí)現(xiàn)過程

本文提出的關(guān)于有向賦權(quán)網(wǎng)絡(luò)最短路徑問題模型的解決方法，其具體實(shí)現(xiàn)流程如圖1所示。

在搜索過程中，由于有向賦權(quán)網(wǎng)絡(luò)路徑是路徑固定的不可隨機(jī)抽點(diǎn)，在本文中，主要采用多次遞歸函數(shù)方法結(jié)合鄰接矩陣的特性獲取迭代初始解。通過計(jì)算迭代初始解的長度，并將迭代初始解的路徑編碼放入禁忌表中，然后根據(jù)權(quán)限值的大小選取該初始解的路徑領(lǐng)域解，選取出符合條件的領(lǐng)域解集后，對(duì)其領(lǐng)域解集進(jìn)行路徑長度計(jì)算，通過比較該領(lǐng)域解集與迭代初始解之間的路徑長度，確定下一輪迭代初始解和禁忌表是否添加和解禁。一次輪詢比較，直到終止條件得到滿足，結(jié)束此次計(jì)算。以上是本文設(shè)計(jì)實(shí)現(xiàn)思路。

初始解的確定設(shè)計(jì)：根據(jù)模型要求得到源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)的編碼，根據(jù)源點(diǎn)及上面的鄰接矩陣判斷與該源點(diǎn)連通的其他節(jié)點(diǎn)編碼，從中取出權(quán)值最大的點(diǎn)，依次類推獲取最后的目標(biāo)節(jié)點(diǎn)。

圖1 算法實(shí)現(xiàn)流程

評(píng)價(jià)函數(shù)的設(shè)計(jì)：分別計(jì)算每一次領(lǐng)域搜索后獲取的最短路徑編碼長度，判斷該路徑是否加入到禁忌表中，等待預(yù)設(shè)的迭代次數(shù)結(jié)束后，計(jì)算禁忌表中距離最短的路徑作為該有向拓?fù)渚W(wǎng)絡(luò)的最短路徑。

在本文設(shè)計(jì)中增加了一個(gè)條件函數(shù)用于處理同一禁忌長度和同一迭代次數(shù)，在不同領(lǐng)域路徑搜索數(shù)目下，計(jì)算出最短路徑編碼的出現(xiàn)率關(guān)系。每個(gè)領(lǐng)域路徑搜索數(shù)目的最短路徑編碼出現(xiàn)率計(jì)算方法如式(1)所示

(1)

式中：Wm為最短路徑出現(xiàn)率，C為運(yùn)行次數(shù)，tempCount為最短路徑出現(xiàn)次數(shù)。

終止條件的設(shè)計(jì)：算法達(dá)到預(yù)設(shè)的迭代次數(shù)，即可終止計(jì)算過程。

4 試驗(yàn)與結(jié)論

本文給定一個(gè)具體模型，其中包含的點(diǎn)數(shù)為20個(gè)，其有向賦權(quán)如圖2所示。

在上述的有向賦權(quán)圖中，圓圈中的標(biāo)號(hào)代表路徑編碼，同時(shí)也表示上一個(gè)節(jié)點(diǎn)到下一個(gè)節(jié)點(diǎn)的權(quán)值，而帶箭頭的線上的標(biāo)號(hào)表示兩點(diǎn)間的長度。

為解決該模型的問題，本文利用java語言在eclipse軟件工具中編程，完成1->20的最短路徑查找。

整個(gè)程序中采用的路徑編碼策略：采用可變長，將節(jié)點(diǎn)序號(hào)作為路徑的編碼方式，每條路徑都

圖2 有向賦權(quán)拓?fù)浣Y(jié)構(gòu)網(wǎng)絡(luò)

由起始節(jié)點(diǎn)1到目的節(jié)點(diǎn)號(hào)編碼串表示，其中所有編碼均采用List(鏈表結(jié)構(gòu))實(shí)現(xiàn)。編碼串所代表的路徑不能有重復(fù)節(jié)點(diǎn)，同時(shí)不允許出現(xiàn)無連接節(jié)點(diǎn)間的編碼關(guān)系。

禁忌算法參數(shù)設(shè)置：終止迭代次數(shù)=10，禁忌長度為1-19，領(lǐng)域解集大小分別取3、5、9，運(yùn)行次數(shù)=1 100；通過編寫運(yùn)行程序后發(fā)現(xiàn)其最短路徑為1->4->10->12->14->17->18->20；

長度為15，運(yùn)行1 100次出現(xiàn)該路徑的次數(shù)情況如圖3所示。

圖3 運(yùn)行結(jié)果

由圖3可以得知：上述模型所得的編碼路徑1->4->10->12->14->17->18->20為最短路徑的編碼串，其最短距離為15。

本文另外設(shè)計(jì)一個(gè)8個(gè)點(diǎn)的模型，根據(jù)以上算法的設(shè)計(jì)、實(shí)現(xiàn)以及運(yùn)行的結(jié)果，可充分證明本文提出的關(guān)于有向賦權(quán)網(wǎng)絡(luò)最短路徑問題的解決方法是有效的，同時(shí)，確定了一種對(duì)領(lǐng)域搜索數(shù)目的設(shè)置確定方法。

在后續(xù)的工作中，需要進(jìn)一步研究算法的時(shí)間復(fù)雜度，并對(duì)算法進(jìn)行改進(jìn)，引入其他優(yōu)秀的算法(比如遺傳算法)來減少其時(shí)間復(fù)雜度。

[1] 閻嘯天，武穆清.基于GA的網(wǎng)絡(luò)最短路徑多目標(biāo)優(yōu)化算法研究[J].控制與決策，2009,24(7):1104-1109.

[2] 郝光，張殿業(yè)，馮勛省.多目標(biāo)最短路徑模型及算法[J].西南交通大學(xué)學(xué)報(bào)，2007,42(5):641-646.

[3] 朱濤，張水平，郭戎蕭，等.改進(jìn)的加權(quán)復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要度評(píng)估的收縮方法[J].系統(tǒng)工程與電子技術(shù)，2009，31(8):1902-1905.

[4] 張帆，李軍，王鈞，等.多目標(biāo)最短路徑進(jìn)化求解方法[J].系統(tǒng)工程，2005,23(9):123-126.

[5] 康曉軍，王茂才.基于遺傳算法的最短路徑問題求解[J].計(jì)算機(jī)工程與應(yīng)用，2008,44(23):22-23.

[6] 冶曉隆，蘭巨龍，郭通．基于主成分分析禁忌搜索和決策樹分類的異常流量檢測(cè)方法[J]．計(jì)算機(jī)應(yīng)用，2013,33(10):2846-2850.

[7] 李進(jìn)，傅培華，李修琳，等.低碳環(huán)境下的車輛路徑問題及禁忌搜索算法研究[J].中國管理科學(xué)，2015,30(10):1003-207.

[8] 黃藝?yán)?Dijkstra 算法在室內(nèi)移動(dòng)導(dǎo)航最短路徑尋址的改進(jìn)[J].福建師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2017,33(5):1000-5277.

[9] 胡天寒，葉明全，張浩，等.基于禁忌搜索算法的特征選擇方法研究[J].2016,18(5):1673-1749.

[10] 梅海濤，王毅，華繼學(xué)．直覺模糊小生境的自適應(yīng)遺傳算法求解旅行商問題[J]．計(jì)算機(jī)科學(xué)，2016,43(11) :46-49．

[11] 張毅，梁艷春.基于選路優(yōu)化的改進(jìn)蟻群算法[J].計(jì)算機(jī)工程與應(yīng)用, 2007, 43(2):60-63.

[12] 鐘石泉,杜綱,賀國光.有時(shí)間窗的開放式車輛路徑問題及其遺傳算法[J].計(jì)算機(jī)工程與應(yīng)用,2006，34:201-2-4.

[13] 於世為,郭海湘,諸克軍.基于 GA-TS 的開放式車輛路徑優(yōu)化算法及應(yīng)用[J].系統(tǒng)管理學(xué)報(bào) ,2012，264-269.

[14] 李茂軍, 童調(diào)生.單親遺傳算法及其全局收斂性分析[J].自動(dòng)化學(xué)報(bào), 1999,25(1): 68-72.

[15] 李惠,蔣大奎.基于單親遺傳禁忌搜索算法的手術(shù)排程問題研究[J].計(jì)算機(jī)應(yīng)用研究,2013,699-702.