陳曉琳

【摘 要】本文結(jié)合BP神經(jīng)算法特性，分析了BP神經(jīng)算法在解決QOS問題的可行性，并提出了解決該問題的有效算法模型，詳細(xì)說明了如何運(yùn)用該模型算法來解決QOS多播路由決策的問題。

【關(guān)鍵詞】神經(jīng)網(wǎng)絡(luò)；QOS路由；優(yōu)化算法

1 基于BP神經(jīng)網(wǎng)路優(yōu)化的可行性分析

由于BP神經(jīng)網(wǎng)絡(luò)是一個(gè)既向前傳播也能向后傳播的過程。它在多級網(wǎng)絡(luò)中，可以計(jì)算出隱藏層的任何神經(jīng)元的誤差。它利用最后輸出端的誤差計(jì)算出前一個(gè)神經(jīng)元輸出端的誤差，并再次利用這個(gè)誤差值估計(jì)出更前一層的誤差值。循環(huán)下來，就可獲得所有其他各層的誤差估計(jì)。這誤差估計(jì)雖然它本身的精度會(huì)在向后傳播的過程中不斷降低，但卻可以為多層網(wǎng)絡(luò)的訓(xùn)練提供有效算法。

BP神經(jīng)網(wǎng)絡(luò)作為一個(gè)有導(dǎo)師訓(xùn)練的網(wǎng)絡(luò)。在輸入一個(gè)向量時(shí)，也會(huì)被要求給出對應(yīng)的一個(gè)理想輸出向量，使網(wǎng)絡(luò)中出現(xiàn)異相聯(lián)的映射。也就是輸入向量與對應(yīng)的輸出向量之間構(gòu)成一個(gè)“訓(xùn)練對”。

根據(jù)以上的研究分析，我們可以得出采用有導(dǎo)師學(xué)習(xí)的訓(xùn)練方法，需進(jìn)行以下步驟：1）從訓(xùn)練的樣本集合中取一個(gè)樣本（Ai，Bi）；2）計(jì)算神經(jīng)網(wǎng)絡(luò)中的實(shí)際輸出O；3）求D=Bi-O；4）根據(jù)D調(diào)整權(quán)矩陣W；5）對每個(gè)樣本重復(fù)上述過程，直到對整個(gè)樣本集來說，誤差不超過規(guī)定范圍。

BP神經(jīng)網(wǎng)絡(luò)向前傳播訓(xùn)練方法：1）從樣本集中取一個(gè)樣本（XP，YP）；2）計(jì)算相應(yīng)的實(shí)際輸出OP；

在這個(gè)過程中，信息從輸入層經(jīng)過逐級的變換，傳送到輸出層。它是在網(wǎng)絡(luò)完成訓(xùn)練后正常執(zhí)行的過程，這個(gè)過程在網(wǎng)絡(luò)中執(zhí)行以下運(yùn)算：

OP=Fn（...F2（F1（XPW（1））W（2））...）W（n））

BP神經(jīng)網(wǎng)絡(luò)向后傳播階段訓(xùn)練方法[1]：1）計(jì)算實(shí)際輸出Op與相應(yīng)的理想輸出Yp的差；2）依照極小化誤差的方式來調(diào)整網(wǎng)絡(luò)的權(quán)矩陣。

以上兩個(gè)階段的訓(xùn)練方法都必須受到精度的控制，即：

Ep=■■（ypj-Opj）2

以上即作為網(wǎng)絡(luò)中關(guān)于第p個(gè)樣本的誤差測度。而將網(wǎng)絡(luò)關(guān)于整個(gè)樣本集的誤差測度定義為E=■Ep

值得注意的是，在開始調(diào)整神經(jīng)元的連接權(quán)時(shí)，得先求出輸出層的誤差，而其它層的誤差要通過此誤差反向逐層推算后才能得到。

那么在這里還要注意誤差傳播分析中輸出層權(quán)和隱藏層權(quán)的調(diào)整，下圖是ANP到ANq接：

圖1

