基于混合遺傳免疫粒群優(yōu)化的網(wǎng)絡(luò)擁塞控制方法

孔金生，肖 天，徐 津

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

0 引言

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

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

1 混合的遺傳免疫粒群優(yōu)化算法

1.1 算法設(shè)計(jì)

遺傳免疫粒群算法通過(guò)將遺傳算法中的交叉變異機(jī)制和免疫算法中的識(shí)別選擇思想引入PSO，提高適應(yīng)度好的個(gè)體機(jī)率，并利用已經(jīng)產(chǎn)生的優(yōu)秀個(gè)體與隨機(jī)產(chǎn)生的微粒個(gè)體進(jìn)行交叉變異產(chǎn)生新微粒，與此同時(shí)微粒的多樣性也不會(huì)受到影響［8］.具體算法如下

①對(duì)微粒群進(jìn)行初始化，(含n個(gè)微粒);

②算出每個(gè)粒子的適應(yīng)度值;

③判斷每個(gè)粒子的當(dāng)前適應(yīng)度值，若優(yōu)于個(gè)體極值，則用當(dāng)前適應(yīng)度值替換個(gè)體極值，再將每個(gè)粒子的當(dāng)前個(gè)體極值與全局極值做比較，若優(yōu)于全局極值，則用該個(gè)體極值替換全局極值，并將當(dāng)前粒子保存至記憶庫(kù);

④基于個(gè)體最優(yōu)和全體最優(yōu)值更新粒子;

⑤判斷是否滿足終止條件，若滿足則結(jié)束，不滿足則進(jìn)行下一步;

⑥判定是否出現(xiàn)“早熟”現(xiàn)象，若沒(méi)有，轉(zhuǎn)②，否則進(jìn)行下一步;

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

1.2 性能測(cè)試

采用IGAPSO和標(biāo)準(zhǔn)PSO針對(duì)一個(gè)標(biāo)準(zhǔn)的多峰測(cè)試函數(shù)進(jìn)行優(yōu)化，來(lái)比較兩者在“逃逸”局部極值方面的能力［9］.

圖1 測(cè)試函數(shù)圖像Fig.1 Image of test function

2種算法中均取粒子數(shù)40，設(shè)置循環(huán)結(jié)束條件為達(dá)到最大迭代次數(shù)10 000.2種算法的性能測(cè)試結(jié)果如圖2、圖3所示，結(jié)果表明標(biāo)準(zhǔn)PSO在第607代陷入了局部最優(yōu)值15.919 4，全程耗時(shí)653.812 000 s，而IGAPSO則在第4 451代得到了全局最優(yōu)值 1.7764×10-15，全程耗時(shí)538.609 000 s.可見(jiàn)，經(jīng)過(guò)改進(jìn)，遺傳免疫粒群算法在“逃逸”局部極值方面的能力得到了顯著增強(qiáng).

圖2 標(biāo)準(zhǔn)PSO算法性能測(cè)試結(jié)果Fig.2 Performance test result of standard PSO

圖3 IGAPSO算法性能測(cè)試結(jié)果Fig.3 Performance test result of

2 遺傳免疫粒群算法在網(wǎng)絡(luò)擁塞控制中的應(yīng)用

仿真采用的網(wǎng)絡(luò)拓?fù)淠Ｐ褪请S機(jī)產(chǎn)生的，結(jié)構(gòu)如圖4所示，共有15個(gè)節(jié)點(diǎn).每條鏈路設(shè)置帶寬和延遲兩個(gè)QoS(Quality of Service)參數(shù)點(diǎn)，分別用B和D表示.假設(shè)現(xiàn)在有2個(gè)業(yè)務(wù)流分別應(yīng)用到網(wǎng)絡(luò)中，共同經(jīng)過(guò)鏈路9—13，業(yè)務(wù)流1所需B1=70，D1=10;業(yè)務(wù)流2 所需 B2=80，D2=12;鏈路9-13的鏈路帶寬B3=70.

圖4 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)Fig.4 Image of network topology

由于遺傳免疫粒群優(yōu)化算法選擇網(wǎng)絡(luò)資源較為充足的鏈路，而傳統(tǒng)算法選擇網(wǎng)絡(luò)中最短的路徑.2個(gè)業(yè)務(wù)流同時(shí)發(fā)送請(qǐng)求，遺傳免疫粒群算法與傳統(tǒng)算法優(yōu)化結(jié)果比較如表1所示.

表1 IGAPSO與傳統(tǒng)算法的比較結(jié)果Tab.1 Comparison result of IGAPSO and tradition algorithm

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

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

3 結(jié)論

筆者將遺傳算法和免疫算法引入到微粒群算法中，形成了基于遺傳免疫粒群的優(yōu)化算法(IGAPSO)，該算法既提高了算法跳出局部最優(yōu)的能力，又保證了群體的多樣性，在克服各個(gè)算法缺點(diǎn)的同時(shí)能更大發(fā)揮各自的優(yōu)點(diǎn).最后將遺傳免疫粒群算法應(yīng)用到網(wǎng)絡(luò)擁塞控制中，提出一種基于混合的遺傳免疫粒群優(yōu)化的網(wǎng)絡(luò)擁塞控制方法來(lái)解決網(wǎng)絡(luò)擁塞現(xiàn)象，通過(guò)仿真研究，驗(yàn)證了該方法的可行性.

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

［2］劉紅，白棟，丁煒，等.多目標(biāo)的 Internet路由優(yōu)化控制算法［J］.電子學(xué)報(bào)，2004，32(2):306-308.

［3］王小平，曹立明.遺傳算法—理論、應(yīng)用與軟件實(shí)現(xiàn)［M］.西安:西安交通大學(xué)出版社，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］玄光男，程潤(rùn)偉，汪定偉，等.遺傳算法與工程設(shè)計(jì)［M］.北京:科學(xué)出版社，2000.

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

［8］朱洪程.基于遺傳免疫微粒群算法的工程項(xiàng)目多目標(biāo)綜合優(yōu)化研究［D］.天津:天津大學(xué)管理與經(jīng)濟(jì)學(xué)院，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算法的模糊流水車間調(diào)度問(wèn)題［J］.計(jì)算機(jī)工程與應(yīng)用.2012，48(2):238-240.