基于遺傳算法的計(jì)算機(jī)通信網(wǎng)絡(luò)可靠性多目標(biāo)優(yōu)化設(shè)計(jì)

毛奇

（南京機(jī)電職業(yè)技術(shù)學(xué)院 江蘇 南京210000）

基于遺傳算法的計(jì)算機(jī)通信網(wǎng)絡(luò)可靠性多目標(biāo)優(yōu)化設(shè)計(jì)

毛奇

（南京機(jī)電職業(yè)技術(shù)學(xué)院 江蘇 南京210000）

隨著科學(xué)技術(shù)的不斷進(jìn)步，計(jì)算機(jī)通信網(wǎng)絡(luò)隨之也迅速發(fā)展起來(lái)，因此對(duì)計(jì)算機(jī)通信網(wǎng)絡(luò)的可靠性的要求也越來(lái)越高，行之有效的方法就是在確保計(jì)算機(jī)通信網(wǎng)絡(luò)可靠性的基礎(chǔ)上減少其鏈路成本費(fèi)用，本章對(duì)遺傳算法進(jìn)行了扼要介紹，對(duì)計(jì)算機(jī)通信網(wǎng)絡(luò)進(jìn)行了基于遺傳算法的多目標(biāo)優(yōu)化設(shè)計(jì)，并通過(guò)實(shí)例仿真說(shuō)明了該方法的有效性，運(yùn)用該算法大大降低了鏈路成本，提高了網(wǎng)絡(luò)可靠性。

計(jì)算機(jī)通信網(wǎng)絡(luò)；遺傳算法；多目標(biāo)優(yōu)化；鏈路成本

隨著計(jì)算機(jī)通信網(wǎng)絡(luò)的高速發(fā)展，網(wǎng)絡(luò)的規(guī)模隨之也變得越來(lái)越壯大，同時(shí)也伴隨著鏈路容量的不斷擴(kuò)大，從而導(dǎo)致對(duì)于計(jì)算機(jī)通信網(wǎng)絡(luò)可靠性要求也越來(lái)越高[1-5]。近幾年，我國(guó)對(duì)計(jì)算機(jī)通信網(wǎng)絡(luò)可靠性的研究也涌現(xiàn)出了不少新方法[6-8]，取得了很大突破，但是針對(duì)實(shí)際計(jì)算機(jī)通信網(wǎng)絡(luò)其達(dá)到期望目標(biāo)還有一段距離，特別的一旦計(jì)算機(jī)通信網(wǎng)絡(luò)發(fā)生故障，其將會(huì)產(chǎn)生很大的難易彌補(bǔ)的損失。目前國(guó)內(nèi)對(duì)基于智能算法的計(jì)算機(jī)通信網(wǎng)絡(luò)可靠性多目標(biāo)優(yōu)化的研究還很少，而大部分研究全都有針對(duì)性，即能夠轉(zhuǎn)化成為串并聯(lián)結(jié)構(gòu)的簡(jiǎn)單通信網(wǎng)絡(luò)，同時(shí)傳統(tǒng)意義上的全是將網(wǎng)絡(luò)費(fèi)用最小化當(dāng)做約束條件而損失一定的可靠性，因此文中提出了一種新的方法，即運(yùn)用遺傳算法實(shí)現(xiàn)計(jì)算機(jī)通信網(wǎng)絡(luò)可靠性多目標(biāo)優(yōu)化。

1 建立計(jì)算機(jī)通信網(wǎng)絡(luò)可靠性數(shù)學(xué)建模

將網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)假定為加權(quán)無(wú)向圖G=（V，E），其中V和E分別表示網(wǎng)絡(luò)結(jié)點(diǎn)的集合和通信鏈路邊集。|V|和|E|分別表示G的結(jié)點(diǎn)個(gè)數(shù)和邊數(shù)，邊eij=（vi，vj）代表結(jié)點(diǎn)vi能夠直接到達(dá)vj的鏈路，如果eij= 0則代表鏈路不通。

C表示通信網(wǎng)絡(luò)結(jié)點(diǎn)間的鏈路成本矩陣，cij表示i、j兩結(jié)點(diǎn)間的鏈路成本鏈路，則成本矩陣為：

R表示通信網(wǎng)絡(luò)結(jié)點(diǎn)間的可靠度矩陣，rij表示i、j兩結(jié)點(diǎn)間的鏈路可靠度，則可靠度矩陣為：

