基于遺傳模擬退火算法的多約束QoS組播路由算法①

劉金明， 仲光蘋

(1.黑龍江八一農(nóng)墾大學信息技術學院，黑龍江 大慶 163319;2.東北石油大學數(shù)學科學與技術學院，黑龍江 大慶 163318)

0 引言

多約束QoS組播路由問題實際上就是帶多個QoS約束的Steiner樹問題，是典型的NP完全問題[1]，存在大量基于蟻群算法、遺傳算法等智能搜索算法的求解方法，其中應用最多的就是遺傳算法及其改進算法.文獻[2]中Xiang等提出了基于遺傳算法來求解QoS路由問題，其算法采用的二進制編碼方法，導致其搜索空間會隨著網(wǎng)絡規(guī)模的增大而急劇增大.文獻[3]中Wang等提出基于遺傳算法求解帶寬和時延約束費用最小組播路由問題，其算法采用樹型結構編碼策略，算法的性能較好，但樹形編碼卻帶來了非常復雜的交叉和變異操作.文獻[4]中Hamdan等針對時延和時延抖動約束的費用最小組播路由問題，提出了基于整數(shù)隊列編碼策略的遺傳算法求解方法，算法的編碼方式非常簡單，且效率較高.文獻[5]中劉金明等提出了基于遺傳模擬退火算法求解組播路由問題的相關方法，但是只涉及了帶寬和時延兩個QoS約束條件.文獻[6]中，張琨等提出了基于模擬退火方法的多約束QoS組播路由算法，算法求得的組播路由樹的費用性能較好，但由于模擬退火算法自身的不足，導致算法的效率比較低.本文在前人研究基礎上，提出基于遺傳模擬退火算法的多約束QoS組播路由算法，該組播路由算法采用基于備選路徑集策略的整數(shù)隊列編碼方法，結合模擬退火算法溫度參數(shù)設計適應度函數(shù)，并引入啟發(fā)式交叉操作策略和自適應的交叉變異概率思想，即解決了遺傳算法容易陷入過早的收斂和進化后期搜索效率低的問題，又克服了模擬退火算法自身進化速度慢的缺陷.實驗仿真表明，本文提出的算法求得的組播路由樹具有良好的費用性能，且收斂速度很快.

1 QoS組播路由問題描述

組播網(wǎng)絡可用無向帶權連通圖G=(V，E)來表示，其中V為節(jié)點集，E為鏈路集，R+和R+分別表示正實數(shù)集和非負實數(shù)集.對于任意鏈路e∈E，可定義3種度量，分別為:費用函數(shù)C(e):E→R+，帶寬函數(shù)B(e):E→R+和時延函數(shù)D(e):E→R+;對于任意網(wǎng)絡節(jié)點n∈V，可定義3種度量，分別為費用函數(shù)C(n):E→R+，時延函數(shù)D(n):E→R+和包丟失率函數(shù)PL(n):V→R+.在組播網(wǎng)絡中，給定源節(jié)點s∈V，目的節(jié)點集合M?{V－{s}}，?di，dj∈M，則s和M組成的組播路由樹T(s，M)將存在下列關系:

式中，PT(s，di)為組播路由樹T(s，M)上從給定源節(jié)點s到任意目的節(jié)點di的一條路由路徑，DJ(s，M)為組播路由樹T(s，M)中的最大時延抖動值.

在組播網(wǎng)絡G=(V，E)中，給定源節(jié)點s∈V，目的節(jié)點集合M?{V－{S}}，?di∈M，設定帶寬函數(shù)B(·)∈R+，時延函數(shù)D(·)∈R+，時延抖動函數(shù)DJ(·)∈R+，包丟失率函數(shù)PL(·)∈ R+，費用函數(shù)C(·)∈R+，則多約束QoS組播路由算法求得的組播路由樹T(s，M)必須滿足如下條件:

(1)帶寬約束:B(PT(s，di))≥Bi;

(2)時延約束:D(PT(s，di))≤Di;

(3)時延抖動約束:DJ(s，M)＜DJ;

