遺傳算法在寬帶通信網(wǎng)設(shè)計(jì)中的應(yīng)用

南京郵電學(xué)院 王國華 張順頤

　　摘要：本文討論了使用遺傳算法來進(jìn)行寬帶通信網(wǎng)絡(luò)設(shè)計(jì)的研究方法,使用遺傳算法對網(wǎng)絡(luò)設(shè)計(jì)中的拓?fù)�、路由和容量分配等方面的�?yōu)化問題進(jìn)行了詳細(xì)的描述,并簡要舉例說明遺傳算法的使用。

關(guān)鍵詞：遺傳算法,網(wǎng)絡(luò)設(shè)計(jì),通信網(wǎng)絡(luò),網(wǎng)絡(luò)時延

　　一、引言

　　ITU-T對寬帶業(yè)務(wù)定義為支持速率高于1.5 M bit/s（或者在ISDN、T1、DS1中數(shù)字術(shù)語的基本速率的傳輸通道能力）的業(yè)務(wù)。寬帶網(wǎng)絡(luò)主要是作為骨干傳輸網(wǎng)絡(luò)使用,要求提供較高的帶寬滿足數(shù)據(jù)流量的突發(fā)性,可按需分配帶寬,傳輸延遲小,節(jié)點(diǎn)多且連接關(guān)系復(fù)雜,節(jié)點(diǎn)發(fā)送數(shù)據(jù)類型多,流量差別大,并覆蓋比較大的區(qū)域。隨著網(wǎng)絡(luò)的迅速發(fā)展,網(wǎng)絡(luò)業(yè)務(wù)量成倍增加,以及網(wǎng)絡(luò)應(yīng)用日益增多,網(wǎng)絡(luò)需要越來越高的帶寬傳輸數(shù)據(jù)、聲音、圖像等大量信息；光纖的鋪設(shè)解決了傳輸介質(zhì)的帶寬,網(wǎng)絡(luò)瓶頸已經(jīng)轉(zhuǎn)化為帶寬使用效率、交換能力、最佳或最短路由的選擇等問題。使用遺傳算法（Genetic Algorithm,GA）可以為這些問題提供快速簡便的解決方案,但原有解決方案通常都是基于窄帶網(wǎng)絡(luò)的研究方法,當(dāng)遇到寬帶網(wǎng)絡(luò)問題時這些方法并不完全適用。本文著重于研究使用遺傳算法作為優(yōu)化和研究工具為寬帶網(wǎng)絡(luò)設(shè)計(jì)提供一個比較標(biāo)準(zhǔn)的解決方案,并著重于網(wǎng)絡(luò)路由的優(yōu)化方法。

　　二、寬帶通信網(wǎng)絡(luò)設(shè)計(jì)相關(guān)參數(shù)

　　寬帶網(wǎng)具有很大的傳輸帶寬,主要研究的是網(wǎng)絡(luò)的交換能力、路由選擇、網(wǎng)絡(luò)延遲和組織結(jié)構(gòu)等方面。寬帶網(wǎng)傳輸延遲主要是受交換能力和路由選擇等影響形成的延遲。網(wǎng)絡(luò)采用不同的交換技術(shù)對網(wǎng)絡(luò)設(shè)計(jì)和業(yè)務(wù)具有一定的影響,主要體現(xiàn)在網(wǎng)絡(luò)規(guī)模、費(fèi)用成本、交換速率、QoS、多播支持和靈活性等方面。當(dāng)前寬帶網(wǎng)絡(luò)的主要發(fā)展方向是寬帶IP網(wǎng)絡(luò)。

　　為了在通信網(wǎng)中將遺傳算法用公式化的方法描述出來,下面給出通信網(wǎng)相關(guān)的研究設(shè)計(jì)參數(shù)定義。

