遺傳算法在計算機網絡中的應用

丁 玲，范 平，聞 彬

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

1 計算機的發展

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

2 遺傳算法的定義

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

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

3 遺傳算法的重要性

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

4 遺傳算法在計算機網絡中的應用

4.1 遺傳算法在計算機網絡優化設計中的應用

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

優化設計中的數學模型

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

4.2 遺傳算法在計算機網絡可靠度優化計算中的應用

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

4.3 遺傳算法在計算機輔助創新作曲中的應用

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

5 結束語

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

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

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