ANP是輸出層的第q個(gè)神經(jīng)元，Wpq是從其前導(dǎo)層的第p個(gè)神經(jīng)元到ANq得聯(lián)接權(quán)。取wpq=wpq+Δwpq （1）

據(jù)Delta規(guī)則Wij（t+1）=W（t）+α（yi-aj（t））O（t） （2）

有Δwpq=αδvp （3）

那么在實(shí)際的路由問題中，我們就可以利用神經(jīng)網(wǎng)絡(luò)這種不斷調(diào)整其連接權(quán)值或閥值的過程來不斷的為我們每一個(gè)節(jié)點(diǎn)選擇其最優(yōu)的路由決定，并最終達(dá)到整個(gè)路徑或延時(shí)方面的最優(yōu)化。每一個(gè)節(jié)點(diǎn)中的神經(jīng)元會(huì)根據(jù)每一次反饋過來的信息進(jìn)行下一步選擇。但由于每個(gè)節(jié)點(diǎn)同時(shí)存在很多不同的相連的路徑，那么數(shù)據(jù)會(huì)通過各個(gè)不同路徑先向前傳播，然后根據(jù)最終到達(dá)目的節(jié)點(diǎn)的信息反饋到源節(jié)點(diǎn)，供其參考，最后選擇最終合適的路徑。

2 QOS路由優(yōu)化算法的實(shí)現(xiàn)

被調(diào)整后的神經(jīng)網(wǎng)絡(luò)連接權(quán)值，可以使任意一個(gè)輸入都可在網(wǎng)絡(luò)對中得到最佳的的輸出或者結(jié)果，這也是BP神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)的最終目的。正向傳播和反向傳播構(gòu)成了BP神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)過程。正向傳播按照字面意思，就肯定是向前傳遞網(wǎng)絡(luò)信息，并針對某一輸入值得到相應(yīng)輸出結(jié)果；而反向傳播既是向后一層一層的傳遞誤差值，不斷地向后反饋信息，調(diào)整每個(gè)神經(jīng)元之間的的連接權(quán)值，使網(wǎng)絡(luò)在得到不同的輸入信息后都能經(jīng)過正確的計(jì)算得到最佳的輸出結(jié)果，并且誤差得保持在一定的范圍之內(nèi)。

BP神經(jīng)算法的學(xué)習(xí)方法是對需要得到訓(xùn)練的樣本進(jìn)行針對網(wǎng)絡(luò)權(quán)值的調(diào)整的訓(xùn)練。每組都由相應(yīng)的輸入以及希望得到的輸出這兩個(gè)結(jié)構(gòu)的組成。在向前傳播的過程中，將需要得到訓(xùn)練的樣本輸入，通過每一個(gè)神經(jīng)元進(jìn)行處理，并最終到達(dá)輸出。在這整個(gè)過程中，上一級的神經(jīng)元就會(huì)影響到下一級的神經(jīng)元，如果通過層層傳播，最終得到的結(jié)果不是期望的結(jié)果，就會(huì)進(jìn)行下一步，向后傳播。

向后傳播則是將誤差信號依照原來的方式向后傳播，傳播的過程中根據(jù)一定的規(guī)則對每個(gè)節(jié)點(diǎn)的權(quán)重閥值進(jìn)行更改，這個(gè)過程直到到達(dá)最開始的神經(jīng)元才停止，轉(zhuǎn)而開始上面的步驟，向前傳播。這個(gè)過程循環(huán)往復(fù)下去，直至最終的輸出結(jié)果達(dá)到期望的要求，那么這個(gè)時(shí)候算法的學(xué)習(xí)才算完畢，否則，繼續(xù)往復(fù)下去。

學(xué)習(xí)過程的循環(huán)往復(fù)，最終到整個(gè)神經(jīng)網(wǎng)絡(luò)得到理想的結(jié)果為止。在這里需要注意的是，神經(jīng)網(wǎng)絡(luò)在進(jìn)行訓(xùn)練的實(shí)際過程中，是只有向前傳播而沒有向后傳播的。

