基于無向圖理論的計算機網(wǎng)絡k-劃分優(yōu)化遺傳算法


頁數(shù)：7 字數(shù)：3960

基于無向圖理論的計算機網(wǎng)絡k-劃分優(yōu)化遺傳算法

摘要 本文分析了網(wǎng)絡多劃分優(yōu)化問題的實質(zhì)，提出運用無向圖多劃分理論對該問題加以研究，并結(jié)合問題本身的特點，設計了一種改進型遺傳算法。該算法從適應度函數(shù)設計、遺傳操作算子以及參數(shù)選取等方面對經(jīng)典遺傳算法進行了改進。實際研究結(jié)果表明該算法實現(xiàn)了計算機網(wǎng)絡自動劃分優(yōu)化的目的，且算法性能優(yōu)于經(jīng)典遺傳算法。
關(guān)鍵詞 遺傳算法 無向圖 k-劃分 網(wǎng)絡劃分優(yōu)化

引言
在計算機網(wǎng)絡的設計與管理中，為了改善網(wǎng)絡性能，同時便于對網(wǎng)絡實施控制管理，采取的有效手段之一是將整個大的網(wǎng)絡劃分為多個較小的、相對獨立的子網(wǎng)(該問題被稱為“網(wǎng)絡k-劃分優(yōu)化”問題，這里k指劃分的子網(wǎng)數(shù))。網(wǎng)絡k-劃分優(yōu)化問題，屬于組合優(yōu)化的范疇，即根據(jù)輸入的數(shù)據(jù)信息和網(wǎng)絡基本拓撲模型，尋找可能的最佳網(wǎng)絡配置，這是一個NP完全問題。對于該問題的研究，由于其計算復雜度隨網(wǎng)絡規(guī)模和需劃分的子網(wǎng)數(shù)k的增大而急劇增加，傳統(tǒng)的啟發(fā)式搜索方法已無能為力。近年來，遺傳算法已被引入到該問題的求解中來。遺傳算法作為一種全局優(yōu)化搜索算法，由于其本身所具有的全局收斂性和隱含的并行性，加之其簡單易用、魯棒性強，能夠輕易地獲得問題的全局最優(yōu)解，且問題越復雜，它相對于其他算法的優(yōu)越性越明顯，故十分適合解決這類問題。但應用經(jīng)典遺傳算法求解網(wǎng)絡的k-劃分優(yōu)化問題時，其求解時間很長，且求得最優(yōu)解的成功率很低。因而，有必要針