(4)包丟失率約束:PL(PT(s，di))≤PLi;

(5)費用約束:在所有滿足上述(1)～(4)條件的組播路由樹中，使C(T(s，M))最小.

其中，Bi，Di和PLi分別對應著目的節(jié)點 di的帶寬、時延和包丟失率約束，而DJ是整個組播路由樹的時延抖動約束.

2 多約束QoS組播路由算法

2.1 編碼及種群初始化

在組播網(wǎng)絡中，給定源節(jié)點s和目的節(jié)點集合M，基于備選路徑集的整數(shù)隊列編碼方法就是將染色體編碼成長度為m=|M|的整數(shù)隊列，每一個隊列就是染色體的一個基因，也就是從源節(jié)點到特定目的節(jié)點滿足一定約束條件的路由路徑.本文采用的具體編碼方案如下:

首先，對所有的目的節(jié)點di∈M，計算其備選路徑集.目的節(jié)點di備選路徑集的生成方法為:先對網(wǎng)絡使用帶寬約束Bi進行簡化，再使用Dijkstra第k最短路徑算法找到從給定源節(jié)點s到特定目的節(jié)點di所有滿足時延約束Di和包丟失率約束PLi的路由路徑.設Qi為特定目的節(jié)點di的備選路徑集，則

然后，從所有的目的節(jié)點對應的路徑集中都任選一條路由路徑作為染色體的基因，組成一棵基因個數(shù)為m的組播路由樹，作為初始種群的一個染色體.

按照上述方法生成一定數(shù)量的染色體構成初始種群，完成種群初始化.

2.2 適應度函數(shù)設計

適應度函數(shù)決定了遺傳算法的搜索方向，直接影響遺傳算法的執(zhí)行時間和求解效率.多約束QoS組播路由問題實際上是帶多個約束的費用最小化問題.由于遺傳算法的編碼過程中已經(jīng)去除了帶寬、時延和包丟失率約束，因此目標函數(shù)可以直接表示為

其中，Φ(Z)為懲罰函數(shù)，r為懲罰因子，當組播路由樹滿足時延抖動約束時，其值為0;否則等于r(r為比較大的正實數(shù)).

結合模擬退火算法的溫度參數(shù)，可以將遺傳算法的適應度函數(shù)定義為

式中:fmin為當前代種群中最小目標函數(shù)值，t為當前代溫度值.

此適應度函數(shù)可以使算法在進行賭輪選擇時具有兩點好處:一是在溫度高時(組播路由算法運行早期)，可有效避免個別適應度高的染色體充斥整個種群造成早熟;二是在溫度低時(組播路由算法運行后期)，優(yōu)良染色體具有相對更大的適應度函數(shù)值，使其能夠更容易遺傳給下一代，加快算法的搜索速度.

結合了溫度參數(shù)的新型適應度函數(shù)的使用，可以有效解決傳統(tǒng)遺傳算法自身存在的容易陷入過早收斂和進化后期搜索效率低的問題.

2.3 遺傳參數(shù)設計

2.3.1 選擇操作

選擇操作采用最常用的賭輪選擇的方法，同時為保證算法能夠收斂到全局最優(yōu)解，在進行選擇操作前先使用最優(yōu)保留策略將當前種群中的最優(yōu)解直接復制給下一代種群.

2.3.2 交叉和變異操作

交叉概率Pc和變異概率Pm是遺傳算法設計過程中影響其搜索行為和求解性能的關鍵，直接決定了算法的收斂性能.本文采用自適應的交叉和變異概率計算方法，其計算公式如下:

式中，k1，k2，k3，k4，k5，k6都是常數(shù)，且 k3=k1+k2，k6=k4+k5;fitmax是當前代種群中的最大適應度函數(shù)值，fitavg是當前代種群的平均適應度函數(shù)值;fiti'是兩個要進行交叉操作的染色體中較大的適應度函數(shù)值，fiti是要進行變異操作的染色體的適應度函數(shù)值.

