基于混合遺傳免疫粒群優化的網絡擁塞控制方法

孔金生，肖 天，徐 津

(1.鄭州大學電氣工程學院，河南鄭州450001;2.華中科技大學電子與信息工程系，湖北武漢430074)

0 引言

近年來，經濟的飛速發展已經帶動了網絡技術的巨大進步，而Internet作為發展最廣泛、最迅速的計算機網絡，在人類的生活中有著不可替代的作用.當過多的數據包存在網絡中時，網絡的整體性能就會下降，這種現象稱為擁塞.擁塞會降低吞吐量、延時等一些性能指標，影響網絡運行的穩定性和服務質量，因此，通過適當的方法來預防和控制擁塞是目前網絡研究的一個熱點問題［1-2］.利用全局搜索尋優技術的智能優化算法在網絡優化領域得到了廣泛應用，包括微粒群算法(PSO)、遺傳算法(Genetic Algorithm，GA)、免疫算法(Immune Algorithm，IA)等優化算法［3-4］.微粒群算法實現方便，具有良好的收斂性［5］;遺傳算法的全局搜索能力強，具有較好的魯棒性，不易陷入局部最優［6］;免疫算法具有種群多樣性，速度相對快，易獲得全局最優解等優越性.這些優化算法還存在一些問題，例如微粒群算法在處理復雜優化問題時出現過早收斂，不能盡快找到最優解;遺傳算法初始種群往往是隨機生成的，導致算法的收斂時間長［7］;免疫算法易陷入局部最優，這些優化算法在解決實際問題時會受到一定的限制.

筆者將遺傳算法和免疫算法引入到微粒群算法中，形成了遺傳免疫粒群優化算法(簡稱IGAPSO)，這種混合的策略并不是對3種算法的簡單拼湊，也不是機械的繼承，通過理論分析研究，IGAPSO算法既提高了跳出局部最優的能力，又保證了群體的多樣性，提高了尋優效率.仿真結果驗證了該優化算法的可行性，最后將遺傳免疫粒群算法應用到網絡擁塞控制中，提出一種基于混合遺傳免疫粒群優化的網絡擁塞控制方法.

1 混合的遺傳免疫粒群優化算法

1.1 算法設計

遺傳免疫粒群算法通過將遺傳算法中的交叉變異機制和免疫算法中的識別選擇思想引入PSO，提高適應度好的個體機率，并利用已經產生的優秀個體與隨機產生的微粒個體進行交叉變異產生新微粒，與此同時微粒的多樣性也不會受到影響［8］.具體算法如下

①對微粒群進行初始化，(含n個微粒);

②算出每個粒子的適應度值;

③判斷每個粒子的當前適應度值，若優于個體極值，則用當前適應度值替換個體極值，再將每個粒子的當前個體極值與全局極值做比較，若優于全局極值，則用該個體極值替換全局極值，并將當前粒子保存至記憶庫;

④基于個體最優和全體最優值更新粒子;

⑤判斷是否滿足終止條件，若滿足則結束，不滿足則進行下一步;

⑥判定是否出現“早熟”現象，若沒有，轉②，否則進行下一步;

⑦隨機生成n/2個粒子，再在記憶庫中隨機選出n/2個粒子，兩部分粒子共同構成新的微粒群，對新微粒群中的各微粒，基于其適應度大小和濃度賦予各自參與交叉和變異運算的選擇概率，粒子依概率進行交叉變異運算，得到下一代粒子群，然后返回進行②.

1.2 性能測試

采用IGAPSO和標準PSO針對一個標準的多峰測試函數進行優化，來比較兩者在“逃逸”局部極值方面的能力［9］.

圖1 測試函數圖像Fig.1 Image of test function

2種算法中均取粒子數40，設置循環結束條件為達到最大迭代次數10 000.2種算法的性能測試結果如圖2、圖3所示，結果表明標準PSO在第607代陷入了局部最優值15.919 4，全程耗時653.812 000 s，而IGAPSO則在第4 451代得到了全局最優值 1.7764×10-15，全程耗時538.609 000 s.可見，經過改進，遺傳免疫粒群算法在“逃逸”局部極值方面的能力得到了顯著增強.

