殷 星，魏 明

(1.武漢郵電科學(xué)研究院，湖北 武漢 430070；2.武漢烽火技術(shù)服務(wù)有限公司，湖北 武漢 430070)

0 引 言

最短路徑問題的研究在運(yùn)籌學(xué)、圖論和計(jì)算智能中起著重要的作用。當(dāng)前，國內(nèi)外深入研究最短路徑問題涵蓋通信網(wǎng)絡(luò)、物聯(lián)網(wǎng)、機(jī)器人和地理信息導(dǎo)航等領(lǐng)域，極其具有研究和應(yīng)用價(jià)值。早期研究最短路徑主要有經(jīng)典的Dijkstra算法、Floyd算法以及帶有啟發(fā)式搜索的A*算法，評價(jià)這些算法的優(yōu)劣主要是從算法占用的時(shí)間和空間復(fù)雜度兩個(gè)維度來衡量[1-3]。文獻(xiàn)[4]運(yùn)用改進(jìn)的Dijkstra算法，在光網(wǎng)絡(luò)中能夠求解指定必經(jīng)節(jié)點(diǎn)的最短路徑，但缺點(diǎn)是只適用于網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)較少的骨干網(wǎng)中。文獻(xiàn)[5]利用網(wǎng)絡(luò)分割法將復(fù)雜網(wǎng)絡(luò)分解成簡單網(wǎng)絡(luò)，基本思想是減小算法搜索范圍達(dá)到降低求解網(wǎng)絡(luò)規(guī)模的目的，雖能提高算法的運(yùn)行效率，但無法快速有效地找出分割點(diǎn)。文獻(xiàn)[6]在大規(guī)模網(wǎng)絡(luò)中針對多約束多目標(biāo)QoS路由問題提出一種遺傳算法解決機(jī)制，但該算法應(yīng)用范圍有一定的限制。研究最短路徑問題，人們試圖用傳統(tǒng)的經(jīng)典算法去求解，在時(shí)間上并不令人滿意。對于優(yōu)化PTN網(wǎng)絡(luò)中邏輯同路由問題的方法是要找出符合條件的最優(yōu)路徑，用這些最優(yōu)路徑來替換已經(jīng)發(fā)生邏輯同路由中的路徑，從而可以得出優(yōu)化方案。根據(jù)該問題優(yōu)化的思路，可以將該網(wǎng)絡(luò)優(yōu)化問題轉(zhuǎn)換為求解帶有多約束條件的最優(yōu)路徑問題。蟻群算法是一種優(yōu)化路徑的算法，具有很強(qiáng)的搜索最優(yōu)解的能力，但該算法在面對復(fù)雜的優(yōu)化問題時(shí)，容易陷入局部最優(yōu)解，導(dǎo)致優(yōu)化性能急劇下降[7]。

根據(jù)蟻群算法的優(yōu)缺點(diǎn)，設(shè)計(jì)一種改進(jìn)的蟻群算法來求解帶有多約束條件的最優(yōu)路徑問題。首先對該問題進(jìn)行數(shù)學(xué)建模，然后分析基本蟻群算法的原理，對該算法中的狀態(tài)轉(zhuǎn)移規(guī)則、啟發(fā)式函數(shù)和信息素更新規(guī)則進(jìn)行改進(jìn)并適當(dāng)調(diào)整其中的參數(shù)。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的蟻群算法在求解含多約束條件的最優(yōu)路徑問題時(shí)，加快了收斂速度，提高了搜索目標(biāo)的準(zhǔn)確度，并且通過算例驗(yàn)證了改進(jìn)蟻群算法的有效性。

1 數(shù)學(xué)模型

在PTN網(wǎng)絡(luò)優(yōu)化中，首先是尋找從源網(wǎng)元到宿網(wǎng)元之間的可達(dá)路由，在這基礎(chǔ)上需要滿足QoS約束條件，并且使得優(yōu)化的路徑質(zhì)量達(dá)到最優(yōu)，最終輸出優(yōu)化方案。QoS約束條件中的變量包括鏈路時(shí)延Delay、鏈路費(fèi)用Cost、鏈路承載業(yè)務(wù)數(shù)量Quantity、鏈路帶寬Band?？梢詫TN網(wǎng)絡(luò)中的路徑優(yōu)化問題轉(zhuǎn)換成圖論中帶約束的最優(yōu)路徑問題。設(shè)無向圖G=(V,E,W),其中頂點(diǎn)集V={v1,v2,…,vn}是圖中的所有頂點(diǎn)，代表網(wǎng)絡(luò)拓?fù)渲械乃芯W(wǎng)元節(jié)點(diǎn)，邊集E={(eu,v),u∈V,v∈Vandu≠v}是圖中頂點(diǎn)u到頂點(diǎn)v的所有邊，代表網(wǎng)絡(luò)拓?fù)渲芯W(wǎng)元之間的鏈路，權(quán)集W={(wu,v),u∈V,v∈Vandu≠v}表示圖中每條邊的權(quán)值，是一個(gè)四元組(Delay，Cost，Quantity，Band)，每條邊的初始權(quán)值計(jì)算公式為：