具體步驟如下：在此次學(xué)習(xí)算法中，只考慮QOS路由的最小跳轉(zhuǎn)數(shù)，根據(jù)BP神經(jīng)網(wǎng)絡(luò)模型的相關(guān)理論，本文首先建立一個(gè)反饋式神經(jīng)網(wǎng)絡(luò)路由分配計(jì)算機(jī)結(jié)構(gòu)。

定義反饋函數(shù)R，它表示反向傳播中對神經(jīng)網(wǎng)絡(luò)的反饋：1）定義參考數(shù)值P；2）若Rk≥Pk-1，那么有W+ij修正為w+ji+Rk； w-jt修正為w-jt+Rk/（n-1） .（ t≠i）

當(dāng)該路徑的回饋函數(shù)大于等于P，到達(dá)神經(jīng)元j的所有正權(quán)重加強(qiáng)，這個(gè)就意味改路徑下次被使用的機(jī)率增大，而且其它的負(fù)權(quán)重會(huì)相應(yīng)加強(qiáng)些許，以期達(dá)到平衡。反之，神經(jīng)元j的負(fù)權(quán)重被加強(qiáng)，該路徑被使用的機(jī)率減小，而且其正權(quán)重相應(yīng)加強(qiáng)達(dá)到平衡。

在此例中，節(jié)點(diǎn)A到目的節(jié)點(diǎn)F，路徑（A，C，F(xiàn)）跳轉(zhuǎn)2次，測量數(shù)據(jù)包返回起始節(jié)點(diǎn)A，獲得的路徑值為2。α為學(xué)習(xí)速率，用來控制反饋函數(shù)的取值范圍。若α值取0.5，路徑（A，C，F(xiàn)）的反饋函數(shù)為1，路徑（A，E，C，F(xiàn)）的反饋值為0.667，很顯然前一個(gè)路徑為改變權(quán)重值做出最大的貢獻(xiàn)，那么神經(jīng)元就優(yōu)先選擇該路徑。

3 BP神經(jīng)網(wǎng)絡(luò)算法過程

1）分別對輸入層到隱含層的權(quán)值、隱含層到輸出層的權(quán)值和輸入層到隱含層的閥值進(jìn)行初始化。（其中p0表示訓(xùn)練樣本輸入；t0表示訓(xùn)練樣本期望值；ptest表示需要仿真的樣本；l表示隱含層神經(jīng)元數(shù)目；r表示迭代次數(shù)；lv表示權(quán)值學(xué)習(xí)率；lf表示閥值學(xué)習(xí)率；mse表示誤差）

Function[out7，out1，out2，out3，out4，out5，out6]=bp0（p0，t0，ptest，l，r，lv，lf，mse） [p，minp，maxp，t，mint，maxt]=premnmx（p0，t0）；

P2=tramnmx（ptest，minp，maxp）；

m=size（p）；

n=size（t）；

w=rand（m（1），1）； %初始化輸入層到隱含層的權(quán)值

v=rand（1，n（1））； %初始化隱含層到輸出層的權(quán)值

thetal1=rand（1，1）； %初始化輸入層的閥值

thetal2=rand（n（1），1）； %初始化隱含層的閥值

m0=size（ptest）；

sum00（1：r）=mse；

h0=plot（1：r，sum00，EraseMode，normal）；

2）分別計(jì)算輸入層的輸出、隱含層的輸出和輸出層的輸出。

o1=p（：，g0）； %輸入層的輸出

o2=1./（1+exp（-（w*o1+theta1）））；%計(jì)算隱含層的輸出

o3=v*o2+theta2； %計(jì)算輸出層的輸出

e=t（：，g0）-o3；

3）對神經(jīng)網(wǎng)絡(luò)中的各層次進(jìn)行訓(xùn)練，即對輸出層、隱含層和輸入層進(jìn)行閥值調(diào)整。

theta2=theta2+lf*e； %調(diào)整輸出層閥值

deta=v*e；

v=v+lv*o2*e； %調(diào)整輸入層至隱含層權(quán)值

