隨著網絡應用越來越廣泛，在傳統的HTTP、FTP、E-mail等數據業務的基礎上增加了各種實時和多媒體業務。要滿足這些業務的需求，特別是要保證一些實時業務的帶寬、時延等特殊需求，僅以目前Internet中"盡最大努力交付"的服務是難以完成的。因此，組播技術的研究成為這個領域的熱點，同時也對于組播的服務質量提出了更高的要求，QoS組播的需求已成為Internet相關技術的研究熱點。Qos組播路由技術是網絡支持QoS保證的關鍵技術之一，因此，高效的QoS組播路由算法就顯得至關重要。QoS（Quality of Service）服務質量，是網絡的一種安全機制， 是用來解決網絡延遲和阻塞等問題的一種技術。 在正常情況下，如果網絡只用于特定的無時間限制的應用系統，并不需要QoS,比如Web應用，或E-mail設置等。但是對關鍵應用和多媒體應用就十分必要。當網絡過載或擁塞時，QoS 能確保重要業務量不受延遲或丟棄，同時保證網絡的高效運行。網絡資源總是有限的，只要存在搶奪網絡資源的情況，就會出現服務質量的要求。服務質量是相對網絡業務而言的，在保證某類業務的服務質量的同時，可能就是在損害其它業務的服務質量。例如，在網絡總帶寬固定的情況下，如果某類業務占用的帶寬越多，那么其他業務能使用的帶寬就越少，可能會影響其他業務的使用。因此，網絡管理者需要根據各種業務的特點來對網絡資源進行合理的規劃和分配，從而使網絡資源得到高效利用。

遺傳算法GA（Genetic Algorithm）的特點在于具有搜索能力、潛在的并行性及較強的魯棒性，計算過程簡單，能很好地解決開發最優解和探尋搜索空間的矛盾；蟻群算法（ant colony optimization, ACO），又稱螞蟻算法，是一種用來在圖中尋找優化路徑的機率型算法。它由Marco Dorigo于1992年在他的博士論文中提出，其靈感于螞蟻在尋找食物過程中發現路徑的行為。蟻群算法是一種模擬進化算法，初步的研究表明該算法具有許多優良的性質。針對PID控制器參數優化設計問題，將蟻群算法設計的結果與遺傳算法設計的結果進行了比較，數值仿真結果表明，蟻群算法具有一種新的模擬進化優化方法的有效性和應用價值。各個螞蟻在沒有事先告訴他們食物在什么地方的前提下開始尋找食物。當一只找到食物以后，它會向環境釋放一種信息素，吸引其他的螞蟻過來，這樣越來越多的螞蟻會找到食物！有些螞蟻并沒有象其它螞蟻一樣總重復同樣的路，他們會另辟蹊徑，如果令開辟的道路比原來的其他道路更短，那么，漸漸，更多的螞蟻被吸引到這條較短的路上來。最后，經過一段時間運行，可能會出現一條最短的路徑被大多數螞蟻重復著。

將遺傳算法和蟻群算法用于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組播路由的有效算法。