　　● 鏈路設(shè)計(jì)：鏈路的設(shè)計(jì)包括鏈路的傳輸能力、帶寬、容量、傳輸延遲等方面的因素。寬帶網(wǎng)絡(luò)的主干帶寬非常大,鏈路的傳輸延遲、帶寬和容量的限制一般情況下可以不考慮,設(shè)計(jì)中主要考慮的是租用鏈路帶寬的費(fèi)用以及帶寬分配和利用率等。若一條連接共租用了b條鏈路,每條鏈路i上租用的Ci容量的費(fèi)用用di（Ci）表示,那么這條連接的總租用費(fèi)用D就是：

　　● 交換節(jié)點(diǎn)設(shè)計(jì)

　　交換節(jié)點(diǎn)設(shè)計(jì)包括交換能力、接口能力、延遲、封裝延遲、路由等。

　　交換節(jié)點(diǎn)的交換能力對寬帶網(wǎng)絡(luò)有較大的影響,造成延遲的主要部分來自于此,因此交換能力往往會成為網(wǎng)絡(luò)交換的瓶頸。節(jié)點(diǎn)交換能力包括交換速率、交換接口的吞吐量等,交換速率主要受到硬件性能、數(shù)據(jù)包分析和封裝效率、路由選擇算法和選擇速率等影響,采用快速有效的路由選擇算法可以極大的提高交換速率,交換接口吞吐量和吞吐能力的大小直接制約著鏈路帶寬的使用率和傳輸時延,如果鏈路的流量大于接口的吞吐量會在節(jié)點(diǎn)緩沖中排隊(duì)等候造成時延。如果交換節(jié)點(diǎn)的交換能力強(qiáng)則數(shù)據(jù)包的延遲小,交換能力弱則延遲增大,甚至?xí)�發(fā)生擁塞導(dǎo)致丟包的情況。

　　● 包延遲

　　寬帶網(wǎng)絡(luò)的平均包延遲主要由兩方面構(gòu)成：隊(duì)列延遲和交換延遲。在寬帶網(wǎng)絡(luò)中鏈路傳輸延遲非常小,可以不予考慮。網(wǎng)絡(luò)中到達(dá)節(jié)點(diǎn)的業(yè)務(wù)量是隨機(jī)的,數(shù)據(jù)隊(duì)列被存儲在交換節(jié)點(diǎn)的交換緩沖區(qū)中,如果緩沖區(qū)溢出會導(dǎo)致數(shù)據(jù)包丟失。假設(shè)在一個設(shè)計(jì)比較好的網(wǎng)絡(luò)中很少發(fā)生阻塞或者數(shù)據(jù)包很少丟失,那么這個網(wǎng)絡(luò)就可以近似地認(rèn)為具有無限大緩沖隊(duì)列或者延遲系統(tǒng)。因此,隊(duì)列延遲和交換延遲都可以用M/M/1隊(duì)列來模擬。根據(jù)參考[3]中的平均等待時間計(jì)算公式可以計(jì)算延遲時間,平均等待時間計(jì)算公式為：

　　其中ρ=λ/μ,λ為到達(dá)率,μ為服務(wù)率。

　　以代表網(wǎng)絡(luò)中鏈路的數(shù)目,和分別代表鏈路m上的容量和總流量,以bit/s為單位。是網(wǎng)絡(luò)中交換的個數(shù),和分別代表交換n的交換能力和總流量,也以bit/s為單位。σ是網(wǎng)絡(luò)中的平均流量。則隊(duì)列延遲和交換延遲計(jì)算如下：

　　隊(duì)列延遲主要是由于主干接口吞吐能力的限制引起的,當(dāng)鏈路上需要傳輸?shù)目偭髁啃∮谠撴溌返慕涌谕掏履芰�時該流量可以順利傳輸,當(dāng)總流量大于接口吞吐能力時則需要在緩沖中排隊(duì)等候發(fā)送。在這個M/M/1隊(duì)列中,到達(dá)率,服務(wù)率,由于傳輸延遲（即服務(wù)時間）小到可以不予考慮,主干隊(duì)列延遲時間就是等待時間,帶入公式1,得到平均隊(duì)列延遲時間T1為：