加權(quán)無(wú)向圖G內(nèi)的各個(gè)結(jié)點(diǎn)及鏈路全可以運(yùn)用度量來(lái)代表其狀態(tài)，其邊eij的狀態(tài)包含邊傳播時(shí)延：delay（eij），E→R+，邊費(fèi)用cost（eij）：E→R+以及邊可靠度rel（eij）：E→R+3個(gè)度量。同時(shí)給出界定條件：結(jié)點(diǎn)間的通信量矩陣、鏈路容量的可能取值、通信費(fèi)用函數(shù)以及鏈路和結(jié)點(diǎn)的可靠性概率。建立數(shù)學(xué)模型如下：

約束條件：網(wǎng)絡(luò)的可靠性和適存性以及鏈路容量的可能取值范圍。

式中，Z（G）、D（G）以及R（G）分別表示計(jì)算機(jī)通訊網(wǎng)絡(luò)的總費(fèi)用、時(shí)延均值以及可靠性。Sat_cost（G）、Sat_delay（G）以及Sat_rel（G）表示各性能指標(biāo)滿意度函數(shù)，Gen_sat（G）則表示綜合滿意度函數(shù)。Wc、Wd以及Wr表示控制比重的權(quán)值系數(shù)，可靠度約束常數(shù)α和β分別表示計(jì)算機(jī)通信網(wǎng)絡(luò)內(nèi)結(jié)點(diǎn)i與結(jié)點(diǎn)j間的鏈路數(shù)目及有能夠直接到結(jié)點(diǎn)的鏈路的結(jié)點(diǎn)數(shù)目。

2 基于遺傳算法的計(jì)算機(jī)通信網(wǎng)絡(luò)可靠性多目標(biāo)優(yōu)化設(shè)計(jì)

2.1 遺傳算法

遺傳算法[9-12]可分成5部分即選擇編碼方式、確定初始化種群、運(yùn)算適應(yīng)度函數(shù)、交叉變異運(yùn)算以及選擇運(yùn)算，其能夠不依靠實(shí)際問(wèn)題自身而實(shí)現(xiàn)復(fù)雜系統(tǒng)的優(yōu)化求解問(wèn)題，實(shí)現(xiàn)流程見圖1。

2.2 遺傳算法優(yōu)化過(guò)程設(shè)計(jì)

1）編碼方式選擇，選用二進(jìn)制編碼方式對(duì)計(jì)算機(jī)通信網(wǎng)絡(luò)的個(gè)結(jié)點(diǎn)進(jìn)行編碼。

2）確定適應(yīng)度函數(shù)，為有效防止遺傳算法中的欺騙現(xiàn)象的發(fā)生,將種群中個(gè)體的成本值,按照數(shù)值的大小進(jìn)行排列,成本數(shù)值最小的個(gè)體排序編碼設(shè)為1，成本數(shù)值最大的個(gè)體排序編碼設(shè)為Pop_size，則：

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

3）選擇運(yùn)算，針對(duì)適應(yīng)度函數(shù)值是fk個(gè)體基因其選擇概率Pk為：

圖1 遺傳算法實(shí)現(xiàn)流程圖

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

3 實(shí)例仿真及結(jié)果分析

3.1 實(shí)例一

計(jì)算機(jī)通信網(wǎng)絡(luò)結(jié)點(diǎn)數(shù)目N=6，約束常數(shù)α和β均等于2，設(shè)定迭代次數(shù)100次，則計(jì)算機(jī)通信網(wǎng)絡(luò)的鏈路成本矩陣C0及可靠度矩陣R0分別是：

依照遺傳算法的實(shí)現(xiàn)流程圖以及設(shè)計(jì)流程，完成對(duì)其的優(yōu)化求解。終止條件設(shè)定為迭代次數(shù)等于100時(shí)終止仿真。通過(guò)遺傳算法對(duì)計(jì)算機(jī)通信網(wǎng)絡(luò)優(yōu)化求解[13-15]過(guò)程后，獲得其通信網(wǎng)絡(luò)鏈路成本的最小值是45，與此同時(shí)確保其可靠度獲得最大值等于0.875，其鏈路成本以及可靠度仿真曲線見圖2與圖3。

圖2 計(jì)算機(jī)通信網(wǎng)絡(luò)鏈路成本仿真曲線

圖3 計(jì)算機(jī)通信網(wǎng)絡(luò)可靠度仿真曲線

3.2 實(shí)例二

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

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

優(yōu)化過(guò)程中的3種情況如下：

