主頁(yè)（http://www.130131.com）：遺傳算法在寬帶通信網(wǎng)設(shè)計(jì)中的應(yīng)用

　　一、引言

　　ITU-T對(duì)寬帶業(yè)務(wù)定義為支持速率高于1.5 M bit/s（或者在ISDN、T1、DS1中數(shù)字術(shù)語(yǔ)的基本速率的傳輸通道能力）的業(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ò)需要越來(lái)越高的帶寬傳輸數(shù)據(jù)、聲音、圖像等大量信息；光纖的鋪設(shè)解決了傳輸介質(zhì)的帶寬,網(wǎng)絡(luò)瓶頸已經(jīng)轉(zhuǎn)化為帶寬使用效率、交換能力、最佳或最短路由的選擇等問(wèn)題。使用遺傳算法（Genetic Algorithm,GA）可以為這些問(wèn)題提供快速簡(jiǎn)便的解決方案,但原有解決方案通常都是基于窄帶網(wǎng)絡(luò)的研究方法,當(dāng)遇到寬帶網(wǎng)絡(luò)問(wèn)題時(shí)這些方法并不完全適用。本文著重于研究使用遺傳算法作為優(yōu)化和研究工具為寬帶網(wǎng)絡(luò)設(shè)計(jì)提供一個(gè)比較標(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ù)對(duì)網(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)中將遺傳算法用公式化的方法描述出來(lái),下面給出通信網(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)的交換能力對(duì)寬帶網(wǎng)絡(luò)有較大的影響,造成延遲的主要部分來(lái)自于此,因此交換能力往往會(huì)成為網(wǎng)絡(luò)交換的瓶頸。節(jié)點(diǎn)交換能力包括交換速率、交換接口的吞吐量等,交換速率主要受到硬件性能、數(shù)據(jù)包分析和封裝效率、路由選擇算法和選擇速率等影響,采用快速有效的路由選擇算法可以極大的提高交換速率,交換接口吞吐量和吞吐能力的大小直接制約著鏈路帶寬的使用率和傳輸時(shí)延,如果鏈路的流量大于接口的吞吐量會(huì)在節(jié)點(diǎn)緩沖中排隊(duì)等候造成時(shí)延。如果交換節(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ì)列被存儲(chǔ)在交換節(jié)點(diǎn)的交換緩沖區(qū)中,如果緩沖區(qū)溢出會(huì)導(dǎo)致數(shù)據(jù)包丟失。假設(shè)在一個(gè)設(shè)計(jì)比較好的網(wǎng)絡(luò)中很少發(fā)生阻塞或者數(shù)據(jù)包很少丟失,那么這個(gè)網(wǎng)絡(luò)就可以近似地認(rèn)為具有無(wú)限大緩沖隊(duì)列或者延遲系統(tǒng)。因此,隊(duì)列延遲和交換延遲都可以用M/M/1隊(duì)列來(lái)模擬。根據(jù)參考[3]中的平均等待時(shí)間計(jì)算公式可以計(jì)算延遲時(shí)間,平均等待時(shí)間計(jì)算公式為：

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

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

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

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

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

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

　　三、遺傳算法簡(jiǎn)述

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

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

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

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

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

　　4.1 基因因子表示方法

　　網(wǎng)絡(luò)拓?fù)淇梢杂霉?jié)點(diǎn)間連接邊的集合來(lái)定義,更直接的就是用鄰接矩陣表示。一個(gè)n×n的布爾值矩陣中,如果節(jié)點(diǎn)x到節(jié)點(diǎn)y之間有邊連接則a[x][y]值為1,否則為0。這是在假定鏈路是雙連接的情況下,也就是說(shuō)這是一個(gè)對(duì)稱矩陣。這樣只需要n（n-1）/2個(gè)二進(jìn)制值就可以表示這個(gè)矩陣。為方便起見(jiàn),二維矩陣可以通過(guò)如下公式轉(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ù)也可以使用二維鄰接矩陣表示,在這個(gè)矩陣中的因子值就是連接之間的相應(yīng)參數(shù)值。一個(gè)n×n的矩陣中,如果節(jié)點(diǎn)x到節(jié)點(diǎn)y之間有邊連接則a[x][y]對(duì)應(yīng)參數(shù)值為C,否則為0,其中C就是這個(gè)相應(yīng)的參數(shù)值。這是在假定鏈路是雙連接的情況下,這個(gè)矩陣也是一個(gè)對(duì)稱矩陣,只需要n（n-1）/2個(gè)二進(jìn)制值就可以表示這個(gè)矩陣。為了方便起見(jiàn),二維矩陣可以通過(guò)如下公式轉(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ù)�、容量或者費(fèi)用等參數(shù)的染色體基因就可以用一個(gè)長(zhǎng)度為n（n - 1）/ 2位的二進(jìn)制串來(lái)表示,它等同于式[1]和[2]的矩陣A和B。這樣選擇、交叉、突變以及其他的遺傳算法常規(guī)分析動(dòng)作就可以分別運(yùn)用到運(yùn)算中來(lái)。并且在運(yùn)算中,往往需要把A和B兩個(gè)矩陣結(jié)合起來(lái)進(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ù)量。通過(guò)遺傳算法的運(yùn)算改變節(jié)點(diǎn)的路由矩陣A就可以通過(guò)上式得到相應(yīng)路由的總費(fèi)用。