　　交換延遲主要是由于節(jié)點(diǎn)的交換能力的限制引起的,當(dāng)?shù)竭_(dá)節(jié)點(diǎn)的總流量小于該節(jié)點(diǎn)的交換能力時該流量可以順利進(jìn)行交換,當(dāng)總流量大于交換能力時就需要在緩沖中排隊(duì)等待交換。在這個M/M/1隊(duì)列中,到達(dá)率,服務(wù)率,由于寬帶網(wǎng)中交換速率普遍提高,線速交換的大量應(yīng)用,交換處理時間（即服務(wù)時間）可以忽略不計(jì),交換延遲就是等待時間,帶入公式1,平均交換延遲時間T2就是：

　　這樣整個網(wǎng)絡(luò)中（不包含傳播延遲）平包延遲T就是：

　　需要指出的是,用遺傳算法的解決方案不依賴于單一的延遲或者費(fèi)用等結(jié)構(gòu)的模型。對于不同的網(wǎng)絡(luò)或者同一網(wǎng)絡(luò)的不同需求可以具有不同的結(jié)構(gòu)模型。

　　三、遺傳算法簡述

　　遺傳算法是根據(jù)生物學(xué)上的染色體基因因子構(gòu)成機(jī)制而產(chǎn)生的一種計(jì)算工程學(xué)。通過遺傳算法可以找出最優(yōu)解決方案。它是一種快捷、簡便、容錯性強(qiáng)的算法,可以直接對結(jié)構(gòu)對象進(jìn)行操作,易于優(yōu)化和并行化,適應(yīng)范圍廣。

　　遺傳算法是具有“生產(chǎn)+檢測”的迭代過程的搜索算法。它是一種群體型操作,該操作以群體中的所有個體為對象。選擇、交叉、變異和重排序是遺傳算法的主要操作算子。遺傳算法的運(yùn)算過程為：選擇編碼方式→產(chǎn)生初始群體→計(jì)算初始群體適應(yīng)度→如果不滿足終止條件則循環(huán)以下過程直到滿足為止：選擇→交叉→變異→（重排序）→計(jì)算新群體適應(yīng)度。

　　四、使用遺傳算法建立網(wǎng)絡(luò)優(yōu)化模型

　　網(wǎng)絡(luò)的總體優(yōu)化過程可分為拓?fù)鋬?yōu)化、路由優(yōu)化和容量優(yōu)化等多種優(yōu)化處理過程。下面對優(yōu)化過程

進(jìn)行具體描述,并建立相應(yīng)的的網(wǎng)絡(luò)模型。

　　4.1 基因因子表示方法

　　網(wǎng)絡(luò)拓?fù)淇梢杂霉?jié)點(diǎn)間連接邊的集合來定義,更直接的就是用鄰接矩陣表示。一個n×n的布爾值矩陣中,如果節(jié)點(diǎn)x到節(jié)點(diǎn)y之間有邊連接則a[x][y]值為1,否則為0。這是在假定鏈路是雙連接的情況下,也就是說這是一個對稱矩陣。這樣只需要n（n-1）/2個二進(jìn)制值就可以表示這個矩陣。為方便起見,二維矩陣可以通過如下公式轉(zhuǎn)變?yōu)橐痪S矩陣A：

a [k]=a [i] [j] [1]

　　這里,j > i,并且k =(2n - i)(i - 1)/2 + j - i容量、費(fèi)用等參數(shù)也可以使用二維鄰接矩陣表示,在這個矩陣中的因子值就是連接之間的相應(yīng)參數(shù)值。一個n×n的矩陣中,如果節(jié)點(diǎn)x到節(jié)點(diǎn)y之間有邊連接則a[x][y]對應(yīng)參數(shù)值為C,否則為0,其中C就是這個相應(yīng)的參數(shù)值。這是在假定鏈路是雙連接的情況下,這個矩陣也是一個對稱矩陣,只需要n（n-1）/2個二進(jìn)制值就可以表示這個矩陣。為了方便起見,二維矩陣可以通過如下公式轉(zhuǎn)變?yōu)橐痪S矩陣B：

b [k] = a [i] [j] [2]