(1)

根據(jù)大量的工程經(jīng)驗(yàn)，權(quán)值影響因子a=0.3,b=0.3,c=0.2,d=0.2；為了方便描述，引入其他數(shù)學(xué)符號定義：

pod表示源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑，其中o,d分別表示圖G中的源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)；

tuv,Quv,Buv,Luv分別表示節(jié)點(diǎn)u到v的時(shí)延、業(yè)務(wù)數(shù)量、保證帶寬、鏈路；

|pod|, |Luv|分別表示源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑長度、路徑節(jié)點(diǎn)u到v的鏈路長度，|pod|=∪|Luv|；

p表示滿足多約束條件的路徑集合；

δ是每公里傳輸業(yè)務(wù)的費(fèi)用；

Tlimit,Climit,Qlimit,Blimit分別表示設(shè)置限制的總時(shí)延、路徑總費(fèi)用、鏈路承載業(yè)務(wù)數(shù)量、鏈路承載帶寬。

給出評價(jià)路徑質(zhì)量函數(shù)公式：

(2)

構(gòu)建多約束最短路徑目標(biāo)函數(shù)的數(shù)學(xué)模型為：

(3)

工程上，當(dāng)鏈路上的業(yè)務(wù)數(shù)量超過總承載業(yè)務(wù)數(shù)量、鏈路保證帶寬超過承載帶寬時(shí)，PTN網(wǎng)管將會(huì)顯示鏈路的告警信息，因此選取的路徑是要在滿足QoS約束的條件下，求解目標(biāo)函數(shù)的最優(yōu)解。

2 算法設(shè)計(jì)

蟻群算法是一種根據(jù)自然界中螞蟻覓食行為來求解組合優(yōu)化問題的算法[8]。通過科學(xué)觀察發(fā)現(xiàn)，自然界中的螞蟻總能發(fā)現(xiàn)一條從蟻巢到食物源的最短路徑，并且在尋找食物的過程中會(huì)釋放一種揮發(fā)性物質(zhì)，稱為信息素。其他螞蟻通過感知信息素的濃度來指導(dǎo)自己的運(yùn)動(dòng)方向，濃度越高，螞蟻向該方向移動(dòng)的概率就越大。因此，更多的螞蟻在該路徑上留下的信息素就越多，最終大部分的螞蟻都會(huì)經(jīng)過最優(yōu)的路徑。蟻群算法的核心主要是基于螞蟻狀態(tài)轉(zhuǎn)移規(guī)則和信息素更新規(guī)則，但蟻群算法具有收斂速度慢、容易陷入局部最優(yōu)解的缺陷[9]。為了提高蟻群算法的收斂速度和求解問題的正確率，在基本蟻群算法的基礎(chǔ)上，對螞蟻狀態(tài)轉(zhuǎn)移規(guī)則、啟發(fā)式函數(shù)和信息素更新規(guī)則進(jìn)行改進(jìn)。

2.1 螞蟻狀態(tài)轉(zhuǎn)移規(guī)則及啟發(fā)式函數(shù)的改進(jìn)

基本的蟻群算法狀態(tài)轉(zhuǎn)移公式[10]為：

(4)

其中，

(5)

基本蟻群算法中的啟發(fā)式函數(shù)，由于使用節(jié)點(diǎn)之間距離的倒數(shù)作為指導(dǎo)螞蟻運(yùn)動(dòng)的方向，導(dǎo)致螞蟻在搜索的過程中每一步都趨于單步最優(yōu)而偏離全局最優(yōu)方向[11]。針對這一問題，該文采用當(dāng)前節(jié)點(diǎn)走過的距離作為參考值對啟發(fā)函數(shù)進(jìn)行改進(jìn)，改進(jìn)的公式為：

(6)