　　在實(shí)際的網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)中,染色體的編碼還往往采取域的概念,就是將某些相關(guān)的節(jié)點(diǎn)或者鏈路等基因因子結(jié)合在一起作為一個(gè)整體參加運(yùn)算,并在運(yùn)算中采取一定的運(yùn)算規(guī)則,使得這個(gè)域中的基因因子同時(shí)發(fā)生符合某種規(guī)則的變化,這樣可以大大簡(jiǎn)化和方便遺傳算法的運(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ù)條件來(lái)采用某種判定準(zhǔn)則,當(dāng)判定出染色體集群已經(jīng)進(jìn)化成熟且不再有進(jìn)化趨勢(shì)時(shí)就可以終止算法的運(yùn)行,常用判定準(zhǔn)則有：連續(xù)幾代個(gè)體平均適應(yīng)度的差異小于某一個(gè)極小的閾值；或者群體中所有個(gè)體適應(yīng)度的方差小于某一個(gè)極小的閾值。當(dāng)優(yōu)化過(guò)程中連續(xù)幾代子染色體集群中的最優(yōu)子染色體始終相同,或者總費(fèi)用、總延遲等參數(shù)指標(biāo)已經(jīng)達(dá)到設(shè)計(jì)要求的標(biāo)準(zhǔn),那么也可以判定已經(jīng)到達(dá)優(yōu)化的終止條件。也可以通過(guò)預(yù)先設(shè)定遺傳運(yùn)算發(fā)生的次數(shù)來(lái)終止遺傳算法的運(yùn)算。

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

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）

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

　　對(duì)于父染色體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)行。為了使突變?cè)诙�進(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ī)選擇一條可行路由；容量?jī)?yōu)化則是將鏈路L上的容量重新取值；突變發(fā)生的概率為0.0001--0.1。

　　重排序運(yùn)算：染色體中基因因子的排列順序?qū)τ谌旧�體特性的決定是至關(guān)重要的。重排序的目的就是查找更具有進(jìn)化潛力的基因因子序列。在路由優(yōu)化中,如果進(jìn)行重排序運(yùn)算,有可能會(huì)發(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í),數(shù)據(jù)包就被緩存以等待最短路徑修復(fù),這種路由策略并不高效,不能很好的反映網(wǎng)絡(luò)的動(dòng)態(tài)性,也難以有效的實(shí)現(xiàn)網(wǎng)絡(luò)負(fù)載的分擔(dān),從而使得數(shù)據(jù)包在網(wǎng)絡(luò)中的實(shí)際傳輸時(shí)間與期望值差別很大,網(wǎng)絡(luò)帶寬利用率低、傳輸延遲大和傳輸總費(fèi)用高。寬帶網(wǎng)絡(luò)中數(shù)據(jù)傳輸?shù)穆酚蓛?yōu)化問(wèn)題是寬帶網(wǎng)絡(luò)設(shè)計(jì)的重點(diǎn)之一,未來(lái)的智能路由器應(yīng)該能夠適應(yīng)動(dòng)態(tài)變化的網(wǎng)絡(luò),使數(shù)據(jù)包得以避免擁塞從而獲取各方面的優(yōu)勢(shì)。遺傳算法可以很方便的和現(xiàn)存路由協(xié)議結(jié)合起來(lái),對(duì)通信網(wǎng)中的路由算法進(jìn)行優(yōu)化,以獲得通信網(wǎng)的最佳路由。比如OSPF(開(kāi)放式最短路徑優(yōu)先協(xié)議)中每個(gè)參與路由器都有網(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);//臨時(shí)保存子集群

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

　　在這個(gè)通信網(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ī)則。針對(duì)該網(wǎng)絡(luò)的優(yōu)化問(wèn)題我們制定規(guī)則如下：

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

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

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

　　4、突變運(yùn)算中,以塊為單位進(jìn)行突變；無(wú)效主干傳輸線因子可自動(dòng)優(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郈郋郌。在這個(gè)例子中,遺傳算法的計(jì)算過(guò)程大概僅需要3個(gè)運(yùn)算循環(huán)15 ~ 18次運(yùn)算就可以完成,如果使用Dijkstra算法進(jìn)行運(yùn)算,那么所用的時(shí)間復(fù)雜性為n(n—1) 3/2,即n2量級(jí),在這個(gè)例子中就需要7個(gè)運(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)化是一個(gè)復(fù)雜且涉及范圍廣泛的課題,是寬帶通信網(wǎng)絡(luò)技術(shù)中不可缺少的部分。網(wǎng)絡(luò)優(yōu)化的傳統(tǒng)方法有很多,比如梯度法、爬山法、模擬退火算法、列表尋優(yōu)法等,但是他們的局限性也非常大,算法也比較復(fù)雜,在許多限制條件下不能有效的發(fā)揮作用。遺傳算法由于其高效、快速等優(yōu)點(diǎn)成為眾多方法中比較好的一種�？梢栽谶z傳算法中融合其它優(yōu)化方法的思想,構(gòu)成一種混合遺傳算法�；�于遺傳算法的網(wǎng)絡(luò)優(yōu)化方法是網(wǎng)絡(luò)優(yōu)化發(fā)展的主要方向之一。本文對(duì)遺傳算法在網(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]周明、孫樹(shù)棟：《遺傳算法原理及應(yīng)用》,國(guó)防工業(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]陳國(guó)良等：《遺傳算法及其應(yīng)用》,人民郵電出版社,1996

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