計(jì)算機(jī)網(wǎng)絡(luò)k-劃分優(yōu)化遺傳算法講解(編輯修改稿)
2024-07-22 05:16 本頁面
【文章內(nèi)容簡介】 操作。 改進(jìn)的雜交操作 為了避免過多地破壞有用的模式（Schema），本文采用兩個交叉點(diǎn)位置相距較小的兩點(diǎn)雜交算子，另外，為避免產(chǎn)生空劃分解，在雜交操作之后還引入空劃分檢查校正操作，如圖2所示：父體A：000101030202兩點(diǎn)交叉000102020102檢查校正000103020102父體B：000302020103000301030203000301030203圖2 改進(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)行對等基因位對換操作來實(shí)現(xiàn)變異。同時鑒于變異幅度過大可能會破壞最優(yōu)解，故對換次數(shù)較少。 算法描述上述求解網(wǎng)絡(luò)k劃分優(yōu)化問題的改進(jìn)遺傳算法描述如下：{隨機(jī)產(chǎn)生初始化種群X(0)={x1(0)，x2(0)，…，xn (0)}； //n：種群規(guī)模t=0。 //t：演化代數(shù)，初值t =0 根據(jù)適應(yīng)度函數(shù)定義，計(jì)算X(0)中每個個體的適應(yīng)度值f(xi)； while(fmax(x(t)) fmin(x(t))ε) // fmax(x(t)) fmin(x(t))ε為停機(jī)準(zhǔn)則 { 計(jì)算種群X(t)中各個體的適應(yīng)度值比例，確定選擇概率pi； for(k=1；k≤n；k=k+2) { 根據(jù)選擇概率pi和轉(zhuǎn)盤式選擇策略在X(t)中選擇兩個個體xa，xb； 以概率pm對個體xa，xb執(zhí)行變異操作，得到兩個新個體xam，xbm； rdm=random[0，1]； if(rdm≤pc) // pc為雜交概率 { 對個體xam，xbm執(zhí)行雜交操作，得到兩個新個體xamc，xbmc； 對個體xamc，xbmc執(zhí)行空劃分檢查校正操作，得到兩個新個體x1，x2； } else { x1= xam。 x2= xbm。} 將x1，x2插入到新種群X(t+1)中； } 計(jì)算X(t+1)中個體的適應(yīng)度值，并用X(t)中適應(yīng)度值最大的個體xmax(t)替換X(t+1)中適應(yīng)度值最小的個體xmin(t+1)；t=t+1；} 輸出X(t)；}5 算法收斂性分析定理[2]：在選擇算子前保留當(dāng)前最好解的SGA能以概率收斂到全局最優(yōu)解。本文設(shè)計(jì)的算法屬于種
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1