計算機(jī)網(wǎng)絡(luò)可靠度優(yōu)化計算中遺傳算法的實踐分析

盧宏煦 劉恒

摘要：當(dāng)前正值計算機(jī)網(wǎng)絡(luò)科技時代，計算機(jī)網(wǎng)絡(luò)已成為各行業(yè)普遍使用的重要工具之一，如何提高計算機(jī)網(wǎng)絡(luò)可靠度并對其進(jìn)行優(yōu)化已成為全球關(guān)注的焦點。而遺傳算法相較于傳統(tǒng)算法具有求解便捷、搜索高效、算法結(jié)構(gòu)簡便等特點，并且在計算全局時可以獲取最優(yōu)近似值。因此，本文在兼顧計算機(jī)網(wǎng)絡(luò)鏈路介質(zhì)成本和網(wǎng)絡(luò)可靠度數(shù)學(xué)模型因素的同時，通過實踐分析將遺傳算法應(yīng)用于計算機(jī)網(wǎng)絡(luò)可靠度優(yōu)化計算及其執(zhí)行過程。

關(guān)鍵詞：計算機(jī)網(wǎng)絡(luò)；可靠度；優(yōu)化；遺傳算法；實踐分析

中圖分類號：TP393文獻(xiàn)標(biāo)識碼：A文章編號：1009-3044(2012)01-0093-03

隨著計算機(jī)網(wǎng)絡(luò)技術(shù)的逐漸壯大發(fā)展，全球計算機(jī)網(wǎng)絡(luò)普及率日益提高，進(jìn)而各行業(yè)對于計算機(jī)網(wǎng)絡(luò)依賴性也相繼增強(qiáng)，如銀行業(yè)、醫(yī)療行業(yè)、網(wǎng)絡(luò)銷售行業(yè)等。計算機(jī)網(wǎng)絡(luò)可靠性（Reliability），又稱計算機(jī)網(wǎng)絡(luò)可用性（Availability），指計算機(jī)網(wǎng)絡(luò)存在著一棵生成樹的可能性，是描述計算機(jī)網(wǎng)絡(luò)保證各個用戶之間相互聯(lián)通能力的重要參數(shù)，其測度包括：網(wǎng)絡(luò)連通性、生存性、抗破壞性以及多種模式下網(wǎng)絡(luò)元件的有效性等。因此，如何科學(xué)提高計算機(jī)網(wǎng)絡(luò)可靠度并對其進(jìn)行優(yōu)化成為廣大計算機(jī)網(wǎng)絡(luò)研究人員及使用人員關(guān)注的焦點。

1計算機(jī)網(wǎng)絡(luò)可靠性概念簡析

計算機(jī)在一定的操作、負(fù)載、溫濕度和維修方式的條件下，并且在規(guī)定的時間內(nèi)，可連通網(wǎng)絡(luò)和保持網(wǎng)絡(luò)通信的能力被稱作計算機(jī)網(wǎng)絡(luò)可靠性，其體系科學(xué)完整，并經(jīng)歷了半個多世紀(jì)的發(fā)展擴(kuò)充，已經(jīng)被作為系統(tǒng)工程科學(xué)。計算機(jī)網(wǎng)絡(luò)可靠度可分為一下三種不同類型：

1)ɑ終端可靠度：制定匯點和制定源點之間至少存在一條正常鏈路的概率即為ɑ終端可靠度；

2)γ終端可靠度：指定的γ個結(jié)點所構(gòu)成的集合中都存在正常鏈路的概率稱為γ終端可靠度；

3)全終端可靠度：任意亮點間均存在正常鏈路的概率被稱作全終端可靠度。

另外，支持計算機(jī)網(wǎng)絡(luò)正常運行的參數(shù)還包括計算機(jī)網(wǎng)絡(luò)結(jié)構(gòu)，它也是計算機(jī)網(wǎng)絡(luò)運行的一項重要那個參數(shù)。

2問題描述

假設(shè)所使用的計算機(jī)傳輸介質(zhì)兩節(jié)點之間不多于一條直線接鏈路，因此計算機(jī)網(wǎng)絡(luò)可以運用數(shù)學(xué)圖G=（N，L）進(jìn)行描述。并且網(wǎng)絡(luò)節(jié)點自身不會發(fā)生任何故障，網(wǎng)絡(luò)鏈路介質(zhì)可靠度與自身長度無相關(guān)關(guān)系，網(wǎng)絡(luò)和網(wǎng)絡(luò)鏈路只存在兩種狀態(tài)：正常工作以及故障，同時網(wǎng)絡(luò)中的設(shè)備（包括計算機(jī)網(wǎng)絡(luò)傳輸介質(zhì)及交換設(shè)備）出現(xiàn)故障是隨機(jī)的并且是相互獨立的。

網(wǎng)絡(luò)鏈路介質(zhì)成本矩陣如（1）所示：

3.4計算適值

將種群中個體成本值由大到小降序排列，則最適值函數(shù)如（8）所示：

f（x）=（x-1）/(PoP-size-1)（8）

x：個體在成本排序中的位置（最小成本的個體排序編碼為1）；PoP-size：種群規(guī)模即最大成本的個體排序編碼。

3.5遺傳運算

遺傳運算主要以交叉和變異兩種形式進(jìn)行。

3.5.1交叉

通過在網(wǎng)絡(luò)結(jié)點范圍內(nèi)（[1,N]）產(chǎn)生隨機(jī)數(shù)，以此設(shè)定基因交叉位置且每次只能對一個結(jié)點實現(xiàn)操作。這樣可最大保持原有網(wǎng)絡(luò)連通性，但是有時可能出現(xiàn)錯誤的網(wǎng)絡(luò)連通結(jié)構(gòu)，所以還需要進(jìn)行調(diào)整操作。

3.5.2變異

先要確認(rèn)變異的基因及數(shù)目，之后按照選定范圍選取新的基因片段以替代舊基因片段，以此生成后代。通常異變率均在0.001到0.01范圍內(nèi)，但有時若異變產(chǎn)生錯誤的網(wǎng)絡(luò)連通結(jié)構(gòu)的基因，就需要進(jìn)行調(diào)整操作。

3.6進(jìn)化運算

須保證每個基因的選擇概率應(yīng)與其適值成正比，公式如（9）所示：

此時網(wǎng)絡(luò)可靠度約束常數(shù)都為2，總結(jié)點數(shù)為5，迭代次數(shù)為100次。仿真求解表明，網(wǎng)絡(luò)鏈路介質(zhì)總成本為40，保證網(wǎng)絡(luò)可靠度最大值得0.88。

5結(jié)束語

通過實踐分析，應(yīng)用遺傳算法對計算機(jī)網(wǎng)絡(luò)可靠度進(jìn)行優(yōu)化，確實可以有效降低網(wǎng)絡(luò)鏈路總成本，并在原有基礎(chǔ)之上進(jìn)一步提高計算機(jī)網(wǎng)絡(luò)的可靠度，整個過程操作簡便，并易于實現(xiàn)。

參考文獻(xiàn)：

[1]李宗英.計算機(jī)網(wǎng)絡(luò)可靠性優(yōu)化技術(shù)[J].軟件導(dǎo)刊,2008(6).

[2]張永富.基于遺傳算法的網(wǎng)絡(luò)可靠性優(yōu)化設(shè)計[D].南京:南京郵電大學(xué),2008.

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

[4] Ball M, Van R M Slyke.Backtracking algorithms for network reliability analysis[J].Annuls of Discrete Mathematics, (1)1977, (1):49-64.