余平

摘 要：互聯(lián)網(wǎng)絡中尋找最優(yōu)路由是最廣泛研究的一個課題，如何找到兩個節(jié)點之間的最優(yōu)路徑卻一直是包交換互聯(lián)網(wǎng)絡中的一個難題。本文提出了一種基于神經(jīng)網(wǎng)絡技術(shù)尋找最優(yōu)路徑的方法，通過調(diào)整神經(jīng)元權(quán)值解決尋找最優(yōu)路徑問題，經(jīng)過反向傳播算法求解最優(yōu)路徑。通過運用本文算法測試表明，本文提出的算法計算簡單，收斂速度快，適合在以包交換作為路由算法獲得最優(yōu)路徑的研究中使用?？梢员M管目前已經(jīng)建立了最短路徑算法，技術(shù)人員仍然在不斷研究其他更優(yōu)的路徑選擇方法，神經(jīng)網(wǎng)絡技術(shù)正是其中可選方法之一。

關(guān)鍵詞：最短路徑；神經(jīng)網(wǎng)絡；多層前向反饋網(wǎng)絡（MLFN）；激活函數(shù)

中圖分類號：TP18 文獻標識碼：A

1 引言（Introduction）

現(xiàn)代通信網(wǎng)絡廣泛使用TCP/IP網(wǎng)絡體系結(jié)構(gòu)，在TCP/IP網(wǎng)絡體系結(jié)構(gòu)中，網(wǎng)際層是很重要的網(wǎng)絡層次，網(wǎng)際層的主要功能就是為數(shù)據(jù)包（網(wǎng)際層的數(shù)據(jù)信息單元）尋找路徑并轉(zhuǎn)發(fā)數(shù)據(jù)包，這個過程稱為路由選擇，路由選擇是網(wǎng)際層最重要的功能，特別是在包交換網(wǎng)絡中。路由選擇技術(shù)對網(wǎng)絡性能有很大的影響，最理想的路由算法就是為源節(jié)點與目標節(jié)點尋找最短路徑并高速轉(zhuǎn)發(fā)數(shù)據(jù)，并且能夠避免數(shù)據(jù)包的丟失。不過要尋找兩個節(jié)點之間的最短路徑是眾所周知的難題，目前廣泛研究的最短路徑算法都具有許多約束條件[1]。

在包交換網(wǎng)絡中，兩個主機之間的數(shù)據(jù)包通信一般通過如下方式：發(fā)送主機將數(shù)據(jù)組織成數(shù)據(jù)塊，一般稱為包，包中封裝有目標主機的網(wǎng)絡地址（一般稱為IP地址），網(wǎng)絡中的路由設(shè)備根據(jù)包中攜帶的目標地址為數(shù)據(jù)包尋找路徑并轉(zhuǎn)發(fā)，最終到達目標主機。一個路由策略的主要目標就是盡量減少IP數(shù)據(jù)包的傳輸延遲，盡最大可能傳輸數(shù)據(jù)包。影響數(shù)據(jù)包平均傳輸延遲時間的主要因素有網(wǎng)絡的可靠性以及網(wǎng)絡帶寬容量和網(wǎng)絡路由等因素的影響，其中路由對網(wǎng)絡性能影響非常重大。因此一個理想的路由算法[2]應該盡量在規(guī)定的時間內(nèi)找到最優(yōu)路徑來滿足網(wǎng)絡的服務質(zhì)量（QoS）。

目前的最短路徑搜索算法主要有：

（1）Bellman-Ford的動態(tài)規(guī)劃算法，這種算法主要用于求含負權(quán)值的單源點最短路徑算法。

（2）與Bellman算法類似的Dijkstra標記算法（也稱迪杰斯特拉算法），其按路徑長度遞增依次產(chǎn)生最短路徑。