其中，L(u)表示螞蟻在節(jié)點(diǎn)u所走過的距離，即使單步距離Luv很小，當(dāng)節(jié)點(diǎn)u走過的總路徑L(u)較大時(shí)，節(jié)點(diǎn)u到v的期望程度也不會(huì)很大，避免了螞蟻因貪圖一小步而偏離全局最優(yōu)解，使得螞蟻算法在搜索的過程中有了方向性指導(dǎo)，提升算法搜索最優(yōu)路徑的精確度。

為了進(jìn)一步提高螞蟻在搜索下一個(gè)節(jié)點(diǎn)時(shí)的效率，將圖G中初始權(quán)重wuv引入到狀態(tài)轉(zhuǎn)移規(guī)則中，使得在螞蟻搜索下一個(gè)節(jié)點(diǎn)的過程中不會(huì)盲目隨機(jī)地尋找路徑，縮短算法尋優(yōu)的收斂時(shí)間。改進(jìn)后的狀態(tài)轉(zhuǎn)移公式為：

(7)

其中，

(8)

其中，ε是初始權(quán)重的重視程度因子。根據(jù)螞蟻尋路的特性可知，螞蟻在前期幾輪迭代中隨機(jī)尋路的收斂時(shí)間較長，這與q0是固定的閾值有關(guān)，因此對q0采用一種動(dòng)態(tài)的調(diào)整策略，調(diào)整公式為：

(9)

其中，Nmax為最大迭代次數(shù)，Nc為當(dāng)前迭代次數(shù)。

2.2 信息素更新規(guī)則的改進(jìn)

基本蟻群算法信息素更新公式[12]為：

(10)

(11)

其中，H為信息素強(qiáng)度，是一個(gè)正的常數(shù)值。由于揮發(fā)系數(shù)ρ設(shè)置成一個(gè)固定的常數(shù)，對于螞蟻經(jīng)過的路徑揮發(fā)速度都相同，這不利于提升螞蟻搜索的效率，揮發(fā)系數(shù)設(shè)置不同，又會(huì)造成螞蟻對某些路徑有所偏好，也會(huì)影響螞蟻搜索最優(yōu)解的正確率[14]。因此，在設(shè)置不同的揮發(fā)系數(shù)時(shí)，需要弱化螞蟻對單步路徑的偏好，提高搜索效率。改進(jìn)的揮發(fā)系數(shù)公式為：

ρ(t+1)=

(12)

2.3 算法尋優(yōu)的步驟

改進(jìn)后求解多約束最優(yōu)路徑的蟻群算法步驟如下：

①設(shè)置蟻群算法中的基本參數(shù)和約束參數(shù)；

②根據(jù)網(wǎng)絡(luò)拓?fù)鋱D中各邊的權(quán)重初始化信息素；

③放置K個(gè)螞蟻在源節(jié)點(diǎn)，螞蟻通過狀態(tài)轉(zhuǎn)移規(guī)則和約束條件進(jìn)行選路，路徑信息素更新規(guī)則的選擇采用局部和全局更新相結(jié)合的方式，即偏向最大信息素一側(cè)采用全局更新，偏向最小信息素一側(cè)采用局部更新；

④當(dāng)螞蟻都到達(dá)目標(biāo)節(jié)點(diǎn)后，計(jì)算螞蟻經(jīng)過的路徑質(zhì)量；

⑤重復(fù)步驟④，直到K個(gè)螞蟻都完成尋路為止；

⑥判斷當(dāng)前迭代次數(shù)是否達(dá)到最大迭代次數(shù)，是則將滿足條件下的路徑質(zhì)量進(jìn)行排序，輸出路徑質(zhì)量最高的那條路徑作為求解PTN網(wǎng)絡(luò)中的最優(yōu)路徑；否則重復(fù)步驟③～⑤。

3 實(shí)驗(yàn)仿真及結(jié)果分析

3.1 仿真實(shí)驗(yàn)

該文利用可視化的網(wǎng)絡(luò)拓?fù)渖绍浖礼ephi，首先獲取網(wǎng)管中的各網(wǎng)元坐標(biāo)、網(wǎng)元名稱、光纖連接信息和鏈路的權(quán)重值，其次將獲得的數(shù)據(jù)轉(zhuǎn)成CSV文件，將CSV文件導(dǎo)入到Gephi的數(shù)據(jù)資料中，用網(wǎng)絡(luò)布局FR算法(Fruchterman-Reingold)生成300個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)拓?fù)?，如圖1所示。

圖1 網(wǎng)絡(luò)拓?fù)錈o向圖

在運(yùn)行算法之前，需要對算法中的各個(gè)參數(shù)進(jìn)行設(shè)置，詳細(xì)參數(shù)如表1所示。

