摘  要： 提出了一種基于遺傳多蟻群的QoS組播路由算法，前期利用遺傳算法的快速性、全局收斂性生成蟻群算法的初期信息素；后期引入多蟻群思想，克服蟻群算法容易陷入局部最優(yōu)，導(dǎo)致算法停滯的缺點(diǎn)。仿真結(jié)果表明，該算法在多節(jié)點(diǎn)情況下具有更強(qiáng)的尋優(yōu)能力和可靠性，是一種有效的QoS路由方法。
關(guān)鍵詞： QoS組播；遺傳算法；蟻群算法；多蟻群

    隨著網(wǎng)絡(luò)應(yīng)用越來(lái)越廣泛，在傳統(tǒng)的HTTP、FTP、E-mail等數(shù)據(jù)業(yè)務(wù)的基礎(chǔ)上增加了各種實(shí)時(shí)和多媒體業(yè)務(wù)。要滿足這些業(yè)務(wù)的需求，特別是要保證一些實(shí)時(shí)業(yè)務(wù)的帶寬、時(shí)延等特殊需求，僅以目前Internet中“盡最大努力交付”的服務(wù)是難以完成的[1]。因此，組播技術(shù)的研究成為這個(gè)領(lǐng)域的熱點(diǎn)，同時(shí)也對(duì)于組播的服務(wù)質(zhì)量提出了更高的要求，QoS組播的需求已成為Internet相關(guān)技術(shù)的研究熱點(diǎn)。Qos組播路由技術(shù)是網(wǎng)絡(luò)支持QoS保證的關(guān)鍵技術(shù)之一，因此，高效的QoS組播路由算法就顯得至關(guān)重要。而QoS路由的目的就是在網(wǎng)絡(luò)中尋找滿足用戶對(duì)線路的帶寬、延遲、延遲抖動(dòng)、費(fèi)用要求的路由，即向用戶提供端到端的服務(wù)質(zhì)量保證，而基于多個(gè)不相關(guān)可加度量的QoS路由問(wèn)題是NP完全問(wèn)題。目前一般采用智能優(yōu)化算法來(lái)求解，如遺傳算法、蟻群算法、模擬退火算法等。
    遺傳算法[2]GA(Genetic Algorithm)的特點(diǎn)在于具有搜索能力、潛在的并行性及較強(qiáng)的魯棒性，計(jì)算過(guò)程簡(jiǎn)單，能很好地解決開(kāi)發(fā)最優(yōu)解和探尋搜索空間的矛盾；蟻群算法[3]AC(Ant Colony Algorithm)是一個(gè)增強(qiáng)型學(xué)習(xí)系統(tǒng)，通過(guò)信息素的積累和更新收斂于最優(yōu)路徑上，具有正反饋、分布式的計(jì)算特性和很強(qiáng)的魯棒性。
    將遺傳算法和蟻群算法用于QoS組播路由已經(jīng)取得較好的效果，但是缺點(diǎn)也很明顯。遺傳算法對(duì)于系統(tǒng)中的反饋信息利用不夠，在中后期往往做大量無(wú)謂的迭代，求最優(yōu)解的效率降低；蟻群算法則由于初期螞蟻的隨機(jī)活動(dòng)使得前期信息素的更新較慢、求解速度慢，由于在后期容易早熟，而陷入局部最優(yōu)。
    本文針對(duì)目前應(yīng)用蟻群算法解決NP完全問(wèn)題的研究現(xiàn)狀，以基本蟻群算法為基礎(chǔ)，提出一種遺傳多蟻群融合算法(GAMAC_QoS)來(lái)解決QoS多約束組播路由問(wèn)題，對(duì)多個(gè)約束QoS組播路由問(wèn)題進(jìn)行了研究。利用基本蟻群算法的分布式和全局搜索能力，使信息素積累和更新收斂于最優(yōu)路徑上。


    (3)初始種群生成
    采用隨機(jī)方法從中選擇若干個(gè)個(gè)體組成初始種群，首先刪除不滿足QoS約束條件的節(jié)點(diǎn)以及與之相連的鏈路，再刪除不滿足帶寬要求的鏈路，得到一個(gè)新的精簡(jiǎn)后的網(wǎng)絡(luò)拓?fù)?。利用隨機(jī)深度優(yōu)先算法，生成源節(jié)點(diǎn)為根，目的節(jié)點(diǎn)為葉子的組播樹(shù)。
    (4)選擇算子
    采用個(gè)體最佳保留策略(最佳個(gè)體保留個(gè)數(shù)設(shè)置為2)與采用遺傳算法中運(yùn)用最廣的輪盤(pán)賭選擇機(jī)制執(zhí)行選擇功能。
    (5)交叉算子
    采用Davis順序交叉方法，先進(jìn)行常規(guī)的雙點(diǎn)交叉，再進(jìn)行維持原有相對(duì)訪問(wèn)順序的巡回線路修改[5]。具體交叉如下：
    ①隨機(jī)在父串上選擇一個(gè)交配區(qū)域，如兩父串選定為：
    old1=12|3456|789
    old2=98|7654|321
    ②將old2的交配區(qū)域加到old1的前面，將old1的交配區(qū)域加到old2的前面：
    old1’=7654|123456789
    old2’=3456|987654321
    ③依次刪除old1’，old2’中與交配區(qū)相同的數(shù)碼，得到最終的兩子串：
    new1=765412389
    new2=345698721
    (6)變異算子
    采用逆轉(zhuǎn)變異法逆轉(zhuǎn)。如染色體(1-2-3-4-5-6)在區(qū)間2-3和區(qū)間5-6處發(fā)生斷裂，斷裂片段又以反向順序插入，于是逆轉(zhuǎn)之后的染色體變?yōu)?1-2-5-4-3-6)。這里的進(jìn)化，是指逆轉(zhuǎn)算子的單方向性，只有經(jīng)逆轉(zhuǎn)后，適應(yīng)值有提高的才接受下來(lái)，否則逆轉(zhuǎn)無(wú)效。