　　這里,j > i,并且k= （2n - i）（i - 1）/2 + j - i這樣,代表網(wǎng)絡(luò)的拓?fù)洹⑷萘炕蛘哔M(fèi)用等參數(shù)的染色體基因就可以用一個長度為n（n - 1）/ 2位的二進(jìn)制串來表示,它等同于式[1]和[2]的矩陣A和B。這樣選擇、交叉、突變以及其他的遺傳算法常規(guī)分析動作就可以分別運(yùn)用到運(yùn)算中來。并且在運(yùn)算中,往往需要把A和B兩個矩陣結(jié)合起來進(jìn)行分析和研究。比如已知網(wǎng)絡(luò)中兩節(jié)點(diǎn)間的路由矩陣A和網(wǎng)絡(luò)的費(fèi)用矩陣B,就可以得出兩節(jié)點(diǎn)之間的路由總費(fèi)用D：

　　其中N為網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)量。通過遺傳算法的運(yùn)算改變節(jié)點(diǎn)的路由矩陣A就可以通過上式得到相應(yīng)路由的總費(fèi)用。

　　在實(shí)際的網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)中,染色體的編碼還往往采取域的概念,就是將某些相關(guān)的節(jié)點(diǎn)或者鏈路等基因因子結(jié)合在一起作為一個整體參加運(yùn)算,并在運(yùn)算中采取一定的運(yùn)算規(guī)則,使得這個域中的基因因子同時發(fā)生符合某種規(guī)則的變化,這樣可以大大簡化和方便遺傳算法的運(yùn)算。

　　4.2 寬帶網(wǎng)絡(luò)優(yōu)化中遺傳算法的應(yīng)用

　　首先討論寬帶網(wǎng)絡(luò)優(yōu)化中遺傳算法的終止條件：網(wǎng)絡(luò)設(shè)計(jì)中遺傳算法的終止條件可以結(jié)合寬帶網(wǎng)絡(luò)設(shè)計(jì)的相關(guān)參數(shù)條件來采用某種判定準(zhǔn)則,當(dāng)判定出染色體集群已經(jīng)進(jìn)化成熟且不再有進(jìn)化趨勢時就可以終止算法的運(yùn)行,常用判定準(zhǔn)則有：連續(xù)幾代個體平均適應(yīng)度的差異小于某一個極小的閾值；或者群體中所有個體適應(yīng)度的方差小于某一個極小的閾值。當(dāng)優(yōu)化過程中連續(xù)幾代子染色體集群中的最優(yōu)子染色體始終相同,或者總費(fèi)用、總延遲等參數(shù)指標(biāo)已經(jīng)達(dá)到設(shè)計(jì)要求的標(biāo)準(zhǔn),那么也可以判定已經(jīng)到達(dá)優(yōu)化的終止條件。也可以通過預(yù)先設(shè)定遺傳運(yùn)算發(fā)生的次數(shù)來終止遺傳算法的運(yùn)算。

　　選擇運(yùn)算：選擇運(yùn)算按照一定的比例在當(dāng)前父染色體集群中選擇一些優(yōu)良的染色體復(fù)制到下一代子染色體集群中,繼續(xù)進(jìn)行遺傳運(yùn)算。在選擇運(yùn)算中為了防止出現(xiàn)局部最優(yōu)化（早熟）的情況,可以采用加長編碼長度或者結(jié)合模擬退火算法等其他算法的方法進(jìn)行運(yùn)算,降低出現(xiàn)局部最優(yōu)的可能。交叉運(yùn)算：以路由優(yōu)化為例,可以將路由方案看作是染色體,路由染色體可以用下面的路徑列表來表示：

P = {p1,p2,……,p n（n-1）/2}

這里,p k = Path（i,j）=[i,x1,x2,……,xe,j]是代表從節(jié)點(diǎn)i到節(jié)點(diǎn)j的路由路徑的基因因子,i=1,……, n；k=g（i,j）

　　對于一個特定的路由方案P,鏈路的流量可以根據(jù)業(yè)務(wù)量需求來分配。這樣,路由方案的適合程度可以用從容量分配優(yōu)化中得到的最佳解決方案中得出。

