一種基于遺傳算法的通信網(wǎng)拓?fù)鋬?yōu)化方法*

尹夢夢，王 磊，姚昌華，童 瑋

（1.陸軍工程大學(xué)，江蘇 南京 210001；2.南京信息工程大學(xué)，江蘇 南京 210044）

0 引言

通信網(wǎng)[1]的網(wǎng)絡(luò)結(jié)構(gòu)（即網(wǎng)絡(luò)拓?fù)洌┦欠褐妇W(wǎng)絡(luò)節(jié)點和傳輸線路的幾何連接形狀，關(guān)系著網(wǎng)絡(luò)連通性問題[2]。從網(wǎng)絡(luò)的內(nèi)部結(jié)構(gòu)屬性出發(fā)，探究具有較高可靠性的通信網(wǎng)，在各種實際應(yīng)用中是一項重要需求。

目前，關(guān)于通信網(wǎng)可靠性的研究已取得了不少成果。文獻[3]提出了實現(xiàn)導(dǎo)航共享的通信網(wǎng)絡(luò)拓?fù)鋬?yōu)化方法，為尋找不同條件下具有最小通信連接數(shù)（Minimum of Communication Connections Number，MCCN）的通信網(wǎng)絡(luò)拓?fù)浣⒘藢?dǎo)航共享的MCCN 拓?fù)淠Ｐ?，并設(shè)計了相應(yīng)方法，理論上證明了算法的有效性。文獻[4]提出了一種基于服務(wù)特性和節(jié)點可靠性的電力通信網(wǎng)絡(luò)故障恢復(fù)算法，通過與傳統(tǒng)算法的比較，驗證了該算法提高了電力通信網(wǎng)絡(luò)的故障恢復(fù)率和收益，具有很大的實際應(yīng)用價值。文獻[5]利用FCM 算法對電力通信網(wǎng)的關(guān)鍵資源進行識別和備份，從而提升了電力通信網(wǎng)的可靠性。文獻[6]以復(fù)雜網(wǎng)絡(luò)為研究對象，建立了基于冗余度的網(wǎng)絡(luò)可靠性及節(jié)點重要度評估模型。結(jié)果表明，該模型算法能為一定約束成本限制下高可靠性網(wǎng)絡(luò)的構(gòu)造問題提供解決方案。

本文從通信網(wǎng)拓?fù)浣Y(jié)構(gòu)的角度構(gòu)建可靠性優(yōu)化模型。該模型屬于NP-hard 問題，直接求解難度大。本文針對目標(biāo)函數(shù)設(shè)計了改進的遺傳算法求解該模型，是一種啟發(fā)式方法。編碼過程即網(wǎng)絡(luò)轉(zhuǎn)化為鄰接矩陣的過程，設(shè)計的優(yōu)化變量是以圖的鄰接矩陣形式進行編碼。選用輪盤賭、截斷和排序分組3 種選擇操作，使用單點交叉算子在交叉位進行交叉操作，采用單點變異的變異操作。通過仿真實驗，驗證了本算法能有效提升通信網(wǎng)的可靠性。

1 基于自然連通度的通信網(wǎng)可靠性優(yōu)化模型

本文以自然連通度作為網(wǎng)絡(luò)可靠性測度指標(biāo)優(yōu)化其拓?fù)浣Y(jié)構(gòu)。

對通信網(wǎng)圖G的基本假設(shè)如下。

（1）通信網(wǎng)是無權(quán)圖且為無向簡單圖，因此aij的取值集合為{aij=aji=1|e(vi,vj)∈E(G)}和{aij=aji=0|e(vi,vj)?E(G)}。

（2）滿足連通圖，即其拉普拉斯矩陣的次小特征根μ＞0。當(dāng)網(wǎng)絡(luò)規(guī)模增大時，次小特征根求解時間過長。為了簡便處理，本文定義函數(shù)：

