基于遺傳算法的計算機通信網絡可靠性多目標優化設計

毛奇

（南京機電職業技術學院 江蘇 南京210000）

基于遺傳算法的計算機通信網絡可靠性多目標優化設計

毛奇

（南京機電職業技術學院 江蘇 南京210000）

隨著科學技術的不斷進步，計算機通信網絡隨之也迅速發展起來，因此對計算機通信網絡的可靠性的要求也越來越高，行之有效的方法就是在確保計算機通信網絡可靠性的基礎上減少其鏈路成本費用，本章對遺傳算法進行了扼要介紹，對計算機通信網絡進行了基于遺傳算法的多目標優化設計，并通過實例仿真說明了該方法的有效性，運用該算法大大降低了鏈路成本，提高了網絡可靠性。

計算機通信網絡；遺傳算法；多目標優化；鏈路成本

隨著計算機通信網絡的高速發展，網絡的規模隨之也變得越來越壯大，同時也伴隨著鏈路容量的不斷擴大，從而導致對于計算機通信網絡可靠性要求也越來越高[1-5]。近幾年，我國對計算機通信網絡可靠性的研究也涌現出了不少新方法[6-8]，取得了很大突破，但是針對實際計算機通信網絡其達到期望目標還有一段距離，特別的一旦計算機通信網絡發生故障，其將會產生很大的難易彌補的損失。目前國內對基于智能算法的計算機通信網絡可靠性多目標優化的研究還很少，而大部分研究全都有針對性，即能夠轉化成為串并聯結構的簡單通信網絡，同時傳統意義上的全是將網絡費用最小化當做約束條件而損失一定的可靠性，因此文中提出了一種新的方法，即運用遺傳算法實現計算機通信網絡可靠性多目標優化。

1 建立計算機通信網絡可靠性數學建模

將網絡拓撲結構假定為加權無向圖G=（V，E），其中V和E分別表示網絡結點的集合和通信鏈路邊集。|V|和|E|分別表示G的結點個數和邊數，邊eij=（vi，vj）代表結點vi能夠直接到達vj的鏈路，如果eij= 0則代表鏈路不通。

C表示通信網絡結點間的鏈路成本矩陣，cij表示i、j兩結點間的鏈路成本鏈路，則成本矩陣為：

R表示通信網絡結點間的可靠度矩陣，rij表示i、j兩結點間的鏈路可靠度，則可靠度矩陣為：

加權無向圖G內的各個結點及鏈路全可以運用度量來代表其狀態，其邊eij的狀態包含邊傳播時延：delay（eij），E→R+，邊費用cost（eij）：E→R+以及邊可靠度rel（eij）：E→R+3個度量。同時給出界定條件：結點間的通信量矩陣、鏈路容量的可能取值、通信費用函數以及鏈路和結點的可靠性概率。建立數學模型如下：

約束條件：網絡的可靠性和適存性以及鏈路容量的可能取值范圍。

式中，Z（G）、D（G）以及R（G）分別表示計算機通訊網絡的總費用、時延均值以及可靠性。Sat_cost（G）、Sat_delay（G）以及Sat_rel（G）表示各性能指標滿意度函數，Gen_sat（G）則表示綜合滿意度函數。Wc、Wd以及Wr表示控制比重的權值系數，可靠度約束常數α和β分別表示計算機通信網絡內結點i與結點j間的鏈路數目及有能夠直接到結點的鏈路的結點數目。

2 基于遺傳算法的計算機通信網絡可靠性多目標優化設計

2.1 遺傳算法

遺傳算法[9-12]可分成5部分即選擇編碼方式、確定初始化種群、運算適應度函數、交叉變異運算以及選擇運算，其能夠不依靠實際問題自身而實現復雜系統的優化求解問題，實現流程見圖1。

2.2 遺傳算法優化過程設計

1）編碼方式選擇，選用二進制編碼方式對計算機通信網絡的個結點進行編碼。

2）確定適應度函數，為有效防止遺傳算法中的欺騙現象的發生,將種群中個體的成本值,按照數值的大小進行排列,成本數值最小的個體排序編碼設為1，成本數值最大的個體排序編碼設為Pop_size，則：

其中，x表示個體在成本排列的位置，Pop_size為種群大小，1≤x≤Pop_size。

3）選擇運算，針對適應度函數值是fk個體基因其選擇概率Pk為：

圖1 遺傳算法實現流程圖

4）交叉變異運算，交叉步驟：選用任意交叉結點方式在[1，N]范圍內選定基因交叉位置，每一次僅可以一個結點位置使用交叉運算，一般狀況下交叉概率Pc∈（0.01，0.1）范圍。變異步驟：①確定變異基因x=[x1，x2，…，xk]，②任意選擇整數k∈[1，n]，μ∈[1，n]，③產生后代 x′=[x1，x2，…，x′k，…，xk]，此中 x′k為[x′k，xμk]范圍內均勻分布的任意一個數值，若不能完成，則跳轉至②。一般狀況下變異概率Pk∈（0.001，0.01）。

3 實例仿真及結果分析

3.1 實例一

計算機通信網絡結點數目N=6，約束常數α和β均等于2，設定迭代次數100次，則計算機通信網絡的鏈路成本矩陣C0及可靠度矩陣R0分別是：

