遺傳組播路由算法

　　遺傳組播路由算法

　　算法描述

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

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

　　算子設(shè)計

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

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

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

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

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

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

　　算法復(fù)雜度分析

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