[發明專利]一種基于遺傳算法的光多播樹最小代價路由方法

有效

• 申請號: 201310606366.9
• 申請日: 2013-11-25
• 公開（公告）號: CN103685020B
• 公開（公告）日: 2017-07-28
• 發明（設計）人: 劉煥淋;秦亮;陳高翔;代洪躍;徐一帆
• 申請（專利權）人: 重慶郵電大學
• 主分類號: H04L12/721
• 分類號: H04L12/721;H04L12/761
• 代理公司: 重慶市恒信知識產權代理有限公司50102
• 代理人: 劉小紅

1.一種基于遺傳算法的光多播樹最小代價路由方法，其特征在于，包括以下步驟：

101、獲取網絡拓撲G(V，E)，其中V表示網絡拓撲G的節點集，E表示網絡中節點之間的連接邊，當連接邊的容量n≥2時，則將該連接邊轉化為n條并列且容量為1的邊，完成初始化，跳轉至步驟102；

102、獲取步驟101中經過初始化后網絡拓撲G(V，E)的源節點S及目的節點集t，構造源節點S到目的節點集t的多播樹，確定源節點S到目的節點集t的最大多播速率T，并設定目的節點的接收速率為k，其中1≤k≤T；獲取源節點S到目的節點t_i所有存在的N條路徑，其中目的節點t_i為目的節點集t中的一個元素，計算出該目的節點t_i的k條邊路徑組合的方式，產生基因庫,并采用遺傳算法構造源節點S到目的節點集t的染色體種群,每個染色體表示網絡的一種路由方式,其中每個染色體由與目的節點的個數相等的U個基因組成，每個基因表示源節點S到對應目的節點t_i的一種路徑；

103、構造步驟102中染色體的適應度函數

f＝a₁*NC(R)+a₂*N_CL,且a₁>a₂

式中，f為適應度函數值；NC(R)為滿足多播請求速率的多播樹的鏈路代價，N_CL為編碼鏈路數目；a₁、a₂為權重系數；

當適應度函數f根據遺傳算法迭代更新的次數大于或者等于設定次數N1時即對應最優染色體，則輸出該最優染色體的路徑及適應度函數值f，跳轉至步驟106；或當適應度函數f根據遺傳算法迭代更新的次數大于N2且適應度函數值f不變時，則輸出該最優染色體的路徑及適應度函數值f，跳轉至步驟106，結束；否則，跳轉至步驟104；

104、采用比例選擇法對步驟103中的染色體加入到初始染色體種群中，并依次經過交叉步驟、變異步驟求得最優染色體及適應度函數值；

105、對步驟104中求得的最優染色體及適應度函數值代入步驟102建立的染色體種群中，刪除掉適應度函數值大于該最優染色體適應度函數值的基因；

106、輸出最終的最優染色體及其適應度值，并按照該最優染色體所代表的源節點到目的節點的路徑進行路由。

2.根據權利要求1所述的一種基于遺傳算法的光多播樹最小代價路由方法，其特征在于：步驟104中的比例選擇法為輪盤選擇或蒙特卡羅選擇法。

3.根據權利要求1所述的一種基于遺傳算法的光多播樹最小代價路由方法，其特征在于，步驟104中的交叉步驟包括：

A1、隨機選取2個染色體作為父代染色體；

A2、對染色體中的每一個基因產生一個0到1之間隨機數字，用于隨機判斷2個父代染色體是否進行交叉操作；

A3、當步驟A2中隨機產生的數字小于p_c時，2個染色體進行染色體交叉產生2個子代染色體，判斷步驟A2隨機產生的數字是否小于p_c，若該隨機值小于p_c，則將2個父代染色體中對應的基因進行互換；否則，2個父代染色體中對應的基因保持不變；其中p_c為交叉概率，其中交叉概率p_c取值范圍為0.6～0.98；

A4、判斷步驟A3中產生的子代染色體的適應度函數值是否小于父代染色體的適應度函數值，若是，跳轉至步驟A5；

A5、用子代染色體代替父代中適應度函數值較大的父代染色體。

4.根據權利要求1所述的一種基于遺傳算法的光多播樹最小代價路由方法，其特征在于，步驟104中的變異步驟包括：

B1、選擇一個染色體，對染色體中的每一個基因產生一個0到1之間隨機數字；

B2、判斷步驟B1中每個基因的隨機數字是否小于變異概率p_m，若是，在該目的節點對應的基因庫中隨機選擇一個整數代替原始基因位上的數字，即選擇另一種邊分離路徑組合方式；否則，該基因位上的數字保持不變。