　　對于父染色體P1和P2交叉運(yùn)算得到子染色體P的運(yùn)算中,

P1 = {p1,p2, ……, pn（n-1）/2}

P2 = {p’1 , p’2, ……,p’n（n-1）/2}

P= P1?P2 ={s（p1,p’1）,s（p2,p’2）,……,s（pn（n-1）/2,p’n(n-1)/2）}

這里,如果pi路徑比pj短,否則一般交叉發(fā)生的概率為0.4--0.99。

　　突變運(yùn)算：突變運(yùn)算一般在交叉運(yùn)算之后進(jìn)行。為了使突變在二進(jìn)制以外的實(shí)際應(yīng)用中得以進(jìn)行,可以采用隨機(jī)突變,概率函數(shù)為：g = g + Ψ(μ,σ),其中g(shù)是真實(shí)值基因因子,Ψ是隨機(jī)函數(shù),一般是高斯隨機(jī)函數(shù),μ,σ分別是和隨機(jī)函數(shù)有關(guān)的平均值和變量。

　　在通信網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)的具體應(yīng)用中,路由優(yōu)化的突變運(yùn)算就是將路由路徑p重新隨機(jī)選擇一條可行路由；容量優(yōu)化則是將鏈路L上的容量重新取值；突變發(fā)生的概率為0.0001--0.1。

　　重排序運(yùn)算：染色體中基因因子的排列順序?qū)τ谌旧�體特性的決定是至關(guān)重要的。重排序的目的就是查找更具有進(jìn)化潛力的基因因子序列。在路由優(yōu)化中,如果進(jìn)行重排序運(yùn)算,有可能會發(fā)現(xiàn)一條新的更為優(yōu)化的路由方案。重排序運(yùn)算發(fā)生的幾率非常小。

　　寬帶IP網(wǎng)絡(luò)路由是現(xiàn)代寬帶通信網(wǎng)中的一項(xiàng)關(guān)鍵技術(shù),現(xiàn)已有許多關(guān)于寬帶IP網(wǎng)路由的協(xié)議和產(chǎn)品,但是幾乎所有的路由協(xié)議都是以Dijkstra于五十年代提出的最短路徑模型（Dijkstra算法）為基礎(chǔ)的。當(dāng)最短路徑被阻塞時,數(shù)據(jù)包就被緩存以等待最短路徑修復(fù),這種路由策略并不高效,不能很好的反映網(wǎng)絡(luò)的動態(tài)性,也難以有效的實(shí)現(xiàn)網(wǎng)絡(luò)負(fù)載的分擔(dān),從而使得數(shù)據(jù)包在網(wǎng)絡(luò)中的實(shí)際傳輸時間與期望值差別很大,網(wǎng)絡(luò)帶寬利用率低、傳輸延遲大和傳輸總費(fèi)用高。寬帶網(wǎng)絡(luò)中數(shù)據(jù)傳輸?shù)穆酚蓛?yōu)化問題是寬帶網(wǎng)絡(luò)設(shè)計(jì)的重點(diǎn)之一,未來的智能路由器應(yīng)該能夠適應(yīng)動態(tài)變化的網(wǎng)絡(luò),使數(shù)據(jù)包得以避免擁塞從而獲取各方面的優(yōu)勢。遺傳算法可以很方便的和現(xiàn)存路由協(xié)議結(jié)合起來,對通信網(wǎng)中的路由算法進(jìn)行優(yōu)化,以獲得通信網(wǎng)的最佳路由。比如OSPF(開放式最短路徑優(yōu)先協(xié)議)中每個參與路由器都有網(wǎng)絡(luò)的完全拓?fù)湫畔?可以用遺傳算法與OSPF路由算法相結(jié)合進(jìn)行路由優(yōu)化和選擇；另外BGP(邊界網(wǎng)關(guān)協(xié)議)、RIP（路由信息協(xié)議）等路由協(xié)議的路由算法也可以很方便的和遺傳算法融合。

　　五、應(yīng)用舉例以及分析

　　建立遺傳算法的例程如下：

