盧宏煦 劉恒

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

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

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

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

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

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

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

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

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

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

2問(wèn)題描述

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

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

3.4計(jì)算適值

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

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

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

3.5遺傳運(yùn)算

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

3.5.1交叉

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

3.5.2變異

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

3.6進(jìn)化運(yùn)算

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

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

5結(jié)束語(yǔ)

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

參考文獻(xiàn)：

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

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

[3]汪定偉,唐加福,黃敏.遺傳算法與工程設(shè)計(jì)[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.