g=（o2）.*（1-o2）.*deta；

theta1=theta1+lf*g； %調(diào)整隱含層閥值

w=w+lv*o1*g； %調(diào)整隱含層至輸出層權(quán)值

4 結(jié)語

本文針對QOS的特診及相應(yīng)的一些參數(shù)特點(diǎn)，構(gòu)建了QOS組播路由的數(shù)學(xué)模型。然后在此基礎(chǔ)之上利用神經(jīng)網(wǎng)絡(luò)的工作原理和流程，立足于QOS路由——NP-complete問題的特征，闡述了選取BP神經(jīng)網(wǎng)絡(luò)算法作為參考依據(jù)的原因。和算法過程。

【參考文獻(xiàn)】

[1]Q Zhu，M Parsa，J Garcial-Luna-Aceves.A Source-based Algonthm for Delay-constrained Minimum-cost Multi casting[J]. Proceeding of IEEE INFOCOM95， 1995.

[2]方建安，等.采用神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)的神經(jīng)網(wǎng)絡(luò)控制器[J].控制與決策，1993，3（3）.

[3]萬曉榆.下一代網(wǎng)絡(luò)技術(shù)與應(yīng)用[M].北京：人民郵電出版社，2003，3：15-16.

[責(zé)任編輯：丁艷]

3 BP神經(jīng)網(wǎng)絡(luò)算法過程

1）分別對輸入層到隱含層的權(quán)值、隱含層到輸出層的權(quán)值和輸入層到隱含層的閥值進(jìn)行初始化。（其中p0表示訓(xùn)練樣本輸入；t0表示訓(xùn)練樣本期望值；ptest表示需要仿真的樣本；l表示隱含層神經(jīng)元數(shù)目；r表示迭代次數(shù)；lv表示權(quán)值學(xué)習(xí)率；lf表示閥值學(xué)習(xí)率；mse表示誤差）

Function[out7，out1，out2，out3，out4，out5，out6]=bp0（p0，t0，ptest，l，r，lv，lf，mse） [p，minp，maxp，t，mint，maxt]=premnmx（p0，t0）；

P2=tramnmx（ptest，minp，maxp）；

m=size（p）；

n=size（t）；

w=rand（m（1），1）； %初始化輸入層到隱含層的權(quán)值

v=rand（1，n（1））； %初始化隱含層到輸出層的權(quán)值

thetal1=rand（1，1）； %初始化輸入層的閥值

thetal2=rand（n（1），1）； %初始化隱含層的閥值

m0=size（ptest）；

sum00（1：r）=mse；

h0=plot（1：r，sum00，EraseMode，normal）；

2）分別計(jì)算輸入層的輸出、隱含層的輸出和輸出層的輸出。

o1=p（：，g0）； %輸入層的輸出

o2=1./（1+exp（-（w*o1+theta1）））；%計(jì)算隱含層的輸出

o3=v*o2+theta2； %計(jì)算輸出層的輸出

e=t（：，g0）-o3；

3）對神經(jīng)網(wǎng)絡(luò)中的各層次進(jìn)行訓(xùn)練，即對輸出層、隱含層和輸入層進(jìn)行閥值調(diào)整。

theta2=theta2+lf*e； %調(diào)整輸出層閥值

deta=v*e；

v=v+lv*o2*e； %調(diào)整輸入層至隱含層權(quán)值

g=（o2）.*（1-o2）.*deta；

theta1=theta1+lf*g； %調(diào)整隱含層閥值

w=w+lv*o1*g； %調(diào)整隱含層至輸出層權(quán)值

4 結(jié)語

本文針對QOS的特診及相應(yīng)的一些參數(shù)特點(diǎn)，構(gòu)建了QOS組播路由的數(shù)學(xué)模型。然后在此基礎(chǔ)之上利用神經(jīng)網(wǎng)絡(luò)的工作原理和流程，立足于QOS路由——NP-complete問題的特征，闡述了選取BP神經(jīng)網(wǎng)絡(luò)算法作為參考依據(jù)的原因。和算法過程。