2.2 GAMAC_QoS中的多蟻群算法規(guī)則
    GAMAC_QoS算法定義了三種類(lèi)型的螞蟻：
    (1)全智能螞蟻。螞蟻按照傳統(tǒng)蟻群算法選擇規(guī)則選擇下一節(jié)點(diǎn)，此螞蟻稱(chēng)為全智能螞蟻，簡(jiǎn)稱(chēng)為M1。
    (2)非智能螞蟻。螞蟻不按照選擇規(guī)則來(lái)選擇路徑，而是隨機(jī)地選擇下一節(jié)點(diǎn)，此螞蟻稱(chēng)為非智能螞蟻，簡(jiǎn)稱(chēng)為M2。引入非智能螞蟻是為了在算法陷入停滯時(shí)擴(kuò)大搜索空間。
    (3)半智能螞蟻。在選擇下一節(jié)點(diǎn)時(shí)以δ概率按照全智能螞蟻的選擇策略選擇下一節(jié)點(diǎn)，以1－δ概率按照非智能螞蟻的選擇策略選擇下一節(jié)點(diǎn)，此螞蟻稱(chēng)為半智能螞蟻，簡(jiǎn)稱(chēng)為M3?？紤]到算法在陷入停滯的時(shí)候，前期的部分次優(yōu)解還是有價(jià)值的，因此引入半智能螞蟻是最大程度地利用之前的次優(yōu)解，增加搜索最優(yōu)解的成功率。
    算法開(kāi)始之時(shí)，螞蟻的初值全為智能螞蟻，數(shù)目為M，執(zhí)行蟻群算法。當(dāng)算法進(jìn)行到停滯狀態(tài)且比當(dāng)前的參考值差的時(shí)刻，全智能螞蟻發(fā)生變化，一部分轉(zhuǎn)變成非智能螞蟻，一部分轉(zhuǎn)變成半智能螞蟻，余下部分保持全智能螞蟻的性質(zhì)不變，其中半智能螞蟻由智能螞蟻和非智能螞蟻組成，引入?yún)?shù)δ(0<δ<1)來(lái)決定其組成比例。螞蟻狀態(tài)發(fā)生變化后算法得以繼續(xù)推進(jìn)，智能螞蟻的數(shù)目逐漸增加，非智能和半智能螞蟻的數(shù)量逐步減少，最終為零，保證算法的收斂。
    (1)適應(yīng)值函數(shù)與遺傳算法的適應(yīng)值函數(shù)相同。
    (2)路徑選擇策略[6]。全智能螞蟻M1，其選擇策略為：

    對(duì)于非智能蟻群M2，選擇前進(jìn)策略是不考慮任何信息素的反饋信息，隨機(jī)選擇下一節(jié)點(diǎn)，其前進(jìn)策略如下：
 
    圖2表示網(wǎng)絡(luò)費(fèi)用與迭代次數(shù)的關(guān)系，目的節(jié)點(diǎn)為20個(gè)，從圖中可以看出，隨著迭代次數(shù)的增加，該算法比基本蟻群算法具有更快的收斂性，最終組播樹(shù)的費(fèi)用也更低，與參考文獻(xiàn)[7]算法相比收斂速度上相差無(wú)幾，但是最終最優(yōu)組播樹(shù)的費(fèi)用更低。

    針對(duì)蟻群算法的特點(diǎn)進(jìn)行了改進(jìn)，將遺傳算法和蟻群算法相融合，并結(jié)合多蟻群的行為，提出了GAMAC_QoS組播路由算法。通過(guò)仿真實(shí)驗(yàn)證明，該算法相比于基本蟻群算法和參考文獻(xiàn)[7]算法，在多節(jié)點(diǎn)中尋找組播樹(shù)，具有更好的尋優(yōu)能力、可靠性更高，是一種解決QoS組播路由的有效算法。該算法涉及參數(shù)較多，對(duì)于不同規(guī)模模型的網(wǎng)絡(luò)的最佳參數(shù)設(shè)置問(wèn)題，值得今后深入研究。
參考文獻(xiàn)
[1] 孫倩，王新華，劉麗.QoS組播路由算法分析[J].計(jì)算機(jī)技術(shù)與發(fā)展，2009，8(19):97-99.
[2] HOLLAND J H. Adaptation in natural and artificial Systems[M]. Michigan: the University of Michigan Press， 1975.
[3] DORIGO M， GAMBARDELLA L M. Ant colony system: a cooperative learning approach to the traveling salesman problem[J]. IEEE Transactions on Evolutionary Computation， 1997，1(1):53-66.
[4] 孫力娟，王汝傳.基于蟻群算法和遺傳算法融合的QoS組播路由問(wèn)題求解[J].電子學(xué)報(bào)，2006，34(8):1391-1395.
[5] WHITE T， PAGUREK B， OPPACHER F. ASGA:Improving the ant system by integration with genetic algorithms[C]. In: Proe.3rdGenetic Programming Conf.. July 1998.
[6] 張凌，毛力.基于一種新的蟻群算法的QoS組播路由問(wèn)題的研究[J].計(jì)算機(jī)工程與應(yīng)用，2009，45(23):123-126.
[7] GONG B， LI L， WANG X I. A novel QoS multicast routing algorithm based on ant algorithm[C]//International Conference on IEEE Wireless Communications， Networking and Mobile Computing， 2007.