C(G)通過深度優(yōu)先搜索為每一個節(jié)點進行遍歷，遍歷所有節(jié)點其結(jié)果都能連通任意其他節(jié)點。所的圖即為連通圖，否則為非連通圖。

定義自然連通度，即假設(shè)在一個網(wǎng)絡(luò)中，任意節(jié)點vi和vj之間的長度為k的途徑數(shù)目為，然后通過i、j、k的關(guān)系求和：

S值的大小反映了網(wǎng)絡(luò)中冗余路徑數(shù)量的多少。顯然，S將是一個復(fù)雜的表達(dá)式，采用起點和終點為長度為k的閉途徑數(shù)目表示如下：

將S除以節(jié)點間長度為k的階乘來衡量閉路徑的貢獻，其中較短的閉路徑對替代路徑的冗余性影響較大，表示如下：

此時，nk表示網(wǎng)絡(luò)中所有長度為k的閉途徑數(shù)目，可表示為：

代回式（4），可得：

式中，λi代表該網(wǎng)絡(luò)鄰接矩陣的特征根。

影響網(wǎng)絡(luò)可靠性的因素很多。在網(wǎng)絡(luò)節(jié)點數(shù)量一定的情況下，網(wǎng)絡(luò)中鏈路數(shù)量成為主要影響因素。自然連通度值關(guān)于增邊是嚴(yán)格單調(diào)遞增的，在對網(wǎng)絡(luò)鏈路數(shù)量沒有限制的情況下，全連接網(wǎng)絡(luò)拓?fù)鋵⑹强煽啃宰顑?yōu)的網(wǎng)絡(luò)。但是，事實上，網(wǎng)絡(luò)構(gòu)造會受到成本等限制，顯然鏈路數(shù)越多的網(wǎng)絡(luò)成本也將越大。因此，在鏈路數(shù)W一定的情況下，研究網(wǎng)絡(luò)可靠性問題是必要的。本文假設(shè)通信網(wǎng)鏈路數(shù)量滿足的約束條件如下：

由上述分析可建立通信網(wǎng)拓?fù)浣Y(jié)構(gòu)優(yōu)化模型：

式中，λi為以aij組成的鄰接矩陣A(G)的特征根。

2 基于遺傳算法的通信網(wǎng)可靠性仿真優(yōu)化方法

上述模型屬于非線性0-1 整數(shù)規(guī)劃問題，是典型的NP-hard 問題，無法使用目前的一些求解器直接進行求解。傳統(tǒng)解決NP-hard 問題的方法包括使用相似問題替代原問題，即原問題復(fù)雜難求，不能直接求解，尋找相似度高且易于求解的問題進行替代。另一種方法是利用啟發(fā)式搜索。本文優(yōu)先選擇群智能算法。由于網(wǎng)絡(luò)圖的鄰接矩陣為0-1 矩陣，為了編碼方式的便捷性，本文選擇遺傳算法進行問題的搜索，流程如圖1 所示。

圖1 遺傳算法流程

2.1 變量編碼

通信網(wǎng)可表示為無權(quán)、無向簡單圖，而圖本身可以用0-1 鄰接矩陣表示，很合適將其直接當(dāng)做染色體。因此，每個鄰接矩陣為遺傳算法的優(yōu)化變量，即解的編碼。

2.2 選擇操作

為了尋找可靠性更高的通信網(wǎng)拓?fù)浣Y(jié)構(gòu)，在每一次選擇操作中依據(jù)目標(biāo)函數(shù)值選擇結(jié)果較大的個體。本文中分別選用輪盤賭選擇、截斷選擇法、排序分組3 種不同的操作進行對比與分析。

截斷選擇法根據(jù)目標(biāo)函數(shù)值大小對種群中的個體進行降序排列（求解max），選取前n個個體進入下一代，算法操作如下：

（1）在初始種群中計算每個個體（鄰接矩陣）的目標(biāo)函數(shù)值；

（2）按照適應(yīng)度值大小進行降序排列；

（3）截取前n個最好的個體進入下一代。

