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

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


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

    對于非智能蟻群M2，選擇前進策略是不考慮任何信息素的反饋信息，隨機選擇下一節點，其前進策略如下：
 
    圖2表示網絡費用與迭代次數的關系，目的節點為20個，從圖中可以看出，隨著迭代次數的增加，該算法比基本蟻群算法具有更快的收斂性，最終組播樹的費用也更低，與參考文獻[7]算法相比收斂速度上相差無幾，但是最終最優組播樹的費用更低。

    針對蟻群算法的特點進行了改進，將遺傳算法和蟻群算法相融合，并結合多蟻群的行為，提出了GAMAC_QoS組播路由算法。通過仿真實驗證明，該算法相比于基本蟻群算法和參考文獻[7]算法，在多節點中尋找組播樹，具有更好的尋優能力、可靠性更高，是一種解決QoS組播路由的有效算法。該算法涉及參數較多，對于不同規模模型的網絡的最佳參數設置問題，值得今后深入研究。
參考文獻
[1] 孫倩，王新華，劉麗.QoS組播路由算法分析[J].計算機技術與發展，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組播路由問題求解[J].電子學報，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組播路由問題的研究[J].計算機工程與應用，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.