鄧沌華，劉秋兵2，李 蔚

（1.湖北經(jīng)濟學院信息管理學院，武漢 430205； 2.北方自動控制技術研究所，太原 030062；3.華中科技大學武漢國家光電實驗室，武漢 430074）

一種基于改進遺傳算法的波長路由算法

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

（1.湖北經(jīng)濟學院信息管理學院，武漢 430205； 2.北方自動控制技術研究所，太原 030062；3.華中科技大學武漢國家光電實驗室，武漢 430074）

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

波分復用；改進遺傳算法；路由與波長分配；雙交叉變異；自適應

0　引 言

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

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

1　RWA改進算法

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

1.1編碼策略和相關的原則

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

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

波長編號和節(jié)點編號在程序初始化時賦給固定的值，運行過程中，編號保持不變。首先對全網(wǎng)中的所有波長按長度排序，對應λ1～λm，m為可用波長總數(shù)。節(jié)點編號是拓撲中所有節(jié)點的索引編號，對應節(jié)點1至節(jié)點n，n為拓撲中節(jié)點總數(shù)。

編碼方式應滿足完備性、健全性、非冗余性、緊致性和可擴展性的原則。適度函數(shù)的設計與選擇也要滿足適應性評分的非負性、合理與一致性和計算的簡單性。

1.2初始種群的生成

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

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

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

Visited［A節(jié)點對應的編號］=true；//設置A節(jié)點已被訪問過

while（！Path.empty（））

｛cur Node=Path.back（）；

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

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

else

｛從cur Node未被訪問過且有可用波長通道的鄰接點中隨機選擇一個；

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

Visited［新節(jié)點對應的編號］=true；//設置新節(jié)點已被訪問過｝//else結束

｝//while結束

return false；/*尋找路徑失敗*｝//結束

1.3適應度函數(shù)的設計

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

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

1.4遺傳操作

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

（1）對當前請求的源宿節(jié)點利用1.2節(jié)算法生成初始種群oldpop；

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

（3）計算oldpop的適應度，得到適應度總和sumfitness以及最佳個體bestfit；

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

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

（6）用bestfit隨機替換newpop中的一個個體；

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

（8）gennum=gennum+1，轉至（3）；（9）bestfit作為算法結果輸出。

2　仿真結果與分析

仿真采用14節(jié)點、21條雙向單纖鏈路的NSFNET（美國國家科學基金會網(wǎng)絡），其拓撲及鏈路代價如圖2所示。

圖2　NSFNET的仿真拓撲圖

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

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

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

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

（2）與普通GA的比較

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

圖4　DCMA-GA與普通GA的性能對比

3　結束語

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

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

［2］ 顧畹儀，張杰.全光通信網(wǎng)［M］.北京：北京郵電大學出版社，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)絡路由選擇及波長分配算法［D］.西安：西安電子科技大學，2011.

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

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

［8］ 李蔚.波長路由光網(wǎng)絡中快速動態(tài)光鏈路建立的研究［D］.武漢：華中科技大學，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

國家自然科學基金資助項目（61177063）

鄧沌華（1976-），女，湖北武漢人。副教授，碩士，主要研究方向為計算機網(wǎng)絡。