Chromosome GAs_Optimize(Chromosome Parent)

double xRate=0.5;//交叉概率

double mRate=0.05;//突變概率

double tRate=0.005//重排序概率

int Population_size=20;//父集群大小

int Sub_Population_size=20;//子集群大小

Population Pop(Population_size, Parent);//設(shè)置父集群

Population SubPop(Sub_Population_size);//設(shè)置子集群

GAs Optimize(Pop, xRate, mRate, tRate);//設(shè)置運(yùn)算參數(shù)

Optimize.Evaluate(Pop);//計(jì)算群體適合度

While (Optimize.Terminate=FALSE) {//判斷是否符合終止條件

Optimize.Select_Parent(Pop, SubPop);//選擇操作

Optimize.Recombine(SubPop);//臨時保存子集群

Optimize.Cross(SubPop);//交叉操作

Optimize.Mutate(SubPop);//突變操作

Optimize.Taxis(SubPop);//重排序操作

Optimize.Reinsert(Pop, SubPop);//將子集群重新插入父集群

Optimize.Evaluate(SubPop);}return Optimize.getbest();//返回最優(yōu)化結(jié)果}

　　使用了遺傳算法使得網(wǎng)絡(luò)設(shè)計(jì)的限制問題變得簡單化了。如圖2所示的網(wǎng)絡(luò),該網(wǎng)絡(luò)是一個雙向傳輸網(wǎng)絡(luò),每條主干線上的數(shù)字代表該主干線的使用費(fèi)用,現(xiàn)在要選擇一條從節(jié)點(diǎn)A到節(jié)點(diǎn)F的最小費(fèi)用的路由,而其他的因素暫時不予考慮。則該問題就是一個路由優(yōu)化問題。

　　在這個通信網(wǎng)絡(luò)中二維延遲矩陣為：

　　轉(zhuǎn)換成一維延遲矩陣D為：

　　D = {AB,AC,BC,BD,CD,CE,CG,DE,DF,EF,GF}

　　　= {4,3,2,5,2,3,2,1,3,4,4}

　　要使用遺傳算法進(jìn)行分析,首先要正確選擇遺傳染色體基因的表示法,以及遺傳算法的交叉、突變等運(yùn)算的基本規(guī)則。針對該網(wǎng)絡(luò)的優(yōu)化問題我們制定規(guī)則如下：

　　1、染色體基因用位串編碼表示,每一條主干傳輸線作為染色體基因的一個因子,一條主干傳輸線被選中則將對應(yīng)因子標(biāo)示為1,未選中則標(biāo)示為0；

　　2、染色體基因分塊表示,同一起點(diǎn)的鏈路的染色體基因因子放入同一個塊中,從某一節(jié)點(diǎn)出發(fā)沒有分支路由的鏈路因子也放入同一塊中。

　　3、交叉運(yùn)算中,塊與塊之間可以進(jìn)行交叉運(yùn)算,但塊內(nèi)的因子不能進(jìn)行交叉運(yùn)算；

　　4、突變運(yùn)算中,以塊為單位進(jìn)行突變；無效主干傳輸線因子可自動優(yōu)化并恢復(fù)為0。

　　根據(jù)以上規(guī)則,進(jìn)行圖2的網(wǎng)絡(luò)路由優(yōu)化。染色體的基因因子分塊分為以下幾塊：AB、AC塊,BC、BD塊,CD、CE、CG、GF塊,DE、DF塊和EF塊。隨機(jī)選擇兩條染色體基因作為初始運(yùn)算染色體集群：使用R1、R2作為父染色體集群進(jìn)行遺傳算法運(yùn)算,得到的第一代子染色體集群為：繼續(xù)進(jìn)行遺傳算法得到第二代子染色體集群為：

　　繼續(xù)進(jìn)行遺傳算法運(yùn)算得到的子染色體集群和第二代子染色體集群相比,最優(yōu)子染色體基因仍然是R5,那么遺傳算法到此終止。從子染色體集群中我們可以很清楚的得出結(jié)論,延遲最短的路由就是A郈郉郌, 次短路由是A郈郍郌。