排序分組選擇的思想用圖形表示如下。

（1）以個體數(shù)為9 的一個初始種群為例，表1中數(shù)據(jù)為種群個體適應(yīng)度值。

表1 個體數(shù)為9 的一個初始種群的個體適應(yīng)度值

（2）種群個體按適應(yīng)度值由大到小進行排列，如表2 所示。

表2 適應(yīng)度值由大到小進行排列的結(jié)果

（3）排列好的個體平均截取3 段。

（4）每段分別按不同的比例進行隨機選擇。

（5）選擇出來的個體如表3 所示。

表3 選擇出來的個體情況

（6）從頭段中選取由于選擇操作而損失的個體。

（7）將第（3）步選出的頭部個體插入第（5）步中組合成新的個體，結(jié)果如表4 所示。

表4 選擇出來的個體情況

最終種群與初始種群相比，平均適應(yīng)度值都得到了提高。本文選用的3 種選擇算法操作簡便，在計算出適應(yīng)度值后只需進行排序、分組、插入等一些基本的操作可選出較優(yōu)個體。

2.3 交叉操作

選取不同的鄰接矩陣交換矩陣中間元素實現(xiàn)在該交叉位置對其進行基因位變換，具體操作步驟 如下：

（1）對種群個體進行隨機配對操作；

（2）針對配對的染色體設(shè)定相同的位置交叉點；

（3）依照設(shè)定的交叉概率P進行相互配對。

交叉過程如圖2 所示。

圖2 交叉過程

2.4 變異操作

本文主要采用單點變異，即只需要對基因序列中某一個位進行變異。以二進制編碼為例，即0 變?yōu)?，1 變?yōu)?。變異是從種群中隨機選擇個體按一定概率變異得到新個體的過程。例如，對某個個體進行變異，方法如下：

式中，X[i][j]為鄰接矩陣中某一元素，p是位于[0，1]之間的隨機數(shù)，vc是變異概率。

3 算法改進及模型約束

3.1 算法改進

傳統(tǒng)的遺傳算法容易出現(xiàn)收斂速度慢的問題，本文改進了局部尋優(yōu)策略，具體如下。

3.1.1 局部搜索

在每一次迭代結(jié)束后，對種群中的每一個染色體進行局部搜索優(yōu)化。局部搜索具體操作為對當(dāng)前染色體所表示的鄰接矩陣的任意一位取反操作，可表示為函數(shù)N(Gk)。局部搜索對染色的更新具體表示為：

式中，F(xiàn)(Gk)表示染色體的適應(yīng)度，固定每個染色體的局部優(yōu)化次數(shù)，如50 次。

3.1.2 參數(shù)自適應(yīng)

為了同時保證算法在訓(xùn)練時前期的多樣性和后期的集中性，本文對交叉概率Pc和變異概率Vc做自適應(yīng)性的調(diào)整：

式中，ρ1和ρ2分別是小于1 的常數(shù)，i表示迭代次數(shù)。

3.2 模型約束

優(yōu)化模型含有大量的約束條件，且多數(shù)為較強的約束，如對圖的邊的數(shù)目的限制為常數(shù)。此類約束將使得多數(shù)染色體不符合條件而被淘汰，在前期的迭代中導(dǎo)致子代染色體數(shù)目過少甚至為0。因此，本文使用修復(fù)不可行解和懲罰函數(shù)法對問題約束條件進行處理，具體如下。

3.2.1 網(wǎng)絡(luò)圖的無向簡單圖約束

在種群初始化、交叉、變異和局部優(yōu)化中，均可能造成圖的鄰接矩陣不滿足無向簡單圖約束，如aij≠aji。因此，本文在每次涉及到改變圖結(jié)構(gòu)的操作后，對鄰接矩陣進行逐行掃描修復(fù)。

3.2.2 網(wǎng)絡(luò)圖的邊數(shù)目約束

