混合智能算法在多約束優化問題中的應用

摘要：提出了一種將蟻群算法、遺傳算法和粒子種群優化融合的混合智能算法來解決多約束最優路徑和QoS路由問題。采用蟻群算法進行尋徑生成初始群體，利用遺傳算法對路徑進行優化，利用PSO算法來優化蟻群算法中的信息素，優勢互補。仿真結果表明該算法是可行、有效的。

關鍵詞：多約束最優路徑； QoS路由; 蟻群算法； 遺傳算法； 粒子種群優化

中圖分類號：TP301文獻標志碼：A

文章編號：1001－3695(2008)04－1039－04

近年來，通過模擬生物群體的行為來解決計算問題已經成為新的研究熱點。通過對生物群體的研究發現，生物群體內個體間的合作和競爭等復雜行為產生的群體智能往往能對某些特定的問題提供高效的解決方法。例如，受自然界中真實蟻群行為的啟發，在20世紀90年代，意大利學者 M.Dorigo等人通過模擬自然界螞蟻尋徑的行為，提出了一種全新的模擬進化算法——蟻群算法[1~3]。蟻群算法主要是通過螞蟻群體之間的信息交流與相互協作最終找到最優解。

遺傳算法[4]是由美國Michigan大學的John Holland教授等人于1975 年首先提出的模擬自然界中生物遺傳機制的隨機搜索算法，通過選擇、交叉、變異等優化過程設計人工尋優方法。遺傳算法易于與其他的技術算法相結合，形成性能更好的問題求解方法。美國的Eberhart和Kennedy[5~7]為了模擬鳥群、魚群、蜂群等生物群體的社會性行為，引入了一種新的基于種群的優化算法，即粒子種群優化(PSO)算法。

近年來，Internet的QoS實現問題已成為下一代Internet相關技術研究的熱點。QoS路由是網絡多媒體信息傳輸的關鍵之一，在這方面已有不少的研究成果。一般來說，網絡中的鏈路都會與多個QoS約束關聯，多約束路徑(multi－constrained path，MCP)選擇問題，即尋找同時滿足多個獨立的QoS約束的路徑問題，是NP完全問題[8]。國內外許多研究人員曾用遺傳算法[9]、螞蟻算法[10]、點火耦合神經網絡方法[11]等求解多約束QoS路由選擇問題，取得了很好的效果。

遺傳算法具有大范圍全局搜索能力，但對反饋信息利用不夠，當解到一定范圍時往往做大量無為的冗余迭代；蟻群算法具有反饋機制但收斂速度慢；PSO算法收斂速度較快，但不能保證得到最優解。本文對各算法取長補短，嘗試將融合蟻群算法、遺傳算法和粒子種群優化的混合智能算法來解決多約束最優路徑和QoS路由問題。

1多約束路由問題

假定以帶權有向圖G=(N，E)表示一個網絡。其中：N、E分別是網絡節點和鏈路的集合；為了便于表達，同時也用N和E 表示節點數目和鏈路數目。QoS度量指標的數目為m，則每條鏈路具有一個m維的鏈路權重向量。路徑度量可能是加性的(如時延、抖動和分組丟失率的對數)，則總權重為該路徑上所有鏈路的權重之和;也可取路徑上的最小(或最大)的QoS權重(如可利用帶寬)。本文只考慮相加性的約束，如帶寬等約束可以通過對路徑進行過濾，修剪除去不符合要求的鏈路。多約束QoS路由問題的基本概念如下:

定義1多約束路徑。對于網絡G(N，E)，每一條鏈路(u，v)∈E具有m個加性權重wi(u，v)≥0 (i=1，…，m)組成的鏈路權重向量。假設存在m個約束Li( i=1，…，m)，該問題在于發現一條從源點s到目的點d的路徑P，使得

2．3遺傳算法的定義和設置

1）編碼與適應度函數

根據網絡拓撲圖，節點上的節點序列即為染色體編碼，一個節點序列就是一條染色體。因為各節點是由改進后的蟻群算法路由得到的，因此序列中不可能有相同的節點，避免了路由環路。本算法的適應度函數利用式（3）進行計算。

2）初始群體

采用按改進后的蟻群算法搜索到y條路徑，以此作為初始群體，y為群體規模。適應度函數是評價個體優越性的標準。

3）選擇方法

采用最佳個體保留策略和賭輪法相結合的選擇方法，即在群體交叉之前選出最佳個體，直接遺傳到子代群體中，其余個體采用賭輪法。

4）交叉和變異算子

由于本算法的編碼是不定長的，采用以設定的交叉概率pc 。具體操作如下：a)從群體（路徑集）中隨機選擇兩個個體（路徑）p1、p2，將兩條路徑中所有的路由交叉點（若無交叉點，則不進行交叉操作）與源節點和目的節點形成一節點集。b)從上述節點集中隨機地選取兩個節點m、n，交換路徑p1、p2中m、n之間的路徑段（交換的兩個路徑段路由方向必須相同）。交叉操作后的每個新路徑中如果出現相同的節點，則刪除相同節點間的路徑，以防止交叉后的新路徑中有環路。

變異操作的目的在于保持群體的多樣性，避免求解過程陷入局部最優。本算法以設定的變異概率pm選擇某個個體Pi（路徑），產生一個隨機概率p。如果p≤pm，則對Pi實行變異。具體操作如下：a) 隨機選中Pi中的一個節點c，再以c為源節點，以初始的目的節點為目的節點， 利用優化后的蟻群算法搜索網絡圖，得到從c到目的節點的路徑。b)將得到的從c到目的節點的另一條新路徑替換原路徑Pi。如果變異后的新路徑出現相同的節點，則刪除相同節點間的路徑，以防止變異后的新路徑中有環路。