　　如果網(wǎng)絡(luò)鏈路發(fā)生了阻塞或者故障導(dǎo)致CG鏈路不能使用,那么就需要重新計(jì)算次短路由,染色體基因因子重新分塊為：AB、AC塊,BC、BD塊,CD、CE塊,DE、DF塊和EF塊。再次使用遺傳算法進(jìn)行計(jì)算,初始運(yùn)算染色體集群為：運(yùn)算得到第一代子染色體集群為繼續(xù)進(jìn)行遺傳算法得到第二代子染色體集群為：

　　這里終止條件和上一次運(yùn)算的終止條件相同。最短路由仍然是A郈郉郌,次短路由是A郈郋郌。在這個例子中,遺傳算法的計(jì)算過程大概僅需要3個運(yùn)算循環(huán)15 ~ 18次運(yùn)算就可以完成,如果使用Dijkstra算法進(jìn)行運(yùn)算,那么所用的時間復(fù)雜性為n(n—1) 3/2,即n2量級,在這個例子中就需要7個運(yùn)算循環(huán)72次運(yùn)算。隨著網(wǎng)絡(luò)結(jié)構(gòu)的復(fù)雜情況和節(jié)點(diǎn)鏈路數(shù)量的增加,與使用Dijkstra算法相比,遺傳算法的運(yùn)算速度更快,其優(yōu)越性更加顯著。

六、結(jié)論

　　寬帶通信網(wǎng)絡(luò)的優(yōu)化是一個復(fù)雜且涉及范圍廣泛的課題,是寬帶通信網(wǎng)絡(luò)技術(shù)中不可缺少的部分。網(wǎng)絡(luò)優(yōu)化的傳統(tǒng)方法有很多,比如梯度法、爬山法、模擬退火算法、列表尋優(yōu)法等,但是他們的局限性也非常大,算法也比較復(fù)雜,在許多限制條件下不能有效的發(fā)揮作用。遺傳算法由于其高效、快速等優(yōu)點(diǎn)成為眾多方法中比較好的一種。可以在遺傳算法中融合其它優(yōu)化方法的思想,構(gòu)成一種混合遺傳算法。基于遺傳算法的網(wǎng)絡(luò)優(yōu)化方法是網(wǎng)絡(luò)優(yōu)化發(fā)展的主要方向之一。本文對遺傳算法在網(wǎng)絡(luò)優(yōu)化中的應(yīng)用只進(jìn)行了初步的探討,要將這種方法完善還需要做進(jìn)一步探討和研究。

七、參考文獻(xiàn)

[1]Holland, J. H: Adaption in natural and artifical systems. MIT Press , 1975

[2]Thomas Back: Evolutionary Algorithms in Theory and Practice. Oxford University Press , 1996

[3]周炯磐：《通信網(wǎng)理論基礎(chǔ)》,人民郵電出版社,1992

[4]盛友招：《排隊(duì)論及其在計(jì)算機(jī)通信中的應(yīng)用》,北京郵電大學(xué)出版社,1998

[5]周明、孫樹棟：《遺傳算法原理及應(yīng)用》,國防工業(yè)出版社,1999

[6]葉敏：《程控?cái)?shù)字交換與現(xiàn)代通信網(wǎng)》,北京郵電大學(xué)出版社,1998

[7]趙慧玲等：《寬帶Internet網(wǎng)絡(luò)技術(shù)》,電子工業(yè)出版社,1999

[8]William Stallings：《局域網(wǎng)與城域網(wǎng)（第五版）》,電子工業(yè)出版社,1998

[9]趙慧玲等：《ATM、幀中繼、IP技術(shù)與應(yīng)用》,電子工業(yè)出版社,1998

[10]陳國良等：《遺傳算法及其應(yīng)用》,人民郵電出版社,1996

[11]顧冠群等：《計(jì)算機(jī)網(wǎng)絡(luò)》,江蘇省科學(xué)技術(shù)出版社,1989

摘自《網(wǎng)絡(luò)通信世界》