遺傳算法在計算機網(wǎng)絡中的應用

丁 玲，范 平，聞 彬

（湖北科技學院計算機科學與技術學院,430074）

1 計算機的發(fā)展

社會是一個發(fā)展的過程，人類所使用的計算工具也是不斷地更新和發(fā)展，例如計算工具就相繼出現(xiàn)了算盤、計算尺、手搖機械計算機、電動機械計算機等。在1946年，美國發(fā)明了世界上第一臺電子數(shù)字計算機，從此人類的計算工程發(fā)生了天翻地覆的變化。人們接著研究出了第二代計算機，這類計算機和第一代計算機相比有了很大的改進。接著是第三代計算機，這類計算機主要是以中、小規(guī)模集成電路作為電子器件，并且出現(xiàn)了操作系統(tǒng)，功能也是越來越強。第四代計算機機1970年以后采用的。這種計算機不僅運算速度比從前提高了不少，而且已經(jīng)開始用于生活中的各種運算，性能已經(jīng)是大幅度提高。我們現(xiàn)在所用的基本上都是第五代計算機。如果說前面幾代計算機只是性能上的提高，那么第五代計算機可以說是從根本概念上有所突破，它徹底突破了以前的傳統(tǒng)——馮·諾依曼機器的概念，第五代計算機實現(xiàn)了計算的高度統(tǒng)一，徹底改變?nèi)祟惖拿\。

2 遺傳算法的定義

遺傳算法是一種借鑒生物界的進化規(guī)律演化而來的隨機化搜索方法。它不同于一般的算法是它是直接對結構對象進行操作的。內(nèi)在隱蔽性比較好而且相比之下有更好地全局尋優(yōu)能力；并且這種算法是采取概率化的尋優(yōu)方法，它主要的特點就是可以自動獲取和指導優(yōu)化的搜索空間，并且可以自動調(diào)整，不需要人為地來制定一些規(guī)則。

從遺傳算法的定義中我們可以看出，遺傳算法在搜索的時候是采用整體搜索策略和優(yōu)化搜索方法的，所以它在計算的時候并不需要依賴于梯度信息或者別的輔助知識；它需要的只是一個目標函數(shù)，一個能影響搜索方向的函數(shù)和一些相適應的函數(shù)。正式遺傳算法有這些優(yōu)點，所以它的應用范圍比較廣泛，通常不需要確定具體的問題，它幾乎可以用于任何領域，只要滿足遺傳算法的一些條件就可以了。比如說遺傳算法就常用于函數(shù)的優(yōu)化和組合優(yōu)化。

3 遺傳算法的重要性

前面簡單的介紹了一下什么是遺傳算法，那么遺傳算法為什么會如此重要，應用為什么會如此廣泛呢，這跟遺傳算法的特征是密不可分的。一般的算法有可能從問題的單個解開始，但是遺傳算法是從問題解的串集開始搜索，這就體現(xiàn)了遺傳算法比傳統(tǒng)算法的先進之處，傳統(tǒng)的優(yōu)化算法一般都是從單個初始值的迭代開始求最優(yōu)解的，這樣算法有一個很明顯的缺點就是不能考慮到全局。而遺傳算法就可以很好地考慮全局，全面有效的選擇選擇最優(yōu)解。遺傳算法在處理問題的時候會同時處理群體中的多個個體，這樣也是為了避免傳統(tǒng)優(yōu)化算法的誤區(qū)，避免陷入局部最優(yōu)解，同時能實現(xiàn)算法本身的并行化。遺傳算法的最大特點其實是它基本上不用搜索空間的知識和其他的一些輔助信息，而僅用適應度函數(shù)值來評估個體，在此基礎上進行遺傳操作。這種適應度函數(shù)可以不受連續(xù)可微的約束，而且它的定義域也是不受約束的，可以任意設定。遺傳算法的這個特點使得遺傳算法在應用中得到廣泛使用。遺傳算法是借鑒生物界的進化規(guī)律來模擬運算的，所以這種算法一般是不用確定一個特定的計算規(guī)律，而是根據(jù)概率的變遷規(guī)則來指導算法的搜索方向。等等一系列的特點使得遺傳算法在計算機網(wǎng)絡中應用得以如此廣泛。

4 遺傳算法在計算機網(wǎng)絡中的應用

4.1 遺傳算法在計算機網(wǎng)絡優(yōu)化設計中的應用

在一般的計算機網(wǎng)絡優(yōu)化設計中，有兩個很重要的問題就是各條線路的容量分配和各個節(jié)點間的路由選擇。如果一個算法中，網(wǎng)絡拓撲結構和交換量都給定了，那么我們怎么確定各條鏈路的容量大小和選擇各節(jié)點間的最佳路由呢？怎么樣才能減小成本，并且可以保證質(zhì)量，滿足用戶的需求呢？這就是我們需要考慮的問題。通常在傳統(tǒng)的算法情況下我們遇到這種多條件限制的問題時通常都會先確定一個條件不變?nèi)タ紤]另外一個條件，然后在確定另外一個條件不變來考慮原來的條件。比如傳統(tǒng)的算法就是先確定路由然后考慮容量分配問題，或者是先確定容量分配然后在考慮路由量。但是在這種計算機網(wǎng)絡優(yōu)化中，我們這樣做是不太合適的，因為路由的選擇和鏈容量的選擇是確定相關的，因此最佳的方案是同時考慮這兩個問題。我們可以看出來顯然這是一個多約束條件的復雜非線性規(guī)劃問題，對于這種問題，我們可以以遺傳算法為基礎，設計出一種遺傳尋優(yōu)算法。通過計算機遺傳算實例表明這種算法可以算出近似最優(yōu)解，而且精度比較高。

