羅亦俊,劉小亮
(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ì)算效率。
本文基于現(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)域解的確定。
禁忌搜索(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倍。
本文提出的關(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ì)算過程。
本文給定一個(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.