由于幾乎任何操作都將會改變圖的邊的數(shù)目，因此本文選擇對圖進行不可行解的修復(fù)。具體的修復(fù)方式如下。

假設(shè)邊的數(shù)目為：

若W′-W>0，則隨機選擇鄰接矩陣中的?W個元素{a1,a2,…,a?W}。集合中的每一個元素值都為1，且在原鄰接矩陣中的下標(biāo)均滿足j≥i。將集合中的元素的值變?yōu)?，而后做滿足式（1）中的無向簡單圖修復(fù)操作。反之，若W′-W<0，做相反操作。

3.2.3 圖的連通性約束

對于圖的連通性的修復(fù)較為困難，另外經(jīng)過實驗發(fā)現(xiàn)隨機生成的圖是連通圖的概率在95＆以上，意味著只有較少數(shù)的圖不是連通圖。因此，在訓(xùn)練過程中，如果解不滿足連通性約束，則放棄此解。即使用懲罰函數(shù)法，對不滿足約束的解，其適應(yīng)度值設(shè)為負(fù)無窮。

4 仿真實驗及分析

4.1 優(yōu)化拓?fù)浣Y(jié)構(gòu)的實驗仿真

為了驗證提出的網(wǎng)絡(luò)拓?fù)鋬?yōu)化算法的有效性，在仿真運行環(huán)境為64 位Windows10 操作系統(tǒng)、Python3.8、處理器為Intel i7 9570H、主頻2.6 GHz、內(nèi)存16 GB 的情況下進行實驗，參數(shù)設(shè)置如表5 所示。首先，構(gòu)造初始通信網(wǎng)得到其鄰接矩陣。其次，通過表1 設(shè)置的參數(shù)進行遺傳算法的初始化。最后，根據(jù)第4 節(jié)遺傳算法的步驟得到自然連通度的最 優(yōu)值。

表5 參數(shù)設(shè)置

4.2 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)分析

仿真過程中，選用ER 隨機圖為研究對象?；緟?shù)中，定義節(jié)點數(shù)N=50，邊連接概率p=0.12。生成的ER 網(wǎng)絡(luò)（連通圖）拓?fù)浣Y(jié)構(gòu)與度分布，如圖3 所示。

圖3 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)與度分布

在保持網(wǎng)絡(luò)節(jié)點數(shù)和鏈路數(shù)不變的情況下，優(yōu)化前后的通信網(wǎng)拓?fù)浣Y(jié)構(gòu)及度分布分別如圖3 和 圖4 所示。隨著迭代次數(shù)的增加，自然連通度值都明顯呈上升趨勢，如圖5 所示。因此，遺傳算法可用于求解通信網(wǎng)拓?fù)鋬?yōu)化模型，且運用了算法收斂速度快等優(yōu)點。

圖4 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)與度分布

由仿真結(jié)果分析可得到以下基本結(jié)論。

（1）仿真分析驗證了通信網(wǎng)拓?fù)浣Y(jié)構(gòu)優(yōu)化模型的有效性和采用遺傳算法求解該模型的可行性。由圖5 可得，隨著迭代次數(shù)的增加，自然連通度值呈上升趨勢，最優(yōu)結(jié)果在第100 次迭代達(dá)到7.6，說明網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可靠性得到增強。

（2）經(jīng)遺傳算法優(yōu)化后，改變了通信網(wǎng)的度分布，其中網(wǎng)絡(luò)節(jié)點傾向于與度大節(jié)點相連，度小節(jié)點數(shù)增加，而度大節(jié)點數(shù)減少。

（3）根據(jù)圖3（b）和圖4（b）可知，優(yōu)化前網(wǎng)絡(luò)度分布基本呈二項分布特點，而優(yōu)化后網(wǎng)絡(luò)中度值大的節(jié)點數(shù)增加，度由低到高節(jié)點數(shù)依次減少。因此，ER 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)優(yōu)化后，度小的節(jié)點傾向于和度大節(jié)點相連。

