[發(fā)明專利]基于遺傳算法的備用路由配置方法及系統(tǒng)

在審

• 申請?zhí)枺?/td>: 201810220279.2
• 申請日: 2018-03-16
• 公開（公告）號: CN108494678A
• 公開（公告）日: 2018-09-04
• 發(fā)明（設(shè)計）人: 張強;胡心亭;宋彥斌;甄巖;鄢志平;李財云;趙沖;劉全春
• 申請（專利權(quán)）人: 北京智芯微電子科技有限公司;國網(wǎng)信息通信產(chǎn)業(yè)集團有限公司;國家電網(wǎng)公司;國網(wǎng)甘肅省電力公司
• 主分類號: H04L12/711
• 分類號: H04L12/711;H04L12/24;G06N3/12
• 代理公司: 北京中譽威圣知識產(chǎn)權(quán)代理有限公司 11279
• 代理人: 周際;俞佳

1.一種基于遺傳算法的備用路由配置方法，其特征在于，包括以下步驟：

建立電力通信網(wǎng)絡(luò)的備用路由配置的數(shù)學(xué)模型；以及

基于遺傳算法求解最終的備用路由配置路徑。

2.根據(jù)權(quán)利要求1所述的基于遺傳算法的備用路由配置方法，其特征在于，所述建立電力通信網(wǎng)絡(luò)的備用路由配置的數(shù)學(xué)模型包括：

定義電力通信網(wǎng)絡(luò)的拓?fù)鋱D；

定義電力通信網(wǎng)絡(luò)的業(yè)務(wù)集合；

設(shè)置所述備用路由配置的優(yōu)化目標(biāo)；以及

設(shè)置所述備用路由配置的約束條件。

3.根據(jù)權(quán)利要求2所述的基于遺傳算法的備用路由配置方法，其特征在于，所述拓?fù)鋱D為G(V,E)，其中V＝{v₁,v₂,……v_n}代表節(jié)點的集合，該節(jié)點代表所述電力通信網(wǎng)絡(luò)的工作站點，E＝{e₁,e₂,……e_m}代表通信鏈路的集合，兩點之間的路徑表示為P_ij，所述電力通信網(wǎng)絡(luò)的起點和終點分別為v_i和v_j。

4.根據(jù)權(quán)利要求3所述的基于遺傳算法的備用路由配置方法，其特征在于，所述業(yè)務(wù)集合為S＝{s₁,s₂,……，s_k}，其中單個業(yè)務(wù)s_i包括五種屬性(start,end,path,path^*,d_i)，所述五種屬性依次分別代表業(yè)務(wù)的起點、終點、業(yè)務(wù)的主路由路徑、備用路由路徑、業(yè)務(wù)重要度。

5.根據(jù)權(quán)利要求4所述的基于遺傳算法的備用路由配置方法，其特征在于，所述優(yōu)化目標(biāo)是替業(yè)務(wù)集合S找到一套備用路徑組合使得所有鏈路上的通道壓力的均衡度M值最小，

其中，所述通道壓力均衡度M的計算公式為：其中Pr(e_ij)代表鏈路e_ij的通道壓力，計算公式為Pr(e_ij)＝EBI_ij×EI_ij，EBI_ij代表鏈路e_ij的所有業(yè)務(wù)重要度總和，EI_ij代表鏈路自身重要度。

6.根據(jù)權(quán)利要求2所述的基于遺傳算法的備用路由配置方法，其特征在于，所述備用路由配置的約束條件包括：

單向時延指標(biāo)，任意一條可選路由的時延t都不能高于閾值T；以及

相交度指標(biāo)，任意一條可選備用路由與主路由均不相交。

7.根據(jù)權(quán)利要求4所述的基于遺傳算法的備用路由配置方法，其特征在于，基于遺傳算法求解最終的備用路由配置路徑包括以下步驟：

初始化電力通信網(wǎng)以及遺傳算法的相關(guān)參數(shù)；

將業(yè)務(wù)的一條路徑用一條染色體來表示，對遺傳算法的染色體進行編碼，染色體上的基因位代表路徑所經(jīng)過的節(jié)點，染色體個數(shù)等于業(yè)務(wù)數(shù)，將多條染色體組合起來構(gòu)成一個基因組代表網(wǎng)絡(luò)中所有業(yè)務(wù)的備用路徑的一套組合方案，基因組在交叉變異中保持同步；

對于基因組計算其適應(yīng)度函數(shù)值，采用精英保留策略，將本代中適應(yīng)度函數(shù)值最高的個體直接復(fù)制到下一代；

依照適應(yīng)度函數(shù)值，按照輪盤賭選擇算法選擇基因組復(fù)制到新群體；

依照概率隨機選擇多對基因組進行交叉并存入新群體；

依照概率隨機選擇多個基因組進行變異并存入新群體；

判斷循環(huán)代數(shù)是否達到設(shè)定值，若循環(huán)代數(shù)已達到設(shè)定值，選擇最新一次循環(huán)中適應(yīng)度函數(shù)值最高的一組基因組輸出作為最優(yōu)解，否則返回繼續(xù)進行遺傳算法；以及

將輸出的最優(yōu)解進行解碼后得到最終的備選路由配置路徑。

8.根據(jù)權(quán)利要求7所述的基于遺傳算法的備用路由配置方法，其特征在于，所述適應(yīng)度函數(shù)為其中Z為一個足夠大的數(shù)，使得適應(yīng)度函數(shù)始終為正值；種群中的個體是以一個基因組為單位，其個體適應(yīng)度函數(shù)為組內(nèi)所有染色體的適應(yīng)度函數(shù)值的總和f＝∑f(s)。