一種基于改進(jìn)遺傳算法的波長(zhǎng)路由算法

鄧沌華，劉秋兵2，李 蔚

（1.湖北經(jīng)濟(jì)學(xué)院信息管理學(xué)院，武漢 430205； 2.北方自動(dòng)控制技術(shù)研究所，太原 030062；3.華中科技大學(xué)武漢國(guó)家光電實(shí)驗(yàn)室，武漢 430074）

一種基于改進(jìn)遺傳算法的波長(zhǎng)路由算法

鄧沌華1，劉秋兵2，李 蔚3

（1.湖北經(jīng)濟(jì)學(xué)院信息管理學(xué)院，武漢 430205； 2.北方自動(dòng)控制技術(shù)研究所，太原 030062；3.華中科技大學(xué)武漢國(guó)家光電實(shí)驗(yàn)室，武漢 430074）

WDM（波分復(fù)用）光網(wǎng)絡(luò)中基于GA（遺傳算法）的RWA（路由與波長(zhǎng)分配）算法是目前最常見的算法，為了提高網(wǎng)絡(luò)資源利用率并進(jìn)一步降低阻塞率，提出了一種動(dòng)態(tài)的、基于改進(jìn)GA的DCMA-GA（雙交叉變異自適應(yīng)遺傳算法），通過引入自適應(yīng)交叉與變異概率機(jī)制來減少GA的復(fù)雜度并應(yīng)用于波長(zhǎng)分配子算法中。仿真結(jié)果表明，與經(jīng)典算法Dijkstra+FF（首次命中）相比，新算法最大能降低50%的阻塞率，在波長(zhǎng)分配方面可提高10%的性能，驗(yàn)證了新算法的有效性。

波分復(fù)用；改進(jìn)遺傳算法；路由與波長(zhǎng)分配；雙交叉變異；自適應(yīng)

0　引 言

RWA（路由與波長(zhǎng)分配）的本質(zhì)是為請(qǐng)求的連接尋找合適的路由并分配適當(dāng)?shù)牟ㄩL(zhǎng)。在當(dāng)前技術(shù)條件下，網(wǎng)絡(luò)越復(fù)雜，RWA問題的優(yōu)化越關(guān)鍵，如果RWA耗時(shí)較多，則無法準(zhǔn)確及時(shí)地建立光鏈路［1-2］。目前對(duì)于波長(zhǎng)分配子問題的求解主要有3類算法，即基于局部信息、全局資源信息和全局通路信息的波長(zhǎng)分配算法，而常見的波長(zhǎng)分配算法主要有最大總和算法、最小影響算法、RCL（相對(duì)容量損失）算法以及RLI（相對(duì)最小影響）算法等［3-8］。其中，RCL和RLI算法的性能相對(duì)較好，且后者比前者描述網(wǎng)絡(luò)狀態(tài)更加準(zhǔn)確，也是當(dāng)前重點(diǎn)研究和應(yīng)用的波長(zhǎng)分配算法。

而GA（遺傳算法）自1975年被提出至今已有近40年歷史，基于GA對(duì)RWA算法進(jìn)行改進(jìn)，再有所創(chuàng)新和突破完全可期。本文提出了一種動(dòng)態(tài)的、基于改進(jìn)GA的DCMA-GA（雙交叉變異自適應(yīng)遺傳算法），通過引入自適應(yīng)交叉與變異概率機(jī)制來降低GA的復(fù)雜度，并應(yīng)用于波長(zhǎng)分配子算法中。

1　RWA改進(jìn)算法

對(duì)于WDM（波分復(fù)用）光網(wǎng)絡(luò)中的RWA問題，DCMA-GA是一種改進(jìn)型求解算法，主要改進(jìn)在于GA的染色體的設(shè)計(jì)，其染色體由波長(zhǎng)和路徑編號(hào)序列混合組成，長(zhǎng)度動(dòng)態(tài)增長(zhǎng)，并采用雙交叉變異遺傳操作，變異概率采用自適應(yīng)機(jī)制。另外，在GA的適應(yīng)度函數(shù)計(jì)算公式中引入了高效的RLI波長(zhǎng)分配算法，可以加快GA收斂，同時(shí)得到RWA的兩個(gè)最優(yōu)解。

1.1編碼策略和相關(guān)的原則

圖1所示為DCMA-GA的染色體編碼形式，其采用波長(zhǎng)編號(hào)與路由節(jié)點(diǎn)序列組合的可變長(zhǎng)編碼方式。