優(yōu)化設計中的數(shù)學模型

在計算機網(wǎng)絡中，中間節(jié)點一般會采用一種“存儲轉發(fā)”方式工作。通常節(jié)點處理都是需要時間的，比如本算法中的節(jié)點處理和鏈路處理都是需要時間的，但是由于這種處理的時間非常短，而且也不便測量，所以我們在計算的時候通常就是忽略這兩種時延不計，僅僅考慮等待時延。在這種估算的情況下我們可以采用排隊模型來處理，就是采用“先來先服務”規(guī)則。

4.2 遺傳算法在計算機網(wǎng)絡可靠度優(yōu)化計算中的應用

計算機網(wǎng)絡技術的迅速發(fā)展及其在各個領域中的應用的普及，致使網(wǎng)絡用戶節(jié)點不斷增加網(wǎng)絡規(guī)模日漸壯大，人們對網(wǎng)絡的應用也在不斷加強?，F(xiàn)在全世界計算機普及率已經(jīng)很高了，我們可以看出計算機的使用量在當今的這個社會是如此龐大。計算機有它的優(yōu)點，其中人們就是利用了計算機便于儲存信息的特點來儲存大量的信息，很多重要的資料都存在計算機中。但是一旦計算機網(wǎng)絡系統(tǒng)出現(xiàn)故障那么給人們帶來的損失也將是非常慘重的，甚至是無法估計的。所以計算機是否可靠，我們又怎么樣來提高計算機的可靠性呢？在降低計算機網(wǎng)絡成本的同時提高計算機網(wǎng)絡的可靠性是人們一直追求的問題。在傳統(tǒng)求解方法對于這一復雜優(yōu)化NP難題，人們通常顯得力不從心，針對這一現(xiàn)象，本段提出了用于計算機網(wǎng)絡可靠度優(yōu)化計算的遺傳算法，并且用實例實現(xiàn)了算法的執(zhí)行過程。這種問題都可以轉化成數(shù)學模型來做，但是由于模型比較復雜在這里就不做贅述了。當然遺傳算法在計算機網(wǎng)絡中的應用還不止這些，比如說在計算機網(wǎng)絡劃分優(yōu)化用的應用，遺傳算法在計算機網(wǎng)絡劃分應用中可以實現(xiàn)自動網(wǎng)絡劃分的目的，實驗結果表明這種劃分是可行并且有效地。還有就是遺傳算法在計算機通信網(wǎng)容量分配和流量控制中的應用。

4.3 遺傳算法在計算機輔助創(chuàng)新作曲中的應用

現(xiàn)代科技越來越發(fā)達了，而且歷史也證明很多新的科學都是在不同領域學科的交叉點上完成的。上個世紀七十年代出現(xiàn)了一種新的音樂叫做“電腦音樂”就是音樂技術與信息科學技術所產(chǎn)生的交叉科學。近幾年來電腦音樂已經(jīng)取得了較大的進步和發(fā)展，也產(chǎn)生了很多的效果。比如說電子樂器，還有各種音頻信號壓縮等技術。許多采用遺傳算法規(guī)律的算法都是采用基于實例的隨機算法來處理算法的過程。遺傳算法的核心就是根據(jù)生物進化規(guī)則來進行優(yōu)勝劣汰的，它也是通過計算機創(chuàng)造染色體的方式來模擬生物進化法則從而算出結果來的。遺傳算法在音樂方面的作用已經(jīng)得到了充分的證實，但是也還是存在著許多問題。任然需要不斷地改進。

5 結束語

進入90年代以來，遺傳算法可以說是迎來了它的興旺時期，這時候遺傳算法得到了廣泛的應用，無論是在理論研究領域還是在科學應用領域都得到了很大的應用。其中尤其是遺傳算法的應用，人們更是不斷地研究。而且利用遺傳算法進行優(yōu)化和規(guī)則學習的能力也是顯著提高，同時遺傳算法也應用于產(chǎn)業(yè)應用方面。遺傳算法可以說已經(jīng)涉及到現(xiàn)代科技發(fā)展的各個領域，在不同的領域都有著廣泛的應用。隨著科技的發(fā)展遺傳算法的研究出現(xiàn)了幾個新的方向特別引人注目，分別是：遺傳算法的機器學習，遺傳算法在不同學科中的交叉綜合，前面所說的遺傳算法在音樂中的應用就是一個很好地例子。還有就是遺傳算法在人工生命方面的研究?？傊z傳算法是一種新的科學運算規(guī)則，它在當今社會的很多領域都得到了廣泛的應用，而且具有很多優(yōu)點。但是遺傳算法也還是有不足之處的。比如說遺傳算法在效率上就比一般的傳統(tǒng)優(yōu)化算法低，這是因為遺傳算法從全局考慮的原因。遺傳算法的精度、可行度、計算復雜性等方面相比傳統(tǒng)算法來說就缺少一種有效的定量分析方法。

［1］ 張順頤，基于遺傳算法利用網(wǎng)絡時延解決路由問題的心算法[J]；通信學報，1999.20（12）:31-37

［2］ 孫力娟，吳新余.應用遺傳算法求解計算機通信網(wǎng)的最佳路由——一種新的遍歷匹配選擇法[J]；南京郵電學院學報，1996,16（2）：26-28