遺傳組播路由算法

　　算法描述

　　1.求出從源節(jié)點(diǎn)到每個(gè)目的節(jié)點(diǎn)記為DestSet[i]滿足式4的路徑，并通過K-shortest方法獲得組成備選路徑集合，記為PathSet。其中的K-shortest方法采用Dijkstra算法[4]在原圖中求兩節(jié)點(diǎn)間的最短路徑，然后依次刪除最短路徑上的邊，每刪除一條邊就生成一個(gè)子圖，再在子圖中用Dijkstra算法求最短路徑，所有子圖中的最短路徑計(jì)算完畢后，對(duì)這些路徑進(jìn)行排序，選擇最短的一條，就對(duì)應(yīng)原圖中的次短路徑。依次類推，可求得第k最短路徑。

　　2.從備選路徑集合PathSet中依次選取路徑組成一個(gè)組播樹，通過遺傳算法搜索最優(yōu)組播樹。下面給出求解組播樹的遺傳算法(GA)中的算子設(shè)計(jì)。

　　算子設(shè)計(jì)

　　編碼：采用按路徑編碼的方案，這其實(shí)是一種整數(shù)編碼法。編碼以組播樹作為染色體，以路徑作為基因，一棵組播樹由從源節(jié)點(diǎn)到各目的節(jié)點(diǎn)的路徑組成。采用K-shortest算法計(jì)算出符合時(shí)延約束的備選路徑集P={P1,P2，... ，Pm }，Pi={Pi0,Pi1，... ，Pi k-1 } (m為目的節(jié)點(diǎn)數(shù))。用染色體Chrome表示一棵組播樹，其編碼長(zhǎng)度為|DestSet| ，每個(gè)基因位Chrome[i]的取值為0 ~ (k-1)之間的任一整數(shù)，對(duì)應(yīng)DestSet[i].PathSet中的一條路徑。

　　適應(yīng)度函數(shù)：適應(yīng)度函數(shù)是遺傳算法用來判斷個(gè)體好壞的衡量尺度，該算法中組播樹費(fèi)用和越小，其適應(yīng)度值應(yīng)當(dāng)越高。這里將適應(yīng)度函數(shù)定為：

　　產(chǎn)生初始種群：種群記為ChromeSet。其中的每個(gè)個(gè)體ChromeSet[i](i∈0 ~ PopScale-1，PopScale是種群規(guī)模)也即Chrome采用隨機(jī)產(chǎn)生的方式，具體方法為：將一個(gè)隨機(jī)整數(shù)RAND∈[0, k-1]賦給Chrome[j]，( j∈0 ~| DestSet | -1)。

　　選擇算子：算法采用輪盤賭選擇機(jī)制，選擇概率 PS 取區(qū)間[0.5,1)內(nèi)的值。

　　交叉算子：算法采用單點(diǎn)交叉。首先選擇一對(duì)染色體ChromSet[i]，ChromSet[j]，隨機(jī)產(chǎn)生一個(gè)0~(k-1)之間的整數(shù)作為交叉點(diǎn)，然后交換這對(duì)染色體在該位置的基因值。

　　變異算子：變異概率Pm取區(qū)間[0.1,0.2)內(nèi)的值。變異時(shí)按變異概率對(duì)每個(gè)個(gè)體ChromSet[i]的每個(gè)基因位賦0~(k-1)之間的隨機(jī)整數(shù)。

　　算法復(fù)雜度分析

　　復(fù)雜度為搜索備選路徑的時(shí)間復(fù)雜度和利用遺傳算法求解最優(yōu)組播樹的時(shí)間復(fù)雜度兩部分。假設(shè)網(wǎng)絡(luò)節(jié)點(diǎn)總數(shù)為n，目的節(jié)點(diǎn)數(shù)為m，搜索備選的時(shí)間復(fù)雜度為利用遺傳算法求解的時(shí)間復(fù)雜度為其中g(shù)en為算法迭代次數(shù)，Popscale為種群規(guī)模，L為染色體串的長(zhǎng)度，因此算法總的時(shí)間復(fù)雜度為