1）如果相同程度的考慮權(quán)值系數(shù)Wc、Wd以及Wr，則Wc=Wd=Wr=1/3，優(yōu)化后通信網(wǎng)絡(luò)結(jié)構(gòu)見圖4，粗線代表主干網(wǎng)間的鏈路，細(xì)線代表服務(wù)中心和客戶端間的鏈路。

圖4 Wc=Wd=Wr=1/3時(shí)通信網(wǎng)絡(luò)結(jié)構(gòu)圖

2）如果在初始化及交叉變異過(guò)程中刪去不滿足可靠性約束的解，則可忽略可靠性，即相同程度的考慮權(quán)值系數(shù)Wc及Wd，Wc=Wd=0.5，Wr=0優(yōu)化后通信網(wǎng)絡(luò)結(jié)構(gòu)見圖5。

圖5 Wc=Wd=0.5，Wr=0時(shí)通信網(wǎng)絡(luò)結(jié)構(gòu)圖

3）若考慮費(fèi)用多一點(diǎn)，則Wc=0.8，Wd=0.2，Wr=0，優(yōu)化后通信網(wǎng)絡(luò)結(jié)構(gòu)見圖6。

圖6 Wc=0.8，Wd=0.2，Wr=0時(shí)通信網(wǎng)絡(luò)結(jié)構(gòu)圖

綜合以上3中情況，優(yōu)化后的結(jié)果見表1。

表1 優(yōu)化結(jié)果

4 結(jié) 論

通過(guò)實(shí)例一和實(shí)例二可得，基于遺傳算法的可靠性多目標(biāo)優(yōu)化方法能夠很好的對(duì)計(jì)算機(jī)通信網(wǎng)絡(luò)進(jìn)行優(yōu)化求解,很大程度上提高了各項(xiàng)指標(biāo)，能夠獲得很好的滿意最優(yōu)解。遺傳算法在保證計(jì)算機(jī)通信網(wǎng)絡(luò)可靠度的基礎(chǔ)上，能夠有效地降低網(wǎng)絡(luò)結(jié)點(diǎn)之間鏈路介質(zhì)的成本，具有很高的理論價(jià)值和應(yīng)用價(jià)值。

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

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

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

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

[5]李淑萍.計(jì)算機(jī)網(wǎng)絡(luò)可靠性的相關(guān)理論淺析[J].商品與質(zhì)量，2012:256.

[6]王孔勛,Enslow Jr P H,潘啟敬.樹形網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化設(shè)計(jì)的新算法[J].通信學(xué)報(bào)，1990，11（6）:3-9.

[7]劉小娥.基于鏈路可靠性的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)設(shè)計(jì)[J].武漢理工大學(xué)學(xué)報(bào)：信息與管理工程版，2002，24（3）:18-24.

[8]潘啟敬.樹型計(jì)算機(jī)網(wǎng)綜合優(yōu)化設(shè)計(jì)方法[J].通信學(xué)報(bào)，1993，14（1）:3-9.

[9]馬永杰，云文霞.遺傳算法研究進(jìn)展[J].計(jì)算機(jī)應(yīng)用研究，2012:1201-1203.

[10]劉強(qiáng),李積源.基于遺傳算法的通信網(wǎng)絡(luò)可靠性優(yōu)化設(shè)計(jì)[J].海軍工程大學(xué)學(xué)報(bào)，2001，13（6）:102-106.

[11]葉劍，席裕庚，曲潤(rùn)濤.基于遺傳算法的可靠性網(wǎng)絡(luò)規(guī)劃設(shè)計(jì)[J].通信技術(shù)，1999:15-18.

[12]孫立山,郝燕玲.基于混合遺傳算法的網(wǎng)絡(luò)拓?fù)湓O(shè)計(jì)[J1.計(jì)算機(jī)工程，2006，32（3）:25-27.

[13]盧宏煦，劉恒.計(jì)算機(jī)網(wǎng)絡(luò)可靠度優(yōu)化計(jì)算中遺傳算法的實(shí)踐分析[J].電腦知識(shí)與技術(shù)，2012:93-94.

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

[15]張子木.基于遺傳算法的計(jì)算機(jī)通信網(wǎng)絡(luò)可靠性分析及優(yōu)化[D].北京:北京郵電大學(xué)，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稿件編號(hào)：201604134

國(guó)家自然科學(xué)基金（60475017）

毛 奇（1985—），男，江蘇南京人，碩士，助教。研究方向：計(jì)算機(jī)網(wǎng)絡(luò)系統(tǒng)。