當前在大多數(shù)的包交換網(wǎng)絡中，最短路徑計算都應用于網(wǎng)際層路由算法中，特別是網(wǎng)絡連接的鏈路具有權(quán)值，權(quán)值反映的是每條傳輸鏈路的傳輸代價，包括傳輸容量、網(wǎng)絡擁塞、傳輸狀態(tài)（如包隊列頭分組延遲以及網(wǎng)絡故障等）。最短路徑問題可以歸結(jié)為在源節(jié)點和目標節(jié)點之間尋找成本最小路徑問題，換句話說，最短路徑路由問題其實是在許多設(shè)計和規(guī)劃中都需要的經(jīng)典組合優(yōu)化問題，神經(jīng)網(wǎng)絡技術(shù)[3]就可以解決這個復雜的問題。

2 多層前向反饋網(wǎng)絡（MultiLayer forward feedback

network）

多層次網(wǎng)絡，顧名思義由多個功能層次組成的網(wǎng)絡，這種結(jié)構(gòu)的網(wǎng)絡，除了數(shù)據(jù)輸出層和數(shù)據(jù)輸入層意外，還包括隱藏層（或者隱藏單元），每個層次各司其職。多層前向反饋網(wǎng)絡是神經(jīng)網(wǎng)絡中一種典型的分層結(jié)構(gòu)，輸入層神經(jīng)元信息從輸入層進入隱藏層神經(jīng)元網(wǎng)絡后逐層向前傳遞直至輸出層，神經(jīng)元與神經(jīng)元之間的連接的權(quán)值稱為鏈接權(quán)值?，F(xiàn)代網(wǎng)絡一般都是分層次的結(jié)構(gòu)網(wǎng)絡，其中最著名的有ISO七層體系結(jié)構(gòu)與Internet實際使用的TCP/IP體系結(jié)構(gòu)，網(wǎng)絡的體系結(jié)構(gòu)都是分層次的，都是多層次的網(wǎng)絡結(jié)構(gòu)。通信網(wǎng)絡中的網(wǎng)絡節(jié)點對應神經(jīng)網(wǎng)絡的神經(jīng)元，節(jié)點與節(jié)點之間有鏈接鏈路，每條鏈路具有相應的鏈路權(quán)重，對應神經(jīng)元節(jié)點與輸出節(jié)點之間的鏈接鏈路也具有鏈接權(quán)重值，兩者之間關(guān)系如圖1所示。

圖1 多層前向反饋網(wǎng)圖

Fig.1 Multilayer forward feedback

3 反向傳輸網(wǎng)絡（Back propagation network）

反向傳輸是訓練多層人工神經(jīng)網(wǎng)絡的一種系統(tǒng)方法，它需要具有很好的數(shù)學基礎(chǔ)，并具有廣泛的應用潛力。

與生物神經(jīng)元類似，人工神經(jīng)元接收代表其他神經(jīng)元輸出的大量數(shù)據(jù)，每個輸入都乘以鏈路鏈接權(quán)值，類似于生物神經(jīng)中的突觸強度，匯總后的輸入加權(quán)值通過激活函數(shù)處理最后確定神經(jīng)元的輸出圖，如圖2所示。

圖2 反向傳輸多層訓練網(wǎng)圖

Fig.2 Back propagation training network

其中的凈值輸入：

考慮到線值，相應的神經(jīng)元輸入由下面的公式給出：

=

相應的輸出（激活值）使用非線性變換函數(shù)f給出。

4 激活函數(shù)（Activation function）

最后的數(shù)據(jù)輸出是通過稱為激活函數(shù)的非線性過濾函數(shù)產(chǎn)生的（有時稱為變換函數(shù)），常見的選擇是S函數(shù)或邏輯函數(shù)。如圖3所示，其中α是斜率參數(shù)，當函數(shù)的改變在兩個漸進值之間變化時，用于調(diào)整函數(shù)突發(fā)。

圖3 邏輯函數(shù)

Fig.3 Logistic function

多個激活函數(shù)稱為階躍函數(shù)，或Heaviside函數(shù)，如圖4所示。

圖4 Heaviside函數(shù)

Fig.4 Heaviside function

5 學習速率（Learning rate）

