計(jì)算機(jī)網(wǎng)絡(luò)k-劃分優(yōu)化遺傳算法講解-在線瀏覽
2024-08-05 05:16本頁(yè)面
【正文】 充分利用了遺傳算法的全局搜索能力，又增強(qiáng)了遺傳算法的局部搜索能力，使算法在求解網(wǎng)絡(luò)的k劃分優(yōu)化問(wèn)題中具有較快的收斂速度和較高的成功率。 網(wǎng)絡(luò)流量分布模型網(wǎng)絡(luò)劃分的一個(gè)重要依據(jù)是網(wǎng)絡(luò)中任意一對(duì)站點(diǎn)間的通信量，因此可采用如下網(wǎng)絡(luò)流量分布矩陣來(lái)描述網(wǎng)絡(luò)中的流量分布狀況。通過(guò)流量分布矩陣，可計(jì)算出網(wǎng)絡(luò)的總流量和每個(gè)服務(wù)器的輸入/輸出總流量： （2） （3）通過(guò)對(duì)上述網(wǎng)絡(luò)k劃分問(wèn)題的劃分原則和網(wǎng)絡(luò)流量分布模型的分析可知，該問(wèn)題的實(shí)質(zhì)是研究無(wú)向圖的多劃分問(wèn)題，即對(duì)于一無(wú)向圖，將其頂點(diǎn)集劃分為互不相交的k個(gè)子集，求使這些子集間聯(lián)系最少的一種劃分。3 無(wú)向圖多劃分優(yōu)化理論無(wú)向圖多劃分優(yōu)化理論可概述為： 定義 對(duì)于一無(wú)向圖，其中頂點(diǎn)集合，邊的集合，用定義邊的權(quán)值。因?yàn)閳D中所有邊的權(quán)值是一個(gè)常量，求屬于不同劃分的頂點(diǎn)之間的邊的權(quán)值之和的最小值問(wèn)題，實(shí)際上也就是求同一劃分內(nèi)各頂點(diǎn)之間的邊的權(quán)值之和的最大值問(wèn)題。4 算法設(shè)計(jì) 經(jīng)典遺傳算法的不足 圖的k劃分問(wèn)題劃分后所得到的任一子集都不能為空，至少必須包含一個(gè)頂點(diǎn)。 網(wǎng)絡(luò)的k劃分問(wèn)題屬于約束優(yōu)化問(wèn)題，經(jīng)典遺傳算法在產(chǎn)生非法解時(shí)丟棄，當(dāng)合法解產(chǎn)生概率較低時(shí)，該方法將浪費(fèi)大量CPU時(shí)間。 對(duì)經(jīng)典遺傳算法改進(jìn) 編碼表示編碼表示方案的選取很大程度上依賴于問(wèn)題的性質(zhì)及遺傳算子的設(shè)計(jì)。設(shè)網(wǎng)絡(luò)有n個(gè)節(jié)點(diǎn)，根據(jù)需要欲劃分為k個(gè)子網(wǎng)，則染色體（即問(wèn)題的一個(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)格，否則約束條件比較寬松。然后，基于進(jìn)行選擇操作。從網(wǎng)絡(luò)k劃分角度看，變異操作使網(wǎng)絡(luò)節(jié)點(diǎn)在各劃分中進(jìn)行重新分配，以維持種群的多樣性，防止出現(xiàn)早熟現(xiàn)象，本算法中的變異操作不是以經(jīng)典的小概率發(fā)生，而是以大概率（）發(fā)生，采取連續(xù)多次進(jìn)行對(duì)等基因位對(duì)換操作來(lái)實(shí)現(xiàn)變異。 算法描述上述求解網(wǎng)絡(luò)k劃分優(yōu)化問(wèn)題的改進(jìn)遺傳算法描述如下：{隨機(jī)產(chǎn)生初始化種群X(0)={x1(0)，x2(0)，…，xn (0)}； //n：種群規(guī)模t=0。 x2= xbm。本文設(shè)計(jì)的算法屬于種
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1