表1 參數(shù)設(shè)置

實(shí)驗(yàn)1：在網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)n=300和最大迭代次數(shù)Nmax=100的情況下，基于生成的網(wǎng)絡(luò)拓?fù)鋱D，將圖中的所有節(jié)點(diǎn)依次按1～300進(jìn)行編號，選定不同的三組源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)，第一組源節(jié)點(diǎn)1和目標(biāo)節(jié)點(diǎn)50，第二組源節(jié)點(diǎn)66和目標(biāo)節(jié)點(diǎn)120，第三組源節(jié)點(diǎn)185和目標(biāo)節(jié)點(diǎn)268，三組分別運(yùn)行基本蟻群算法和改進(jìn)后的蟻群算法，比較兩者尋找到最優(yōu)解時(shí)的收斂時(shí)間(單位：秒)、迭代次數(shù)和滿足條件的路徑個(gè)數(shù)。實(shí)驗(yàn)得到的數(shù)據(jù)如表2所示。

表2 改進(jìn)前和改進(jìn)后的蟻群算法比較

改進(jìn)前和改進(jìn)后的蟻群算法尋優(yōu)迭代曲線如圖2所示，平均收斂時(shí)間曲線如圖3所示。

圖2 尋優(yōu)迭代曲線

圖3 平均收斂時(shí)間曲線

實(shí)驗(yàn)2：選定固定的源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)，逐漸增大網(wǎng)絡(luò)節(jié)點(diǎn)n的個(gè)數(shù)，比較蟻群算法、遺傳算法[15]和A*算法[16]達(dá)到最優(yōu)解時(shí)的運(yùn)行時(shí)間，實(shí)驗(yàn)數(shù)據(jù)如表3所示，實(shí)驗(yàn)結(jié)果如圖4所示。

表3 算法最優(yōu)解耗時(shí)比較

圖4 尋優(yōu)耗時(shí)曲線

3.2 結(jié)果分析

從實(shí)驗(yàn)1可以看出，相比較改進(jìn)前，改進(jìn)后的蟻群算法搜索效率有明顯的提升，平均收斂時(shí)間縮短了68.95%。從得到最優(yōu)解時(shí)的迭代次數(shù)上看，平均迭代次數(shù)減少了77.21%。從尋優(yōu)的準(zhǔn)確度上看，改進(jìn)前的蟻群算法搜索滿足約束條件的路徑個(gè)數(shù)不全，這說明基本蟻群算法在尋優(yōu)過程中很容易陷入局部最優(yōu)解；改進(jìn)后的蟻群算法提高了搜索的準(zhǔn)確度。

從實(shí)驗(yàn)2可以看出，隨著網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的增加，基本蟻群算法的收斂時(shí)間急速增長，遺傳算法和A*算法次之，改進(jìn)后的蟻群算法收斂時(shí)間增長較緩，這是因?yàn)楦倪M(jìn)后的蟻群算法中的基本參數(shù)提升了算法的尋優(yōu)速度，很好地克服了該算法的缺點(diǎn)。

4 結(jié)束語

關(guān)于優(yōu)化PTN網(wǎng)絡(luò)中存在的邏輯同路由問題，構(gòu)建出了含多約束條件的最優(yōu)路徑模型，并采用改進(jìn)的蟻群算法搜索出滿足QoS約束的最優(yōu)路徑，將最優(yōu)路徑作為解決邏輯同路由問題的優(yōu)化方案。通過改進(jìn)基本蟻群算法中的狀態(tài)轉(zhuǎn)移規(guī)則、啟發(fā)式函數(shù)和信息素更新規(guī)則，充分發(fā)揮出了算法較強(qiáng)的尋優(yōu)能力，同時(shí)又避免了該算法“早熟停滯”現(xiàn)象的發(fā)生，加快了算法的收斂速度。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的算法在運(yùn)行效率和尋優(yōu)效果上都有明顯提升。今后，隨著網(wǎng)絡(luò)規(guī)模數(shù)量的增加，運(yùn)行的時(shí)間復(fù)雜度也隨之增高，研究將大型PTN網(wǎng)絡(luò)進(jìn)行分區(qū)和并行化思路是一種有效的解決方法。簡單、易用的蟻群算法將在PTN網(wǎng)絡(luò)規(guī)劃和優(yōu)化中發(fā)揮重要的作用，同時(shí)，該算法為研究網(wǎng)絡(luò)最優(yōu)路徑問題提供一定的實(shí)用價(jià)值。