大多數(shù)網(wǎng)絡結(jié)構(gòu)在學習過程中都要對權(quán)值w和v進行調(diào)整。學習速率系數(shù)的選擇決定了權(quán)重調(diào)整的大小，從而影響每次迭代的收斂速度，差的系數(shù)選擇可能導致收斂失敗。如果學習速率系數(shù)過大，搜索路徑將發(fā)生振蕩，導致后面的收斂速度更慢。而如果系數(shù)過小，后面的過程將以很小的步驟進行，也會導致收斂速度減慢。

6 問題陳述（Statements）

考慮一個加權(quán)有向圖G=（V；E），V是有n個頂點的集合，E是一組有序的m條邊。固定成本Cij與圖G中頂點i到頂點j的邊相關(guān)聯(lián)。在運輸系統(tǒng)或機器人系統(tǒng)中，物理成本可能就是兩個頂點間的距離，從一個頂點到另一個頂點也需要時間和精力。在一個通信系統(tǒng)中，成本可以由傳輸時間，節(jié)點到節(jié)點間鏈路容量來確定。一般來說，成本系數(shù)矩陣【Cij】不一定是對稱的，比如，從頂點i到頂點j的成本不一定與從頂點j到頂點i的成本一樣。此外，一些頂點間的邊可能也不存在，也就是m可能小于n2（也就是m學習算法如下：

如果輸出是正確的，那就不用做權(quán)重調(diào)整了。

Wij（k+1）=Wijk

如果輸出是1，但是結(jié)果本來應該為0，那么在活動輸入鏈路中將降低權(quán)重值。

Wij（k+1）=Wijk-α.xi，其中α是學習速率（因子）。

如果輸出是0，但是結(jié)果本來應該為1，那么在活動輸入鏈路中將增加權(quán)重值。

Wij（k+1）=Wijk+α.xi

Wij（k+1）是調(diào)整后的權(quán)重值，而Wijk是調(diào)整前的權(quán)重值。

Rosenblatts算法如下：

（1）用（n+1）個輸入神經(jīng)元X0，X1，X2，…，Xn創(chuàng)建感知器，其中X=1是偏置輸入，O是輸出神經(jīng)元。

（2）初始化隨機權(quán)重W=（W0，W1…Wn）。

（3）遍歷訓練輸入模式X集合，使用權(quán)值為每個輸入模式j計算輸入加權(quán)后的總和。

（4）使用階梯函數(shù)計算輸出Y。

Y=f（netj）=1 netj>0

=0 其他

（5）對每個輸入模式j，用目標輸出Yj與計算得到的Yj進行比較，是否對所有的輸入模式都正確分類并都存在且輸出了權(quán)重值。

如果計算的輸出Yj是1，而結(jié)果本來為0，用下面給出的公式修改權(quán)值。

Wi=Wi-α.xi

如果計算的輸出Yj是0，而結(jié)果本來應該為1，就使用如下公式修改權(quán)值。

Wi=Wi+α.xi其中，α是學習因子。

（7）回到第（3）步。

7 結(jié)論（Conclusion）

神經(jīng)網(wǎng)絡被證明是優(yōu)化分組交換多層網(wǎng)絡的一種簡單方法，Rosenblatts算法的初步完成為優(yōu)化神經(jīng)網(wǎng)絡完成最短路徑奠定了基礎(chǔ)，經(jīng)過幾次迭代網(wǎng)絡可以得到優(yōu)化后的路由。

參考文獻（References）

[1] 孫俊逸，雷建鋒.基于神經(jīng)網(wǎng)絡下的最短路徑問題求解[J].中 國科技論文在線，1-7.

[2] 李望超.神經(jīng)網(wǎng)絡中的最短路徑問題[J].電子科學學刊，1996， S1期.

[3] 朱大銘，馬紹漢.神經(jīng)網(wǎng)絡求解圖最短路徑問題的一種新方法 [J].軟件學報，1996，A00：191-198.

作者簡介：

余 平（1969-），女，學士，副教授.研究領(lǐng)域：計算機網(wǎng)絡，網(wǎng) 絡安全.