采用此交叉和變異概率計算方法，適應度函數(shù)值較小的染色體計算出的交叉和變異概率都比較大，能夠加快遺傳算法的搜索速度.當前代最優(yōu)染色體的交叉和變異概率是一個較小值，能夠使最優(yōu)染色體參與到生成下一代個體的交叉和變異操作中，進一步加快算法的搜索速度.當fitavg→fitmax使算法陷入問題求解的局部最優(yōu)時，適應度函數(shù)值較大的染色體計算出的交叉和變異概率也將增大，能夠有效提高算法跳出局部最優(yōu)的能力，有效避免“早熟”.但為了防止原有解空間被完全破壞，當|fitmax－fitavg＜ ε時，就固定Pc，Pm值.

算法的交叉操作采用相同鏈路保留的策略.其交叉策略為:按賭輪方法選擇出兩個父代染色體TM和TN，計算其交叉概率Pc，按概率Pc進行交叉操作生成新的染色體Tc.兩個父代染色體中相同的路由路徑(優(yōu)良基因)將直接遺傳給后代染色體，對于路由路徑不同的目的節(jié)點，以di為例，計算兩個父代染色體中目的節(jié)點di對應的路由路徑PM(s，di)和PN(s，di)的路徑費用，將路徑費用小的路由路徑(優(yōu)良基因)作為組成子代染色體從源節(jié)點s到目的節(jié)點di的基因.對兩個父代染色體TM和TN中所有具有不同路由路徑的目的節(jié)點，按上述操作生成子代染色體的基因，完成交叉操作生成一個子代染色體.

算法的變異操作采用位變異的方法.位變異的方法是:任意選取染色體中某個目的節(jié)點di對應的路由路徑(基因)，從其對應的備選路徑集Qi中隨機選擇一條路由路徑作為基因進行替換.

2.4 模擬退火參數(shù)設計

2.4.1 初溫確定和退溫操作

初始溫度的設定采用t0=Kδ的形式，其中K是一個足夠大的數(shù)，且δ=是初始種群的最大和最小目標函數(shù)值.退溫操作采用tn+1=αt的形式，其中0＜α＜1.

2.4.2 構造鄰域解

鄰域解的構造方法采用與變異操作類似的“路徑交換策略”.

圖1 算法收斂性能的分析

圖2 算法費用性能的分析

2.4.3 設置狀態(tài)接受函數(shù)

模擬退火算法的初始種群由遺傳算法提供，組播路由算法運行一輪次后生成的種群，再經(jīng)過一系列的遺傳操作后，將生成新的種群，這個新的種群就是組播路由算法運行每一輪次中模擬退火算法的初始種群.對該初始種群進行基于Metropolis判別準則的選擇復制后，將生成下一代種群，這個種群就組播路由算法運行一輪次后生成的新一代種群.假設為染色體i構造了一個鄰域染色體j，i和j將基于Metropolis判別準則競爭進入下一代種群.Metropolis判別準則為:令Δf=fit(Ti)－fit(Tj)，若Δf≤0，則新染色體j將被復制到下一代種群中;若Δf＞0，則生成一個隨機數(shù) r∈[0，1]，當 r＜exp(－Δf/tn)時，新染色體j仍將被復制到下一代種群中;否則，把染色體i復制到下一代種群中.

通過在Metropolis判別準則中引入溫度參數(shù)，使算法在高溫時接受劣質(zhì)解的能力比較強，保證了種群的多樣性，避免“早熟”.而當溫度下降時，使優(yōu)良染色體更容易遺傳給下一代，加快算法的收斂速度.

2.5 算法的終止準則

2.5.1 內(nèi)部循環(huán)終止準則

內(nèi)部循環(huán)終止準則是算法由模擬退火部分向遺傳算法部分切換的條件，也稱為Metropolis抽樣穩(wěn)定準則.本文采用基于不改變規(guī)則的控制法，在算法的模擬退火部分求解過程中，若求得的最優(yōu)解連續(xù)若干代進化過程中保持不變，則認為滿足了內(nèi)部循環(huán)終止條件，進行退溫操作，并切換到遺傳算法部分進行遺傳操作.

2.5.2 外部循環(huán)終止準則

