余平

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

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

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A

1 引言（Introduction）

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

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

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

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

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

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

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

network）

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

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

Fig.1 Multilayer forward feedback

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

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

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

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

Fig.2 Back propagation training network

其中的凈值輸入：

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

=

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

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

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

圖3 邏輯函數(shù)

Fig.3 Logistic function

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

圖4 Heaviside函數(shù)

Fig.4 Heaviside function

5 學(xué)習(xí)速率（Learning rate）

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

6 問(wèn)題陳述（Statements）

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

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

Wij（k+1）=Wijk

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

Wij（k+1）=Wijk-α.xi，其中α是學(xué)習(xí)速率（因子）。

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

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

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

Rosenblatts算法如下：

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

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

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

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

Y=f（netj）=1 netj>0

=0 其他

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

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

Wi=Wi-α.xi

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

Wi=Wi+α.xi其中，α是學(xué)習(xí)因子。

（7）回到第（3）步。

7 結(jié)論（Conclusion）

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

參考文獻(xiàn)（References）

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

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

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

作者簡(jiǎn)介：

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