基于混合遺傳算法的多約束組播路由問題的求解Ξ

1、 基于混合遺傳算法的多約束組播路由問題的求解謝黎明 1, 余豐人 2, 丘海明2(1. 廣東輕工職業(yè)技術(shù)學(xué)院 , 廣東 廣州 510300;2. 中山大學(xué)電子與通信工程系 , 廣東 廣州 510275摘 要 :研究了延時(shí) 、 延時(shí)抖動(dòng)約束的最小費(fèi)用組播路由問題 種模擬生物進(jìn)化過程的并行最優(yōu)算法 , 適合在大型 有連續(xù)性 , , 因而用遺傳算 、 關(guān)鍵詞 :(HG A ; 組播 ; Q oS; 模擬退火 (S A ; 指導(dǎo)初始群體生成 ; 啟發(fā)式交叉操作 中圖分類號(hào) :TP3011 文獻(xiàn)標(biāo)識(shí)碼 :A1 文章編號(hào) :052926579(2005 0220045204 隨著網(wǎng)絡(luò)技術(shù)的不斷發(fā)展和 In

2、ternet 的迅速普 及 , 網(wǎng)絡(luò)正以前所未有的速度發(fā)展 , 網(wǎng)絡(luò)規(guī)模將進(jìn) 一步擴(kuò)大 , 網(wǎng)絡(luò)信息流量迅速增加 , 從而網(wǎng)絡(luò)將變 得更加擁擠 , 這將嚴(yán)重影響網(wǎng)絡(luò)的傳輸速率 。 為了 減少網(wǎng)絡(luò)上傳輸信息包的總量 , 提高網(wǎng)絡(luò)的傳輸能 力 , 組播技術(shù)在網(wǎng)絡(luò)傳輸上得到了廣泛應(yīng)用 。 組播 技術(shù)要解決的關(guān)鍵問題之一就是組播路由問題 。 K om pella 等 1在 1992年首次提出了一種滿足給定端到端延時(shí)約束的組播路由算法 , 并證明此類問題是 NP 完全問題 。對(duì)于約束組播路由的求解 , 多年來提出了許多不同的算法 , 其中最引人注目的是近幾 年出現(xiàn)的一種新型優(yōu)化算法 遺傳算法 。 使用遺

3、 傳算法求解科學(xué)研究和工程技術(shù)中各種組合搜索和 優(yōu)化計(jì)算問題的這一基本思想 , 在 20世紀(jì) 60年代 初由美國(guó) Michigan 大學(xué)的 J. H olland 教授提出2,20世紀(jì) 80年代中期得到蓬勃發(fā)展 。但在其發(fā)展的同時(shí) , 遺傳算法也暴露出許多不足和缺陷 , 針對(duì)其 不足 , 近年來又有許多改進(jìn)的方法出現(xiàn) , 其中之一 就是將基本遺傳算法與傳統(tǒng)優(yōu)化方法相結(jié)合的混合 遺傳算法 。 本文正是利用混合遺傳算法 , 對(duì)多約束 的組播路由問題進(jìn)行求解 。1 多約束組播路由問題混合遺傳算法采用樹結(jié)構(gòu)編碼 。對(duì)于信源 s , 設(shè)與之相連的節(jié)點(diǎn)數(shù)為 N s , 計(jì)算與之相連的 N s 個(gè)邊 (e

4、1, e 2, ,e N s 的適應(yīng)度值 (f 1, f 2, , f N s , 采用概率P i =f i +N s fi2 fi不斷連接鄰節(jié)點(diǎn) , 最后刪除不是信宿的葉子節(jié)點(diǎn) ,從而獲得一個(gè)初始個(gè)體 。 重復(fù)這一步驟 , 直到初始 個(gè)體數(shù)目滿足要求為止 。 本文算法中 , 采用的群體 規(guī)模保持不變 , 取值為 15。對(duì)于組播樹有 T =(V T , E T , (T G 個(gè)體費(fèi)用為 f c =C ost (T = (a , b ET(a , b 個(gè)體最大延時(shí)為f D max =maxf Dv 1, f Dv 2, , f DvN 個(gè)體最大延時(shí)抖動(dòng)為f DJ max =maxf DJv 1,

5、 f DJv 2, , f DJvN 其中 ,f Dvi =(a , b P T(s , vi DJ (a , b , f DJvi =(a , b P T(s , vi DJ (a , b 構(gòu)造適應(yīng)度函數(shù) f T =1(af c +bf D max +cf DJ max 可見 , 此適應(yīng)度函數(shù)值大于零 , 在本文算法示 例中 a , b , c 的取值一律取 1。選擇方法采用最佳個(gè)體保留法 , 即每代的適應(yīng) 度值最高的個(gè)體直接進(jìn)入下一代 , 其余個(gè)體是否直 接進(jìn)入下一代則采用比例選擇方法 , 第 i 個(gè)個(gè)體 T i 的被選擇概率為 :P si =f (T i f (T i 在進(jìn)化后期 , 由

6、于產(chǎn)生的群體可能適應(yīng)度相差收稿日期 :2004-09-01基金項(xiàng)目 :國(guó)家自然科學(xué)基金資助項(xiàng)目 (60472010作者簡(jiǎn)介 :謝黎明 (1965年生 , 男 , 講師 ; 通訊聯(lián)系人 :丘海明 ; E -mail :xlm gdqy 1edu 1cn第 44卷 第 2期 2005年 3月 中山大學(xué)學(xué)報(bào) (自然科學(xué)版 ACT A SCIE NTI ARUM NAT URA LI UM UNI VERSIT ATIS S UNY ATSE NI V ol 144 N o 12Mar 1 2005 極小 , 為此結(jié)合模擬退火方法 , 對(duì)適應(yīng)度進(jìn)行拉 伸 , 拉伸方法如下 :f i =(ef iT-1

7、Mi =1e f iT-MT =T 0(g -1 (0<<1T 0為初始溫度 , T 0和 隨具體問題而變。適應(yīng)度的拉伸作用 , 要求保證在初期拉伸后適應(yīng)度相差不 大 ; 而后期為了使更優(yōu)良個(gè)體突出 , 要求各個(gè)體適 應(yīng)度拉伸后的差距變大。 本算法中適應(yīng)度拉伸采用 的 值為 018, 初始溫度 T 0采用初始群體平均適 應(yīng)度值 (15 f i -begin 。(個(gè)體 , 依照下述的交叉規(guī)則以概率 1交叉產(chǎn)生一個(gè)新子女個(gè)體 3。 該過程一直重復(fù)到下一代個(gè)體數(shù) 與初始群體數(shù)目相同為止 。 交叉規(guī)則如下 : 選擇 父母中相同的鏈路 , 將其直接遺傳到子女 。 下一步 就是連接這些零散子樹

8、成為一棵完整的樹 。 連接 這些零散子樹前首先對(duì)這些零散子樹進(jìn)行分類 , 第 一類子樹包括源節(jié)點(diǎn) , 記為 T s ; 第二類子樹包括目的節(jié)點(diǎn) , 記為 T vi ; 第三類子樹即不包括源節(jié)點(diǎn) , 也不包括目的節(jié)點(diǎn) , 記為 T mi 。組成完整組播樹連接規(guī)則采用如下啟發(fā)式的連 接方法 :如果所選擇的父母?jìng)€(gè)體在延時(shí)或延時(shí)抖動(dòng) 約束上只有一項(xiàng)不滿足 , 則在子樹間采用使該項(xiàng)約 束最小的最短路徑連接 , 若父母?jìng)€(gè)體 Q oS 約束全不 滿足或各滿足一個(gè)或全滿足 , 則子樹間隨機(jī)用“ 最 短延時(shí)路徑” 、 “ 最小延時(shí)抖動(dòng)路徑”和“ 最小費(fèi)用 路徑”連接 。交叉完成后 , 新的子女個(gè)體以概率 P m

9、 進(jìn)行變 異 , 變異概率取 01053。 變異規(guī)則如下 :從新子女 個(gè)體中 , 隨機(jī)選擇一些中間節(jié)點(diǎn) (非組播源節(jié)點(diǎn)和 目的節(jié)點(diǎn) , 刪除連接這些節(jié)點(diǎn)的路徑形成零散子 樹 , 然后依照與交叉操作相類似的連接方法連接各 零散子樹 , 但“ 最短延時(shí)路徑” 、 “ 最小延時(shí)抖動(dòng)路 徑”和“ 最小費(fèi)用路徑”隨機(jī)選擇 。本文采用如下的算法結(jié)束條件 :當(dāng)相同的最優(yōu) 個(gè)體在群體中占據(jù)的比例大于時(shí) , 結(jié)束算法操作 , 最終結(jié)果為算法最后一代中的最優(yōu)個(gè)體 。2 實(shí)驗(yàn)及其分析采用美國(guó)州際通信網(wǎng)進(jìn)行實(shí)驗(yàn) 4, 拓?fù)鋱D見圖 1, 該網(wǎng)共有 28個(gè)節(jié)點(diǎn) 、 45條邊 。拓?fù)鋱D上的數(shù) 據(jù) (d , d j , c

10、采用文獻(xiàn) 5的數(shù)據(jù) 。算法采用 C 語言編程對(duì)含 Q os 約束的組播路由進(jìn)行計(jì)算 。實(shí)驗(yàn)主要驗(yàn)證算法的收斂性 、 收斂速度和收斂過程 。文獻(xiàn) 6證明 , 具有變異概率 P m (0, 1 , 交叉概率 P c 0, 1, 同時(shí)采用比例選擇和最優(yōu) 個(gè)體保留的遺傳算法可收斂到全局最優(yōu)解 。 而本文 提出的遺傳算法具有以下特點(diǎn) : 以概率 1進(jìn)行交 叉 ; 變異概率為 0105; 最優(yōu)個(gè)體保留和比例 選擇 。 故本文提出的混合遺傳算法定能收斂到全局 最優(yōu)解 。 0到節(jié)點(diǎn) 9、 11、 18、 2790ms ,ms , 值為 018, 初始溫度 T 0采用初始群體平均適應(yīng)度值 (15 f i -be

11、gin , 本文取值為 01001 464。實(shí)驗(yàn)的平均收斂代數(shù)為 8代 , 收斂結(jié)果如圖 1所示 。 表 1是算法計(jì)算中的一次實(shí)例 數(shù)據(jù) 。圖 1 美國(guó)州際通信網(wǎng)中節(jié)點(diǎn) 0到節(jié)點(diǎn)9, 11, 18, 21, 27的最佳路由 Fig 11 An optimal router of U 1S 1interstatecommunication netw ork3 結(jié) 論本文對(duì)延時(shí) 、 延時(shí)抖動(dòng)約束的最優(yōu)組播路由問 題進(jìn)行了研究 , 提出了一種性能良好的混合遺傳算法 。 實(shí)驗(yàn)結(jié)果表明此混合遺傳算法的性能良好 , 收 斂速度很快 。本文針對(duì)基本遺傳算法中存在的不 足 , 采用混合遺傳算法對(duì)其進(jìn)行改進(jìn) ,

12、 主要是在基 本遺傳算法的基礎(chǔ)上加入初始群體指導(dǎo)生成 、 模擬 退火算法對(duì)適應(yīng)度拉伸以及采用啟發(fā)式算法進(jìn)行交 叉連接 。 初始群體的指導(dǎo)生成目的是為了使初始群 體具有一定的優(yōu)良性 , 從而使算法從第 1代開始就 能在較好的搜索空間中進(jìn)行搜索 , 從而加快算法的 收斂速度 。64中山大學(xué)學(xué)報(bào) (自然科學(xué)版 第 44卷 表 1 本算法計(jì)算中的一次實(shí)例數(shù)據(jù)T ab 11 An exam ple data編號(hào) 1代 2代 3代 4代1(161,29,441 13(109,21,408 13(74,15,344 11(74,15,333 2(145,29,470 1(161,29,441 1(109,2

13、1,408 4(103,18,3963(139,26,515 5(166,24,588 11(98,25,454 7×12(71,14,371 4(182,27,566 9(168,32,520 15(103,18,396 11×14(76,14,370 5(166,24,588 10(201,37,595 1×10(87,14,383 5×9(74,15,3396(130,20,466 8×15(121,20,533 2×13(,14,370 (82,12,396 7(134,28,407 1×13(79,16,384 &

14、#215;12(,15 510(76,14,483 8(151,28,532 3×5(74,15,457 (85,482474,15,3389(168,32,520 (,15(3×6(71,14,371 10(201,37,1411(98,25,414 6×12(71,14,357 11(192398,454 7×8(74,15,333 3×8(86,18,45512(16610×11(74,15,359 7×9(68,11,371 3×13(76,14,365 13(109,21,408 3×14(74

15、,15,344 5×7(76,14,374 8×9(82,19,33114(134,21,431 6×7(87,14,411 6×14(90,12,362 1×13(76,14,365 ( ( ( (編號(hào) 5代 6代 7代 8代11(74,15,333 1(74,15,333 1(74,15,333 1(74,15,333 29(71,14,371 6(74,15,333 2(74,15,333 2(74,15,333 312(76,14,365 12(74,15,333 3(74,15,333 3(74,15,333 48×13(6

16、9,15,339 2×13(69,15,339 5(74,15,333 4(74,15,333 55×6(82,14,349 12×15(74,15,333 6(74,15,333 5(74,15,333 612×13(74,15,533 4×12(74,15,333 9(74,15,333 6(74,15,333 71×6(82,19,331 11×15(76,14,364 10(74,15,333 7(74,15,333 82×6(82,12,384 11×13(69,15,339 11(74,15,

17、333 8(74,15,333 910×11(76,14,483 3×6(74,15,333 3×12(74,15,338 11(74,15,333 104×15(69,15,345 6×7(74,15,333 2×15(69,15,339 9×12(74,15,338 117×14(76,14,364 6×14(74,15,333 9×15(74,15,333 12×13(74,15,338 121×14(74,15,333 1×15(74,15,338 12&#

18、215;13(69,15,339 6×14(74,15,338 138×15(69,15,339 2×11(71,14,365 5×12(74,15,338 2×4(74,15,333 141×4(74,15,338 9×10(74,15,338 2×4(69,15,339 8×9(74,15,333 152×4(76,14,370 8×9(69,15,339 2×14(74,15,338 4×12(69,15,339 1 表示當(dāng)代中最優(yōu)個(gè)體 , 表示經(jīng)比例選擇選中

19、而被保留的個(gè)體 。 每個(gè)個(gè)體用 (d , dj, c 表示性能 , 左側(cè)數(shù)據(jù)表示此個(gè) 體來源 , 如 12表示此個(gè)體由上代個(gè)體 12直接保留而來 ,4×15表示此個(gè)體由上代 4、 15個(gè)體交叉生成 。參考文獻(xiàn) :1 K OMPE LLA V P. Multicasting for multimedia applications C.IEEE I NFOC OM 92, 1992:2078-2085.2 H O LLAND J H. Adaptation in nature and artificial systems M.M ichigan :The University of M

20、ichigan Press ,1975. 3 王征應(yīng) . 基于啟發(fā)式遺傳算法的 Q oS 組播路由問題的 求解 J.計(jì)算機(jī)學(xué)報(bào) ,2001(1 :55-61.4 WI NTER P. S teiner Problem in Netw orks :A Survey C . Netw orks , 1987:129-167. 5 吳新余 . Internet 中的多播路由選擇算法 J.南京郵電 學(xué)院學(xué)報(bào) (自然科學(xué)版 ,1999(2 :1-36 陳國(guó)良 . 遺傳算法及其應(yīng)用 M.北京 :人民郵電出版 社 ,1996.7 HW ANG F K. S teiner tree problemsC.Net

21、w orks , 1992: 55-89.8 ZH U Q. A s ource-based alg orithm for delay -constrained minimal cost multicasting C .Proc IEEE I NFOC OM 95, 1995:377-384.74 第 2期 謝黎明等 :基于混合遺傳算法的多約束組播路由問題的求解 Solution of Q oS Multicast R outing Problems B ased on HGAXIE Li -ming 1, YU Feng -ren 2, QIU Hai -ming 2(1. G uangdo

22、ng Industry T echnical C ollege , G uangzhou 510300,China ;2. Department of E lectronics and C ommunication Engineering ,Sun Y at-sen University ,G uangzhou 510275,China Abstract :A hybrid genetic alg orithm (HG A was presented to delay least-cost multicast routing problem. G enetic alg orithm (C A

23、that simulates the ev olution process of a creature , for com plicated search space. G A does not need im plemented in parallel distributed process , s o that it is effective in sK ey w ords :hybrid genetic alg orithm (HG A ; multicast ; Q oS ; simulated annealing alg orithm (S A ; instructional preliminary colony building ; heuristic cross over operation(上接第 41頁(yè) A R obust ARMA System Ident