3智能算法實現多約束優化

本文提出一種將蟻群算法、PSO算法和遺傳算法進行融合的算法來實現多約束優化問題的求解。三種算法的有機融合很好地互補了各個算法的缺點，更好地發揮了每個算法的優點。算法為了提高效率，對QoS路由問題進行了兩點簡化：a)在算法迭代中不考慮抖動，而是在之前進行處理。因為抖動可通過目的節點的緩沖進行平滑，故為簡化問題，只考慮目的節點的抖動；b)對于帶寬限制，之前先對網絡拓撲進行過濾，通過刪除帶寬小于需求帶寬的鏈路，把網絡濾成一個新的簡單網絡。

算法的偽代碼如下：

4仿真結果及分析

4．1多約束問題

本文研究的QoS本質是對一個有向圖在四種約束條件下最小費用問題。為了清楚地研究問題，本文首先來研究最短路問題。仿真實驗中使用的網絡拓撲如圖1所示。該拓撲是對ANSNET[12]是通過增加附加鏈路修改而得到的，文獻[13~15]中也使用了同樣的拓撲結構，目標函數利用式（3）。

實驗中每條鏈路關聯兩個權值:w1和w2，每次實驗的權值從該網絡拓撲中隨機選擇。仿真程序隨機產生連接請求，并利用各種算法為這些請求尋找可行路徑。如果算法為一個連接請求找到了一條可行路徑，則定義該請求為一個成功路由連接請求。用參數成功率、無效率來表征算法的性能。同時，實驗中分別引入了Chen等人[13]提出的最短路徑算法（x=5）、Zhang等人[15]提出的相同度量相遇算法以及最優算法（最優算法在已簡化和標記的圖中搜索所有可能的路徑來決定是否存在一條可行路徑）與本文的算法進行比較。

5結束語

本文結合混合智能算法在多約束優化問題中的應用，從最短路問題以及QoS路由方面進行了深入的研究。本文提出的算法融合了蟻群算法、PSO算法和遺傳算法，各算法優勢互補，在蟻群算法中加入遺傳變異的進化過程，并且利用PSO算法對信息素進行調整，從而加快了蟻群算法的求解速度，提高了算法尋優的效率。仿真實驗表明，該算法具有較好的性能，是一種有效的求解多約束優化問題的方法。

參考文獻：

[1]DORIGO M， MANIEZZO V， COLORNI A. Ant system: optimization by a colony of cooperating agents[J]. IEEE Trans on Systems，Man，and Cybernetics: Part B， 1996，26(1):28－41.

[2]STUTZLE T， HOOS H H. Max－min ant system[J]. Future Generation Computer System， 2000，16(8):889－914.

[3]ZHANG Su－bing， LIU Ze－min. A QoS routing algorithm based on ant algorithm[C]//Proc of the 25th Annual IEEE International Con－ference on Computer Network. Washington， D C: IEEE Communication Society， 2001:.1581－1585.

[4]陳國良，王煦法，莊鎮泉.遺傳算法及其應用[M].北京:人民郵電出版社，1996.

[5]KENNEDY J， EBERHART R. Particle swarm optimization[C]//Proc of IEEE International Conference on Neural Networks. Piscutaway: IEEE Service Center， 1995:1942－1948.

[6]EBERHART R， KENNEDY J. A new optimizer using particle swarm theory[C]//Proc of the 6th International Symposium on Micro Machine and Human Science. Piscutaway: IEEE Service Center， 1995.

[7]SHI Yu－hui， EBERHART R C. Parameter selection in particle swarm optimization[C]//Proc of the 7th International Conference on Evolutionary Programming. London: Springer－Verlag， 1998:591－600.

[8]ZHENG Wang， CROWCROFT J. Quality－of－service routing for supporting multimedia applications[J]. IEEE Journal on Selected Areas in Communications， 1996，14(7):1228－1234.

[9]FEI Xiang， LOU Jun－zhou， WU Jie－yi， et al. QoS routing based on genetic algorithm[J]. Computer Communications， 1999，22(9):1394－1399.

[10]ZHANG Su－bing， LV Guo－ying， LIU Ze－ming. QoS route attemper algorithm based on ACA[J].Circuit and System Transaction，2000，5(1):1－5.

[11]ZHANG Jun－ying. Multi－QoS route selection algorithm based on ignition coupling nerve network[J]. Communication Transaction， 2002，23(7):40－46.

[12]COMER D E. Internetworking with TCP/IP[M]. 3rd ed.[S.l.]: Prentice Hall， Inc， 1995.

[13]CHEN S， NAHRSTEOT K. On finding multi－constrained paths[C]//Proc of International Conference on Communications.[S.l.]: IEEE， 1998:874－879.

[14]KORKMAZ T， KRUNZ M. A randomized algorithmfor finding a path subject to multiple QoS requirements[J]. International Journal of Computer and Telecommunications Networking， 2001，36(2):251－268.

[15]ZHANG Bao－xian， MOUFTAH H T. A stateless QoS routing algorithm subject to multiple constraints[C]//Proc of IEEE International Conference on Communications.[S.l.]: Institute of Electrical Engineers Inc， 2003:1870－1874.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”