一種基于遺傳算法的通信網拓撲優化方法*

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

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

0 引言

通信網[1]的網絡結構（即網絡拓撲）是泛指網絡節點和傳輸線路的幾何連接形狀，關系著網絡連通性問題[2]。從網絡的內部結構屬性出發，探究具有較高可靠性的通信網，在各種實際應用中是一項重要需求。

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

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

1 基于自然連通度的通信網可靠性優化模型

本文以自然連通度作為網絡可靠性測度指標優化其拓撲結構。

對通信網圖G的基本假設如下。

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

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

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

定義自然連通度，即假設在一個網絡中，任意節點vi和vj之間的長度為k的途徑數目為，然后通過i、j、k的關系求和：

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

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

此時，nk表示網絡中所有長度為k的閉途徑數目，可表示為：

代回式（4），可得：

式中，λi代表該網絡鄰接矩陣的特征根。

影響網絡可靠性的因素很多。在網絡節點數量一定的情況下，網絡中鏈路數量成為主要影響因素。自然連通度值關于增邊是嚴格單調遞增的，在對網絡鏈路數量沒有限制的情況下，全連接網絡拓撲將是可靠性最優的網絡。但是，事實上，網絡構造會受到成本等限制，顯然鏈路數越多的網絡成本也將越大。因此，在鏈路數W一定的情況下，研究網絡可靠性問題是必要的。本文假設通信網鏈路數量滿足的約束條件如下：

由上述分析可建立通信網拓撲結構優化模型：

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

2 基于遺傳算法的通信網可靠性仿真優化方法

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

圖1 遺傳算法流程

2.1 變量編碼

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

2.2 選擇操作

為了尋找可靠性更高的通信網拓撲結構，在每一次選擇操作中依據目標函數值選擇結果較大的個體。本文中分別選用輪盤賭選擇、截斷選擇法、排序分組3 種不同的操作進行對比與分析。

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

（1）在初始種群中計算每個個體（鄰接矩陣）的目標函數值；

（2）按照適應度值大小進行降序排列；

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

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

（1）以個體數為9 的一個初始種群為例，表1中數據為種群個體適應度值。

表1 個體數為9 的一個初始種群的個體適應度值

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

表2 適應度值由大到小進行排列的結果

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

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

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

表3 選擇出來的個體情況

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

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

表4 選擇出來的個體情況

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

2.3 交叉操作

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

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

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

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

交叉過程如圖2 所示。

圖2 交叉過程

2.4 變異操作

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

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

3 算法改進及模型約束

3.1 算法改進

傳統的遺傳算法容易出現收斂速度慢的問題，本文改進了局部尋優策略，具體如下。

3.1.1 局部搜索

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

式中，F(Gk)表示染色體的適應度，固定每個染色體的局部優化次數，如50 次。

3.1.2 參數自適應

為了同時保證算法在訓練時前期的多樣性和后期的集中性，本文對交叉概率Pc和變異概率Vc做自適應性的調整：

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

3.2 模型約束

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

3.2.1 網絡圖的無向簡單圖約束

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

3.2.2 網絡圖的邊數目約束

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

假設邊的數目為：

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

3.2.3 圖的連通性約束

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

4 仿真實驗及分析

4.1 優化拓撲結構的實驗仿真

為了驗證提出的網絡拓撲優化算法的有效性，在仿真運行環境為64 位Windows10 操作系統、Python3.8、處理器為Intel i7 9570H、主頻2.6 GHz、內存16 GB 的情況下進行實驗，參數設置如表5 所示。首先，構造初始通信網得到其鄰接矩陣。其次，通過表1 設置的參數進行遺傳算法的初始化。最后，根據第4 節遺傳算法的步驟得到自然連通度的最 優值。

表5 參數設置

4.2 網絡拓撲結構分析

仿真過程中，選用ER 隨機圖為研究對象。基本參數中，定義節點數N=50，邊連接概率p=0.12。生成的ER 網絡（連通圖）拓撲結構與度分布，如圖3 所示。

圖3 網絡拓撲結構與度分布

在保持網絡節點數和鏈路數不變的情況下，優化前后的通信網拓撲結構及度分布分別如圖3 和 圖4 所示。隨著迭代次數的增加，自然連通度值都明顯呈上升趨勢，如圖5 所示。因此，遺傳算法可用于求解通信網拓撲優化模型，且運用了算法收斂速度快等優點。

圖4 網絡拓撲結構與度分布

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

（1）仿真分析驗證了通信網拓撲結構優化模型的有效性和采用遺傳算法求解該模型的可行性。由圖5 可得，隨著迭代次數的增加，自然連通度值呈上升趨勢，最優結果在第100 次迭代達到7.6，說明網絡拓撲結構可靠性得到增強。

（2）經遺傳算法優化后，改變了通信網的度分布，其中網絡節點傾向于與度大節點相連，度小節點數增加，而度大節點數減少。

（3）根據圖3（b）和圖4（b）可知，優化前網絡度分布基本呈二項分布特點，而優化后網絡中度值大的節點數增加，度由低到高節點數依次減少。因此，ER 網絡拓撲結構優化后，度小的節點傾向于和度大節點相連。

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

圖5 自然連通度的迭代優化

4.3 可靠性分析

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

（1）在隨機去點攻擊策略中（如圖6（a）所示），優化后的網絡可靠性在受到攻擊時相比于優化前更加不穩定，若增大網絡規模，將呈現更高的抗毀性。

圖6 隨機去除網絡的節點與邊

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

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

圖7 蓄意去除邊和節點

5 結語

本文首先建立了通信網拓撲結構優化模型，提出了基于遺傳算法的求解方法，并通過仿真分析驗證了模型與方法的可行性。

（1）建立以自然連通度為目標函數，以邊的數量為約束條件的通信網可靠性組合優化模型；

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

（3）分析了優化前后網絡拓撲結構與分布屬性，表明優化后的通信網呈現出明顯的同配度關聯模式，度小節點傾向于與度大節點相連，高度數節點相對聚集，高度數節點之間連接較多，大多數節點之間連接較少，網絡拓撲呈現出“核心-外圍”結構。

通過可靠性分析發現，經遺傳算法優化后的通信網在面對隨機去點攻擊和按介數去邊攻擊時表現出更高的抗毀能力，而面臨蓄意去點攻擊時則抗毀能力相對較差。因此，實際應用中應結合攻擊策略適應性的構建初始通信網拓撲結構。