混合智能算法在多約束優(yōu)化問題中的應(yīng)用

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

關(guān)鍵詞：多約束最優(yōu)路徑； QoS路由; 蟻群算法； 遺傳算法； 粒子種群優(yōu)化

中圖分類號：TP301文獻(xiàn)標(biāo)志碼：A

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

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

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

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

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

1多約束路由問題

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

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

2．3遺傳算法的定義和設(shè)置

1）編碼與適應(yīng)度函數(shù)

根據(jù)網(wǎng)絡(luò)拓?fù)鋱D，節(jié)點(diǎn)上的節(jié)點(diǎn)序列即為染色體編碼，一個節(jié)點(diǎn)序列就是一條染色體。因?yàn)楦鞴?jié)點(diǎn)是由改進(jìn)后的蟻群算法路由得到的，因此序列中不可能有相同的節(jié)點(diǎn)，避免了路由環(huán)路。本算法的適應(yīng)度函數(shù)利用式（3）進(jìn)行計(jì)算。

2）初始群體

采用按改進(jìn)后的蟻群算法搜索到y條路徑，以此作為初始群體，y為群體規(guī)模。適應(yīng)度函數(shù)是評價(jià)個體優(yōu)越性的標(biāo)準(zhǔn)。

3）選擇方法

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

4）交叉和變異算子

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

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

3智能算法實(shí)現(xiàn)多約束優(yōu)化

本文提出一種將蟻群算法、PSO算法和遺傳算法進(jìn)行融合的算法來實(shí)現(xiàn)多約束優(yōu)化問題的求解。三種算法的有機(jī)融合很好地互補(bǔ)了各個算法的缺點(diǎn)，更好地發(fā)揮了每個算法的優(yōu)點(diǎn)。算法為了提高效率，對QoS路由問題進(jìn)行了兩點(diǎn)簡化：a)在算法迭代中不考慮抖動，而是在之前進(jìn)行處理。因?yàn)槎秳涌赏ㄟ^目的節(jié)點(diǎn)的緩沖進(jìn)行平滑，故為簡化問題，只考慮目的節(jié)點(diǎn)的抖動；b)對于帶寬限制，之前先對網(wǎng)絡(luò)拓?fù)溥M(jìn)行過濾，通過刪除帶寬小于需求帶寬的鏈路，把網(wǎng)絡(luò)濾成一個新的簡單網(wǎng)絡(luò)。

算法的偽代碼如下：

4仿真結(jié)果及分析

4．1多約束問題

本文研究的QoS本質(zhì)是對一個有向圖在四種約束條件下最小費(fèi)用問題。為了清楚地研究問題，本文首先來研究最短路問題。仿真實(shí)驗(yàn)中使用的網(wǎng)絡(luò)拓?fù)淙鐖D1所示。該拓?fù)涫菍NSNET[12]是通過增加附加鏈路修改而得到的，文獻(xiàn)[13~15]中也使用了同樣的拓?fù)浣Y(jié)構(gòu)，目標(biāo)函數(shù)利用式（3）。

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

5結(jié)束語

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

參考文獻(xiàn)：

[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]陳國良，王煦法，莊鎮(zhèn)泉.遺傳算法及其應(yīng)用[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－h(huán)ui， 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.

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