圖2 標準PSO算法性能測試結果Fig.2 Performance test result of standard PSO

圖3 IGAPSO算法性能測試結果Fig.3 Performance test result of

2 遺傳免疫粒群算法在網絡擁塞控制中的應用

仿真采用的網絡拓撲模型是隨機產生的，結構如圖4所示，共有15個節點.每條鏈路設置帶寬和延遲兩個QoS(Quality of Service)參數點，分別用B和D表示.假設現在有2個業務流分別應用到網絡中，共同經過鏈路9—13，業務流1所需B1=70，D1=10;業務流2 所需 B2=80，D2=12;鏈路9-13的鏈路帶寬B3=70.

圖4 網絡拓撲結構Fig.4 Image of network topology

由于遺傳免疫粒群優化算法選擇網絡資源較為充足的鏈路，而傳統算法選擇網絡中最短的路徑.2個業務流同時發送請求，遺傳免疫粒群算法與傳統算法優化結果比較如表1所示.

表1 IGAPSO與傳統算法的比較結果Tab.1 Comparison result of IGAPSO and tradition algorithm

由表1可以看出采用遺傳免疫粒群優化算法的業務流1、2都會選擇最適合的路徑，使網絡負載利用得更加均勻，而傳統算法只選擇最短路徑，造成丟包率很高，網絡無法滿足業務流對帶寬的需求，也浪費了其它合適路徑的網絡資源.圖5反映了網絡優化前后鏈路9—13的吞吐量，顯然優化后的網絡資源利用更合理，吞吐量更高，也保證了以后的業務請求.因此，遺傳免疫粒群算法在避免出現網絡擁塞的前提下合理利用網絡負載，盡量降低網絡資源消耗，提高吞吐量.

圖5 鏈路9—13的吞吐量Fig.5 Throughput of link 9—13

3 結論

筆者將遺傳算法和免疫算法引入到微粒群算法中，形成了基于遺傳免疫粒群的優化算法(IGAPSO)，該算法既提高了算法跳出局部最優的能力，又保證了群體的多樣性，在克服各個算法缺點的同時能更大發揮各自的優點.最后將遺傳免疫粒群算法應用到網絡擁塞控制中，提出一種基于混合的遺傳免疫粒群優化的網絡擁塞控制方法來解決網絡擁塞現象，通過仿真研究，驗證了該方法的可行性.

［1］楊新宇，曾明，江曉，等.一種新的自適應網絡擁塞控制算法［J］.計算機工程，2004，30(8):17-18.

［2］劉紅，白棟，丁煒，等.多目標的 Internet路由優化控制算法［J］.電子學報，2004，32(2):306-308.

［3］王小平，曹立明.遺傳算法—理論、應用與軟件實現［M］.西安:西安交通大學出版社，2002.

［4］EAGELS P K，NOCOL V M.Recent approaches to global optimization problems through particle swam optimization［J］.Natural Computing，2002，12(1):235-306.

［5］謝曉峰，張文俊，楊之廉.微粒群算法綜述［J］.控制與決策，2003，18(2):129-134.

［6］玄光男，程潤偉，汪定偉，等.遺傳算法與工程設計［M］.北京:科學出版社，2000.

［7］趙靜，孔金生.基于遺傳算法和禁忌搜索的混合優化策略［J］.計算機工程與設計，2009，30(23):5489-5491.

［8］朱洪程.基于遺傳免疫微粒群算法的工程項目多目標綜合優化研究［D］.天津:天津大學管理與經濟學院，2010.

［9］ALFI A.PSO with adaptive mutation and inertia weight and its application in parameter estimation of dynamic systems［J］.Acta Automatica Sinica.2011，37(5):541-549.

［10］金超，葉春明.基于QPSO算法的模糊流水車間調度問題［J］.計算機工程與應用.2012，48(2):238-240.