圖1　DCMA-GA的染色體編碼形式

波長(zhǎng)編號(hào)和節(jié)點(diǎn)編號(hào)在程序初始化時(shí)賦給固定的值，運(yùn)行過程中，編號(hào)保持不變。首先對(duì)全網(wǎng)中的所有波長(zhǎng)按長(zhǎng)度排序，對(duì)應(yīng)λ1～λm，m為可用波長(zhǎng)總數(shù)。節(jié)點(diǎn)編號(hào)是拓?fù)渲兴泄?jié)點(diǎn)的索引編號(hào)，對(duì)應(yīng)節(jié)點(diǎn)1至節(jié)點(diǎn)n，n為拓?fù)渲泄?jié)點(diǎn)總數(shù)。

編碼方式應(yīng)滿足完備性、健全性、非冗余性、緊致性和可擴(kuò)展性的原則。適度函數(shù)的設(shè)計(jì)與選擇也要滿足適應(yīng)性評(píng)分的非負(fù)性、合理與一致性和計(jì)算的簡(jiǎn)單性。

1.2初始種群的生成

GA能否快速有效收斂并得到最優(yōu)解，初始種群分布的廣泛性和多樣性至關(guān)重要。DCMA-GA的解決思路是初始種群中路由部分采用隨機(jī)深度優(yōu)先搜索的方法生成。具體算法如下：

bool Get OnePath（std：：map＜int，bool＞Visited，/*由調(diào)用者提供的節(jié)點(diǎn)訪問記錄表*/Node *A，/*源節(jié)點(diǎn)*/Node*B，/*目的節(jié)點(diǎn)*/ std：：vector＜Node*＞Path/*路徑節(jié)點(diǎn)序列存儲(chǔ)表*/）//成功返回true，此時(shí)Path中為隨機(jī)搜索到的A B的一條路徑，失敗返回false

｛Path.clear（）；Path.push_back（A）；

Visited［A節(jié)點(diǎn)對(duì)應(yīng)的編號(hào)］=true；//設(shè)置A節(jié)點(diǎn)已被訪問過

while（！Path.empty（））

｛cur Node=Path.back（）；

if（cur Node==B）return true；//找到一條路徑

if（cur Node的所有鄰接點(diǎn)都已被訪問過‖cur Node到所有未被訪問過的鄰接點(diǎn)均無可用波長(zhǎng)通道）Path.pop_back（）；

else

｛從cur Node未被訪問過且有可用波長(zhǎng)通道的鄰接點(diǎn)中隨機(jī)選擇一個(gè)；

Path.push_back（選中的新節(jié)點(diǎn)）；

Visited［新節(jié)點(diǎn)對(duì)應(yīng)的編號(hào)］=true；//設(shè)置新節(jié)點(diǎn)已被訪問過｝//else結(jié)束

｝//while結(jié)束