依照遺傳算法的實現流程圖以及設計流程，完成對其的優化求解。終止條件設定為迭代次數等于100時終止仿真。通過遺傳算法對計算機通信網絡優化求解[13-15]過程后，獲得其通信網絡鏈路成本的最小值是45，與此同時確保其可靠度獲得最大值等于0.875，其鏈路成本以及可靠度仿真曲線見圖2與圖3。

圖2 計算機通信網絡鏈路成本仿真曲線

圖3 計算機通信網絡可靠度仿真曲線

3.2 實例二

該實例中具有4個服務中心以及8個工作站，并且各中心至多連接3個工作站，依據實際網絡得知，服務中心i與j間的鏈路費用很高，因此C1ij任意生成范圍是[100，300]，服務中心i與工作站j間的鏈路費用相比較而言很低，因此C2ij任意生成范圍是[1，100]，服務中心總通信量是50，w1ij與w2ij取值：

服務中心、服務中心鏈路間以及工作站、服務中心和工作站鏈路間的可靠性分別是0.95、0.9以及0.9、0.85。設定參數：種群規模及最大迭代次數分別是100、500，交叉及變異概率分別是0.3及0.7。

優化過程中的3種情況如下：

1）如果相同程度的考慮權值系數Wc、Wd以及Wr，則Wc=Wd=Wr=1/3，優化后通信網絡結構見圖4，粗線代表主干網間的鏈路，細線代表服務中心和客戶端間的鏈路。

圖4 Wc=Wd=Wr=1/3時通信網絡結構圖

2）如果在初始化及交叉變異過程中刪去不滿足可靠性約束的解，則可忽略可靠性，即相同程度的考慮權值系數Wc及Wd，Wc=Wd=0.5，Wr=0優化后通信網絡結構見圖5。

圖5 Wc=Wd=0.5，Wr=0時通信網絡結構圖

3）若考慮費用多一點，則Wc=0.8，Wd=0.2，Wr=0，優化后通信網絡結構見圖6。

圖6 Wc=0.8，Wd=0.2，Wr=0時通信網絡結構圖

綜合以上3中情況，優化后的結果見表1。

表1 優化結果

4 結 論

通過實例一和實例二可得，基于遺傳算法的可靠性多目標優化方法能夠很好的對計算機通信網絡進行優化求解,很大程度上提高了各項指標，能夠獲得很好的滿意最優解。遺傳算法在保證計算機通信網絡可靠度的基礎上，能夠有效地降低網絡結點之間鏈路介質的成本，具有很高的理論價值和應用價值。

[1]郭永基.可靠性工程原理[M].北京:清華大學出版社，2002.

[2]王少萍.可靠性工程[M].北京:北京航空航天大學出版社，2000.

[3]曹晉華,程侃.可靠性數學引論[M].北京:科學出版社，1986.

[4]周廣濤.計算機輔助可靠性工程[M].北京:宇航出版社，1990.

[5]李淑萍.計算機網絡可靠性的相關理論淺析[J].商品與質量，2012:256.

[6]王孔勛,Enslow Jr P H,潘啟敬.樹形網絡結構優化設計的新算法[J].通信學報，1990，11（6）:3-9.

[7]劉小娥.基于鏈路可靠性的網絡拓撲結構設計[J].武漢理工大學學報：信息與管理工程版，2002，24（3）:18-24.

[8]潘啟敬.樹型計算機網綜合優化設計方法[J].通信學報，1993，14（1）:3-9.

[9]馬永杰，云文霞.遺傳算法研究進展[J].計算機應用研究，2012:1201-1203.

[10]劉強,李積源.基于遺傳算法的通信網絡可靠性優化設計[J].海軍工程大學學報，2001，13（6）:102-106.

[11]葉劍，席裕庚，曲潤濤.基于遺傳算法的可靠性網絡規劃設計[J].通信技術，1999:15-18.

[12]孫立山,郝燕玲.基于混合遺傳算法的網絡拓撲設計[J1.計算機工程，2006，32（3）:25-27.

[13]盧宏煦，劉恒.計算機網絡可靠度優化計算中遺傳算法的實踐分析[J].電腦知識與技術，2012:93-94.

[14]汪定偉，唐加福，黃敏.遺傳算法與工程設計[M].北京:科學出版社，2000.

[15]張子木.基于遺傳算法的計算機通信網絡可靠性分析及優化[D].北京:北京郵電大學，2009.

Computer communication network reliability multi-objective optimal design based on genetic algorithm

MAO Qi
（Nanjing Institute of Mechatronic Technology，Nanjing 210000，China）

With the progress of science and technology,computer communications network has developed rapidly，so the computer communication network reliability requirements have become more sophisticated and effective way is to ensure the reliability of computer communication network,reduce link costs,this chapter provides an overview of genetic algorithms，and using the method of multi-objective optimization design was carried out on the computer communication network,and through the example simulation illustrates the effectiveness of the method，using this algorithm greatly reduces the link cost,improve the network reliability.

computercommunicationnetworks；geneticalgorithm；multi-objectiveoptimization；link cost

TN915

：A

：1674－6236（2017）01-0075-03

2016-04-13稿件編號：201604134

國家自然科學基金（60475017）

毛 奇（1985—），男，江蘇南京人，碩士，助教。研究方向：計算機網絡系統。