外部循環(huán)終止準則是整個組播路由算法的終止準則.本文采用循環(huán)總數(shù)控制法和基于不改變規(guī)則的控制法相結合的方法.即當算法達到外部循環(huán)總次數(shù)時，認為達到了外部循環(huán)終止條件;或者算法還沒有達到設定的循環(huán)總次數(shù)，但在一定迭代次數(shù)內(nèi)沒有改變當前最優(yōu)解時，也認為達到了外部循環(huán)終止條件.

3 仿真實驗

本文在VC++6.0編程環(huán)境下對提出的算法進行了仿真.在仿真實驗中，為了仿真方便，將QoS組播路由問題進行簡化，只考慮鏈路的時延和費用兩個度量屬性，鏈路的帶寬，節(jié)點的費用、時延、包丟失率度量屬性都被忽略掉了，相應的QoS約束條件也進行了簡化，只保留時延和時延抖動兩個約束條件.由本文的編碼方案可知，采用簡化后的度量屬性和約束條件不會影響算法仿真的準確性.

通過仿真實驗，主要對提出的多約束QoS組播路由算法的兩點性能進行分析:一是對算法的收斂性能進行分析;二是對算法求得的組播路由樹的費用性能進行分析.

在仿真實驗中，將文獻[4]中提出的基于遺傳算法的時延及時延抖動約束組播路由算法，文獻[6]中提出的基于模擬退火算法的多約束QoS組播路由算法與本文提出的算法在性能和效率上進行了比較.因為上述三個算法所采用的策略不同，所以本文使用CPU執(zhí)行時間來對算法的收斂性能進行分析測試.

圖1展示了本文算法與文獻[4]算法、文獻[6]算法在執(zhí)行時間上的比較結果.而圖2則展示了在不同網(wǎng)絡節(jié)點數(shù)情況下，本文算法與文獻[4]算法、文獻[6]算法在計算出的組播路由樹費用性能上的比較結果.從圖1和圖2不難看出，本文提出的基于遺傳模擬退火算法的多約束QoS路由算法在計算性能和求解效率上具有明顯的優(yōu)勢.

4 結論

本文針對多約束QoS組播路由問題求解的復雜性，提出了一種新型全局智能優(yōu)化算法——遺傳模擬退火算法，并提出了基于遺傳模擬退火算法的多約束QoS組播路由算法.該算法通過采用基于備選路徑集的整數(shù)隊列路徑編碼方案來簡化編解碼操作，結合溫度參數(shù)來設計適應度函數(shù)，即避免了早熟，又加快了進化后期的搜索能力，引入啟發(fā)式交叉操作和自適應的交叉變異概率思想提高算法的計算效率，通過Metropolis判別準則來保證算法的全局收斂性.通過仿真實驗證明，該算法具有收斂速度快，穩(wěn)定性強，費用性能良好的特點，能夠滿足當前多媒體網(wǎng)絡在QoS方面的各種需求.

[1]Stefan Vob.Steiner’s Problem in Graphs:Heuristic Methods[J].Discrete Applied Mathematics，1992，40(1):45 －72.

[2]F.Xiang，L.Junzhou，W.Jieyi，et al.QoS Routing Based on Genetic Algorithm[J].Computer Communications，1999，22(15):1394－1399.

[3]Wang Zhengying，Shi Bingxin，Zhao Erdun.Bandwidth－ delay－constrained Least Cost Multicast Routing Based on Heuristic Genetic Algorithm[J].Computer Communications，2001，24(7):685－692.

[4]M.Hamdan，M.E.El－ Hawary.Multicast Routing with Delay and Delay Variation Constraints Using Genetic Algorithm[J].Proceedings of the Canadian Conference on Electrical and Computer Engineering，2004，4:2363 －2366.

[5]劉金明，王娜，劉勇.基于遺傳模擬退火算法的QoS組播路由問題求解[J].佳木斯大學學報(自然科學版)，2008，26(4):535－538.

[6]張琨，王珩，劉玉風.一種基于模擬退火方法的多約束QoS組播路由算法[J].計算機科學，2005，32(5):41 －45.