return false；/*尋找路徑失敗*｝//結(jié)束

1.3適應(yīng)度函數(shù)的設(shè)計(jì)

適應(yīng)度函數(shù)是GA對(duì)群體進(jìn)行評(píng)估并作出相應(yīng)選擇的唯一依據(jù)，故適應(yīng)度函數(shù)影響到群體的進(jìn)化質(zhì)量，甚至影響到算法最終能否得到最優(yōu)解。路由選擇的優(yōu)化目標(biāo)為路徑代價(jià)盡量小，這是因?yàn)楣饫w傳輸?shù)拇鷥r(jià)問題仍是光路設(shè)計(jì)時(shí)不可忽略的重要考慮因素之一；波長(zhǎng)分配的優(yōu)化目標(biāo)為對(duì)其他相關(guān)通路的相對(duì)影響盡量小，因?yàn)槠渲苯佑绊懭W(wǎng)的平均阻塞率指標(biāo)。綜合上述兩方面的優(yōu)化目標(biāo)以及適應(yīng)度函數(shù)選擇與設(shè)計(jì)的原則，DCMA-GA的適應(yīng)度函數(shù)可表示為

式中，α、β為修正系數(shù)，主要是為了調(diào)節(jié)F（x）的值以便于統(tǒng)計(jì)，且滿足α＞β＞1；Cost（p*）為路徑對(duì)應(yīng)的代價(jià)函數(shù)，如果不考慮其他QoS（服務(wù)質(zhì)量）約束，該值為組成p*的各鏈路的距離代價(jià)之和；RBC（p*，w）即為RLI算法中定義的“分配波長(zhǎng)給光通路對(duì)全網(wǎng)造成的影響”。

1.4遺傳操作

GA的遺傳操作包括選擇、交叉和變異3個(gè)基本操作算子。為了有效提高GA的性能，DCMAGA引入了自適應(yīng)交叉與變異機(jī)制：根據(jù)染色體編碼方式的特殊性，對(duì)波長(zhǎng)與路徑分別進(jìn)行概率獨(dú)立的交叉與變異操作，即個(gè)體的路徑部分與波長(zhǎng)部分分別以獨(dú)立概率進(jìn)行交叉，但是波長(zhǎng)部分須在路徑部分的可用波長(zhǎng)集范圍內(nèi)交叉。既保證了交叉后不會(huì)出現(xiàn)非法個(gè)體，又盡可能地保證了群體的多樣性，擴(kuò)大了算法的全局搜索空間范圍。完整的DCMAGA描述如下：

（1）對(duì)當(dāng)前請(qǐng)求的源宿節(jié)點(diǎn)利用1.2節(jié)算法生成初始種群oldpop；

（2）設(shè)迭代數(shù)gennum=0；

（3）計(jì)算oldpop的適應(yīng)度，得到適應(yīng)度總和sumfitness以及最佳個(gè)體bestfit；

（4）判斷gennum是否大于maxgen，是則跳轉(zhuǎn)至（9），否則繼續(xù)；

（5）對(duì)oldpop逐對(duì)進(jìn)行遺傳操作，子代個(gè)體對(duì)放入新種群newpop，循環(huán)直到newpop大小達(dá)到popsize；

（6）用bestfit隨機(jī)替換newpop中的一個(gè)個(gè)體；

（7）newpop和oldpop互換指針值；

（8）gennum=gennum+1，轉(zhuǎn)至（3）；（9）bestfit作為算法結(jié)果輸出。

2　仿真結(jié)果與分析

仿真采用14節(jié)點(diǎn)、21條雙向單纖鏈路的NSFNET（美國(guó)國(guó)家科學(xué)基金會(huì)網(wǎng)絡(luò)），其拓?fù)浼版溌反鷥r(jià)如圖2所示。

圖2　NSFNET的仿真拓?fù)鋱D

（1）與Dijkstra+FF（首次命中）算法的比較

圖3所示為DCMA-GA與Dijkstra+FF的性能比較，相較于Dijkstra+FF算法，DCMA-GA性能明顯優(yōu)于經(jīng)典算法。當(dāng)負(fù)載較小時(shí)，二者的阻塞率相似，當(dāng)負(fù)載逐漸增大到80 Erl左右時(shí)，Dijkstra+FF算法的阻塞率明顯增大，原因是：（1）Dijkstra+FF算法在尋找路由時(shí)只考察路徑最短的那條，而在網(wǎng)絡(luò)負(fù)荷較大時(shí)該路由上極有可能已沒有可用波長(zhǎng)，此時(shí)Dijkstra算法的不靈活性導(dǎo)致尋路失??；（2）即使Dijkstra算法可以獲得該最短路由，但由于FF算法在分配波長(zhǎng)時(shí)不會(huì)做某種影響評(píng)估，勢(shì)必會(huì)影響后繼RWA。而DCMA-GA不僅在尋路時(shí)借助GA進(jìn)行全局搜索，在分配波長(zhǎng)時(shí)也借助了RLI算法進(jìn)行全網(wǎng)影響評(píng)估，所得RWA結(jié)果不僅對(duì)當(dāng)前請(qǐng)求較優(yōu)，而且對(duì)后繼其他請(qǐng)求的影響也較小，因此對(duì)全網(wǎng)平均阻塞率的影響較大。

圖3　DCMA-GA與Dijkstra+FF性能比較

當(dāng)網(wǎng)絡(luò)負(fù)荷變大時(shí)，本文所提算法與經(jīng)典算法相比能逐步降低網(wǎng)絡(luò)阻塞率，在網(wǎng)絡(luò)負(fù)荷很大時(shí)，所提算法較經(jīng)典算法最大能降低50%的阻塞率。

（2）與普通GA的比較

圖4所示為DCMA-GA與普通GA的性能對(duì)比圖。由圖可知，在迭代開始階段（前15代），DCMA-GA并沒有表現(xiàn)出比普通GA更好的性能。這主要是由于DCMA-GA采用的自適應(yīng)交叉變異機(jī)制仍處在試探階段，交叉變異概率波動(dòng)較大，算法尚未能快速得到最適合當(dāng)前代群體的交叉變異概率。然而在試探階段結(jié)束后（第20代開始），DCMA-GA迅速向群體更優(yōu)的方向進(jìn)化，體現(xiàn)了算法較好的改進(jìn)性能。這主要是由于自適應(yīng)交叉變異機(jī)制能夠得到更豐富的交叉與變異操作，因此群體的多樣性要好于普通GA。同時(shí)，由于在自適應(yīng)交叉變異機(jī)制中，精英個(gè)體得到保留的概率較大，因此到遺傳進(jìn)化后期（第30代后），DCMA-GA得到的群體平均適應(yīng)度基本穩(wěn)定在3.4，而普通GA則維持在3.0左右，表明DCMA-GA能夠得到更優(yōu)的解，較普通算法能提高10%的優(yōu)化率，改進(jìn)效果較為明顯。

圖4　DCMA-GA與普通GA的性能對(duì)比

3　結(jié)束語

本文提出了一種基于全局通路信息的DCMAGA并應(yīng)用于波長(zhǎng)分配子算法中。通過引入自適應(yīng)交叉與變異概率機(jī)制來降低GA的復(fù)雜度。仿真結(jié)果表明，所提算法能有效地提高算法效率，降低算法的復(fù)雜度，尤其在網(wǎng)絡(luò)的負(fù)荷較大時(shí)，所提算法與經(jīng)典算法Dijkstra+FF相比可降低50%的網(wǎng)絡(luò)阻塞率，在波長(zhǎng)分配方面可提高10%的算法性能。為WDM光網(wǎng)絡(luò)中動(dòng)態(tài)RWA問題的算法研究提供了新的改進(jìn)思路，對(duì)光網(wǎng)絡(luò)的規(guī)劃與優(yōu)化設(shè)計(jì)也具有一定的指導(dǎo)意義。

［1］ 原榮.光纖通信技術(shù)［M］.北京：機(jī)械工業(yè)出版社，2011.

［2］ 顧畹儀，張杰.全光通信網(wǎng)［M］.北京：北京郵電大學(xué)出版社，1999.

［3］ Palais Joseph C.光纖通信［M］.王江平，等譯.第五版.北京：電子工業(yè)出版社，2011.

［4］ Mukherjee B.WDM optical communication networks：progress and challenges［J］.IEEE JSAC，2000，18 （10）：1810-1824.

［5］ 孫雪榮.光網(wǎng)絡(luò)路由選擇及波長(zhǎng)分配算法［D］.西安：西安電子科技大學(xué)，2011.

［6］ 徐世中，王展，李樂民.DWDM光傳送網(wǎng)中選路和波長(zhǎng)分配［J］.通信學(xué)報(bào)，2001，24（4）：51-56.

［7］ 張百成，高隨祥.WDM光網(wǎng)絡(luò)動(dòng)態(tài)路由和波長(zhǎng)分配算法［J］.微型機(jī)與應(yīng)用，2005，（11）：37-39.

［8］ 李蔚.波長(zhǎng)路由光網(wǎng)絡(luò)中快速動(dòng)態(tài)光鏈路建立的研究［D］.武漢：華中科技大學(xué)，2006.

A RWA Algorithm Based on Improved Genetic Algorithm

DENG Zhuan-hua1，LIU Qiu-bing2，LI Wei3
（1.College of Information Management，Hubei University of Economics，Wuhan 430205，China；2.North Automatic Control Technology Research Institute，Taiyuan 030062，China 3.Wuhan National Laboratory for Optoelectronics，Wuhan 430074，China）

In WDM optical networks，the routing selection algorithm based on GA and wavelength assignment algorithm are widely used.In order to further optimize the routing and wavelength assignment in WDM optical network，a dynamic RWA algorithm named Double Crossover and Mutation Adaptive-Genetic Algorithm（DCMA-GA）for WDM network based on improved GA is proposed.Through simulation，the new algorithm can reduce the network blocking rate by 50%when the network load is big.The efficiency of algorithm can also be improved by 10%when compared with the normal genetic RWA algorithm.

WDM；improved GA；RWA；double crossover and mutation；adaptive

TN929

A

1005-8788（2016）04-0019-03

10.13756/j.gtxyj.2016.04.006

2016-04-16

國(guó)家自然科學(xué)基金資助項(xiàng)目（61177063）

鄧沌華（1976-），女，湖北武漢人。副教授，碩士，主要研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)。