【參考文獻(xiàn)】

[1]Q Zhu，M Parsa，J Garcial-Luna-Aceves.A Source-based Algonthm for Delay-constrained Minimum-cost Multi casting[J]. Proceeding of IEEE INFOCOM95， 1995.

[2]方建安，等.采用神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)的神經(jīng)網(wǎng)絡(luò)控制器[J].控制與決策，1993，3（3）.

[3]萬曉榆.下一代網(wǎng)絡(luò)技術(shù)與應(yīng)用[M].北京：人民郵電出版社，2003，3：15-16.

[責(zé)任編輯：丁艷]

3 BP神經(jīng)網(wǎng)絡(luò)算法過程

1）分別對輸入層到隱含層的權(quán)值、隱含層到輸出層的權(quán)值和輸入層到隱含層的閥值進(jìn)行初始化。（其中p0表示訓(xùn)練樣本輸入；t0表示訓(xùn)練樣本期望值；ptest表示需要仿真的樣本；l表示隱含層神經(jīng)元數(shù)目；r表示迭代次數(shù)；lv表示權(quán)值學(xué)習(xí)率；lf表示閥值學(xué)習(xí)率；mse表示誤差）

Function[out7，out1，out2，out3，out4，out5，out6]=bp0（p0，t0，ptest，l，r，lv，lf，mse） [p，minp，maxp，t，mint，maxt]=premnmx（p0，t0）；

P2=tramnmx（ptest，minp，maxp）；

m=size（p）；

n=size（t）；

w=rand（m（1），1）； %初始化輸入層到隱含層的權(quán)值

v=rand（1，n（1））； %初始化隱含層到輸出層的權(quán)值

thetal1=rand（1，1）； %初始化輸入層的閥值

thetal2=rand（n（1），1）； %初始化隱含層的閥值

m0=size（ptest）；

sum00（1：r）=mse；

h0=plot（1：r，sum00，EraseMode，normal）；

2）分別計(jì)算輸入層的輸出、隱含層的輸出和輸出層的輸出。

o1=p（：，g0）； %輸入層的輸出

o2=1./（1+exp（-（w*o1+theta1）））；%計(jì)算隱含層的輸出

o3=v*o2+theta2； %計(jì)算輸出層的輸出

e=t（：，g0）-o3；

3）對神經(jīng)網(wǎng)絡(luò)中的各層次進(jìn)行訓(xùn)練，即對輸出層、隱含層和輸入層進(jìn)行閥值調(diào)整。

theta2=theta2+lf*e； %調(diào)整輸出層閥值

deta=v*e；

v=v+lv*o2*e； %調(diào)整輸入層至隱含層權(quán)值

g=（o2）.*（1-o2）.*deta；

theta1=theta1+lf*g； %調(diào)整隱含層閥值

w=w+lv*o1*g； %調(diào)整隱含層至輸出層權(quán)值

4 結(jié)語

本文針對QOS的特診及相應(yīng)的一些參數(shù)特點(diǎn)，構(gòu)建了QOS組播路由的數(shù)學(xué)模型。然后在此基礎(chǔ)之上利用神經(jīng)網(wǎng)絡(luò)的工作原理和流程，立足于QOS路由——NP-complete問題的特征，闡述了選取BP神經(jīng)網(wǎng)絡(luò)算法作為參考依據(jù)的原因。和算法過程。

【參考文獻(xiàn)】

[1]Q Zhu，M Parsa，J Garcial-Luna-Aceves.A Source-based Algonthm for Delay-constrained Minimum-cost Multi casting[J]. Proceeding of IEEE INFOCOM95， 1995.

[2]方建安，等.采用神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)的神經(jīng)網(wǎng)絡(luò)控制器[J].控制與決策，1993，3（3）.

[3]萬曉榆.下一代網(wǎng)絡(luò)技術(shù)與應(yīng)用[M].北京：人民郵電出版社，2003，3：15-16.

[責(zé)任編輯：丁艷]