（4）根據(jù)圖5 可知，使用截斷式選擇法的遺傳算法適應(yīng)度函數(shù)值隨迭代次數(shù)不斷增大，優(yōu)化效果明顯高于以輪盤賭法和排序分組法為選擇操作的遺傳算法。

圖5 自然連通度的迭代優(yōu)化

4.3 可靠性分析

上述分析以自然連通度為網(wǎng)絡(luò)可靠性測度建立拓?fù)鋬?yōu)化模型，并采用遺傳進化算法求解，提高了網(wǎng)絡(luò)可靠性。本文采取隨機攻擊和蓄意攻擊兩種策略，分別對優(yōu)化前后的通信網(wǎng)實施攻擊并分析網(wǎng)絡(luò)可靠性。通過仿真分析可知，通信網(wǎng)拓?fù)鋬?yōu)化前后面臨不同攻擊策略具有以下特點。

（1）在隨機去點攻擊策略中（如圖6（a）所示），優(yōu)化后的網(wǎng)絡(luò)可靠性在受到攻擊時相比于優(yōu)化前更加不穩(wěn)定，若增大網(wǎng)絡(luò)規(guī)模，將呈現(xiàn)更高的抗毀性。

圖6 隨機去除網(wǎng)絡(luò)的節(jié)點與邊

（2）在蓄意去點攻擊策略中（如圖7（a）和圖7（b）所示），由于攻擊方式是依次去除度大節(jié)點，優(yōu)化后的網(wǎng)絡(luò)在遭受此攻擊時受損性更高。

（3）在按介數(shù)去邊攻擊策略中（如圖7（b）所示），按邊的介數(shù)大小依次去邊。優(yōu)化后網(wǎng)絡(luò)面臨該攻擊方法表現(xiàn)出相對較強的可靠性，去除少量介數(shù)較大邊，對網(wǎng)絡(luò)可靠性影響有限。分析原因，在于優(yōu)化后網(wǎng)絡(luò)中度小的節(jié)點傾向于和度大節(jié)點相連，從而導(dǎo)致連接度大節(jié)點之間邊的介數(shù)相對較大，因此邊的冗余性較強。而針對優(yōu)化前的網(wǎng)絡(luò)結(jié)構(gòu)，反之亦然。

圖7 蓄意去除邊和節(jié)點

5 結(jié)語

本文首先建立了通信網(wǎng)拓?fù)浣Y(jié)構(gòu)優(yōu)化模型，提出了基于遺傳算法的求解方法，并通過仿真分析驗證了模型與方法的可行性。

（1）建立以自然連通度為目標(biāo)函數(shù)，以邊的數(shù)量為約束條件的通信網(wǎng)可靠性組合優(yōu)化模型；

（2）提出了基于遺傳算法的通信網(wǎng)可靠性仿真優(yōu)化算法，設(shè)計了變量編碼，改進了選擇操作，定義了交叉操作和變異操作，給出了算法流程；

（3）分析了優(yōu)化前后網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)與分布屬性，表明優(yōu)化后的通信網(wǎng)呈現(xiàn)出明顯的同配度關(guān)聯(lián)模式，度小節(jié)點傾向于與度大節(jié)點相連，高度數(shù)節(jié)點相對聚集，高度數(shù)節(jié)點之間連接較多，大多數(shù)節(jié)點之間連接較少，網(wǎng)絡(luò)拓?fù)涑尸F(xiàn)出“核心-外圍”結(jié)構(gòu)。

通過可靠性分析發(fā)現(xiàn)，經(jīng)遺傳算法優(yōu)化后的通信網(wǎng)在面對隨機去點攻擊和按介數(shù)去邊攻擊時表現(xiàn)出更高的抗毀能力，而面臨蓄意去點攻擊時則抗毀能力相對較差。因此，實際應(yīng)用中應(yīng)結(jié)合攻擊策略適應(yīng)性的構(gòu)建初始通信網(wǎng)拓?fù)浣Y(jié)構(gòu)。