計(jì)算機(jī)網(wǎng)絡(luò)k-劃分優(yōu)化遺傳算法講解(完整版)
【正文】 表3考察了變異概率pm分別取不同的值時(shí)對(duì)算法性能的影響，結(jié)果表明隨著pm的增大，算法收斂于局部最優(yōu)的可能性明顯減小。 x2= xbm。設(shè)網(wǎng)絡(luò)有n個(gè)節(jié)點(diǎn)，根據(jù)需要欲劃分為k個(gè)子網(wǎng)，則染色體（即問題的一個(gè)解）可如下表示：， 其中，例如，對(duì)具有30個(gè)站點(diǎn)的網(wǎng)絡(luò)，劃分為3個(gè)子網(wǎng)的某種網(wǎng)絡(luò)劃分編碼如圖1所示：染色體si：110202…10網(wǎng) 絡(luò)：節(jié)點(diǎn)1節(jié)點(diǎn)2節(jié)點(diǎn)3節(jié)點(diǎn)4節(jié)點(diǎn)5節(jié)點(diǎn)6…節(jié)點(diǎn)29節(jié)點(diǎn)30圖1 基因型編碼示意圖 適應(yīng)度函數(shù)定義根據(jù)圖的k劃分定義及劃分原則，如下定義適應(yīng)度函數(shù)f(x)： 其中其中o(x)就是式（5）中的目標(biāo)函數(shù)，即上面第二個(gè)等號(hào)后面的第一項(xiàng)；r為懲罰系數(shù)，0r1，它根據(jù)個(gè)體x違反約束條件的程度而定，r越大，約束條件要求越嚴(yán)格，否則約束條件比較寬松。因?yàn)閳D中所有邊的權(quán)值是一個(gè)常量，求屬于不同劃分的頂點(diǎn)之間的邊的權(quán)值之和的最小值問題，實(shí)際上也就是求同一劃分內(nèi)各頂點(diǎn)之間的邊的權(quán)值之和的最大值問題。在該算法中，我們通過改進(jìn)適應(yīng)度函數(shù)、遺傳操作算子以及參數(shù)選取，既充分利用了遺傳算法的全局搜索能力，又增強(qiáng)了遺傳算法的局部搜索能力，使算法在求解網(wǎng)絡(luò)的k劃分優(yōu)化問題中具有較快的收斂速度和較高的成功率。關(guān)鍵詞 遺傳算法 無向圖 k劃分 網(wǎng)絡(luò)劃分優(yōu)化1 引言在計(jì)算機(jī)網(wǎng)絡(luò)的設(shè)計(jì)與管理中，為了改善網(wǎng)絡(luò)性能，同時(shí)便于對(duì)網(wǎng)絡(luò)實(shí)施控制管理，采取的有效手段之一是將整個(gè)大的網(wǎng)絡(luò)劃分為多個(gè)較小的、相對(duì)獨(dú)立的子網(wǎng)(該問題被稱為“網(wǎng)絡(luò)k劃分優(yōu)化”問題，這里k指劃分的子網(wǎng)數(shù))。網(wǎng)絡(luò)k劃分優(yōu)化問題，屬于組合優(yōu)化的范疇，即根據(jù)輸入的數(shù)據(jù)信息和網(wǎng)絡(luò)基本拓?fù)淠Ｐ?，尋找可能的最佳網(wǎng)絡(luò)配置，這是一個(gè)NP完全問題。2 問題描述 網(wǎng)絡(luò)k劃分的原則a) 子網(wǎng)間的通信流量應(yīng)盡可能小，即將彼此之間通信量較少的網(wǎng)絡(luò)節(jié)點(diǎn)分配到不同的子網(wǎng)中，以減少通過網(wǎng)絡(luò)互連設(shè)備的開銷；b) 子網(wǎng)內(nèi)的通信流量應(yīng)盡可能大，即將彼此之間通信量較大或通信頻繁的網(wǎng)絡(luò)節(jié)點(diǎn)分配到同一個(gè)子網(wǎng)中，以提高子網(wǎng)的資源利用率、增強(qiáng)子網(wǎng)內(nèi)聚力；c) 各子網(wǎng)的流量應(yīng)盡量趨于平衡，從而保證網(wǎng)絡(luò)負(fù)載均衡，以防止因新增網(wǎng)絡(luò)設(shè)備而導(dǎo)致子網(wǎng)性能急劇下降。因此，（4）式和下式是等價(jià)的： （5）其中 且。u為解x是否為合法解的判定系數(shù)，可定義為：u=0, x為合法解時(shí) 1， 其他 選擇操作為了保持適中的選擇壓力，本文采用轉(zhuǎn)盤式選擇策略，先計(jì)算出個(gè)體的相對(duì)適應(yīng)值，記為。} 將x1，x2插入到新種群X(t+1)中； } 計(jì)算X(t+1)中個(gè)體的適應(yīng)度值，并用X(
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1