結(jié)合SCE法的粒子群優(yōu)化QoS路由算法

1、結(jié)合SCE法的粒子群優(yōu)化QoS路由算法摘要QS(QualityfServie)路由問題是一個非線性的組合優(yōu)化問題，理論上已證明了該問題是NP完全問題。粒子群優(yōu)化算法是一種基于群智能演化計算技術(shù),PS在求解連續(xù)性優(yōu)化問題上得到了較好的應(yīng)用，而把PS算法用于求解路由算法等離散性問題還比擬少見，同時，PS算法在收斂過程中還存在隨機(jī)性，某些情況下會出現(xiàn)停滯現(xiàn)象。為此本文提出了一種結(jié)合SEshuffledplexevlutin法的粒子群優(yōu)化方法用于求解QS路由問題。該算法通過引入插入算子，刪除算子，算子系列和根本算子序列等概念，對根本的粒子群優(yōu)化算法進(jìn)展改良；通過采用SE法，使算法跳出部分最優(yōu)解的限制。

2、仿真結(jié)果顯示，該算法獲得了滿意的效果，在尋優(yōu)速度上優(yōu)于遺傳算法，也進(jìn)步了算法收斂到最優(yōu)解的才能。關(guān)鍵詞粒子群優(yōu)化算法；效勞質(zhì)量；組播路由；遺傳算法；洗牌復(fù)形進(jìn)化算法1引言當(dāng)前隨著網(wǎng)絡(luò)向著數(shù)字化，高速化，寬帶化的開展，出現(xiàn)了許多新型的多媒體實時應(yīng)用。如電視會議、視頻點播、遠(yuǎn)程醫(yī)療及遠(yuǎn)程教學(xué)等等。這些應(yīng)用涉及到多個用戶并要求一定的效勞質(zhì)量保證，如何在提供業(yè)務(wù)的前提下保證網(wǎng)絡(luò)的效勞質(zhì)量成了這些應(yīng)用能否最終施行的關(guān)鍵。因此，近年來，QS組播路由算法的研究已成為網(wǎng)絡(luò)領(lǐng)域中的一類重要研究課題。多QS參數(shù)約束的路由問題是一個非線性的組合優(yōu)化問題，文獻(xiàn)【1】已證明了,基于多個不相關(guān)可加度量的QS路由問題是NP

3、完全問題。近年來，研究者對此類問題作了大量的研究工作，提出了多種解決方法，如模擬退火，禁忌搜索，神經(jīng)網(wǎng)絡(luò)，遺傳算法等2-6。目前，一類新興的模擬生物群體行為的集群智能算法被引入到此類優(yōu)化問題中，如：蟻群優(yōu)化算法8和粒子群優(yōu)化算法7PS等。PS是一種基于群智能的演化計算技術(shù)。PS最早由Kennedy和Eberhart受人工生命研究結(jié)果的啟發(fā)在1995年提出的10。其根本概念源自鳥群捕食行為的研究。PS算法在連續(xù)性問題上獲得了較為滿意的效果，但在離散問題，NP完全問題方面研究得較少9，特別是用PS求解QS路由問題是一個新的研究方向。另外，PS算法存在著易于陷入“停滯階段的缺點，為此本文提出了一種結(jié)

4、合SEshuffledplexevlutin算法的PS求解QS路由問題的算法，仿真結(jié)果顯示了該算法的有效和可行性。2根本概念2.1根本PS算法根本PS的原理是:每個優(yōu)化問題的解都是粒子在搜索空間中的位置，粒子的速度值決定它們飛翔的方向和間隔 ，粒子群追隨當(dāng)前的最優(yōu)粒子在解空間中搜索。在D維的搜索空間中，有隨機(jī)分布的個粒子組成的一個初始粒子群，每個粒子有各自的位置和速度。如第i個粒子的位置表示為一個D維的向量,速度也是一個D維的向量，記為。每個粒子記住自己在迭代過程中找到的最優(yōu)位置，記為，整個粒子群迄今為止搜索到的最優(yōu)位置為全局最優(yōu)解，記為。在算法的初期，為了防止搜索過早陷入部分最優(yōu)解，把粒子群

5、按空間劃分為幾個區(qū)域，而用部分區(qū)域的極值粒子代替全局最優(yōu)解。這樣的尋優(yōu)為部分PS算法，經(jīng)過一定的迭代后，改用全局最優(yōu)解，即全局PS算法進(jìn)展迭代以加快收斂。整個粒子群通過選定個體的和來更新自身的位置和速度：(1)(2)這里，學(xué)習(xí)因子1，2是非負(fù)常數(shù)，他們決定,的影響程度，r1，r2是介于【0，l】之間的隨機(jī)數(shù)。迭代中止條件根據(jù)詳細(xì)問題一般選為最大迭代次數(shù)或(和)粒子群迄今為止搜索到的最優(yōu)位置滿足預(yù)定最小適應(yīng)閾值。2.2SE算法簡介SEshuffledplexevlutin是一種相對較新的連續(xù)性問題的元啟發(fā)搜索算法11。非常合適于求解具有多個部分最小的全局優(yōu)化問題。它主要基于如下概念：結(jié)合了隨機(jī)性

6、和確定性算法；參數(shù)空間中的多點組成的復(fù)形進(jìn)展系統(tǒng)進(jìn)化；復(fù)形中的競爭進(jìn)化；構(gòu)成復(fù)形的點的重新洗牌。SE算法的處理過程如下：首先，隨機(jī)地從問題空間中選定一系列點或者稱為個體，這里，n是問題空間的維數(shù)。這些個體分別構(gòu)成p個復(fù)形，每個復(fù)形由個點構(gòu)成。P和是用戶定義的參數(shù)，他們決定了群體的大小s，即s=p。每個復(fù)形獨立地采用下山單純形法Nelderandead，1965進(jìn)展迭代進(jìn)化。為了實現(xiàn)信息的共享，這些復(fù)形會定期進(jìn)展洗牌shuffled處理，然后形成新的復(fù)形。如此，進(jìn)化和洗牌重復(fù)進(jìn)展直到滿足預(yù)先指定的收斂準(zhǔn)那么。SE算法的主要特征是通過競爭進(jìn)化和定期洗牌來確保每個復(fù)形獲得的信息能在整個問題空間獲得共

7、享。2.3根本PS的停滯現(xiàn)象與改良研究發(fā)現(xiàn)14，根本PS粒子的位置是在本粒子前一最優(yōu)位置和全局最優(yōu)位置之間以減幅正弦波方式振蕩的，假如在這一過程中，粒子經(jīng)過的位置比前一最優(yōu)位置要好，那么粒子將繼續(xù)挪動，通常收斂到目前找到的全局最優(yōu)位置，所有的粒子跟隨這一一樣行為，很快聚集到一個本地最優(yōu)解。然而，假如全局最優(yōu)解不是剛好存在于初始粒子與這個本地最優(yōu)解之間的位置的話，那么大部分粒子均被一樣的本地最優(yōu)解所限制，算法將出現(xiàn)暫時的停滯現(xiàn)象，需要經(jīng)過很長的一段時間才能打破這個本地最優(yōu)解的限制。那么，大多數(shù)粒子將浪費(fèi)大量的計算時間在尋找和挪動到部分最優(yōu)的方向上。為了克制這種現(xiàn)象，我們采用結(jié)合了SE的PS算法。

8、我們在每個復(fù)形中不是采用下山法，而是采用PS算法。從而利用洗牌的處理，保證每個復(fù)形的多樣性，利于算法跳出停滯階段。為了能使我們提出的結(jié)合SE的PS算法應(yīng)用到求解QS路由的離散性問題上，我們做如下改良：首先我們定義如下幾個概念：插入算子，刪除算子，算子序列和根本算子序列。插入算子對于一條QS單播路由，用其經(jīng)過的節(jié)點序列表示為R=(Ni)i=1,n;因此定義的插入算子INS(i1,k)如下：定義1:假如用插入算子INS(i1，k)作用于路由R，那么其結(jié)果為：在網(wǎng)絡(luò)中搜尋一條從路由的第i1-1個節(jié)點N(i1-1)到節(jié)點k的不包含源節(jié)點的最短費(fèi)用途徑，插入到路由的第i1個節(jié)點Ni1前，然后,再在網(wǎng)絡(luò)中

9、尋找一條從節(jié)點k到節(jié)點Ni1的不包含源節(jié)點的最短費(fèi)用途徑，插入到Ni1前，并刪除節(jié)點Ni1。假如網(wǎng)絡(luò)中節(jié)點N(i1-1)到節(jié)點k不存在連通的途徑，那么擴(kuò)大為節(jié)點N(i1-2)到節(jié)點k，以此類推，直到找到或到達(dá)路由源節(jié)點為止。同理，假如網(wǎng)絡(luò)中節(jié)點k到節(jié)點Ni1,不存在連通的途徑，那么擴(kuò)大為節(jié)點k到節(jié)點N(i1+1)，以此類推，直到找到或到達(dá)路由終節(jié)點為止。圖1.隨機(jī)生成的15節(jié)點網(wǎng)絡(luò)拓?fù)錁?gòu)造例1：如圖1中：單播路由R=(3，7，11，8),那么R=R+INS(3，4)的結(jié)果是，尋找一條從R的第3個節(jié)點11到節(jié)點4的最短費(fèi)用途徑(11,9,4)，然后再尋找節(jié)點4到節(jié)點8的的最短途徑4，8，插入并刪

10、除節(jié)點8，最后得到的途徑為3，7，11，9，4，8。刪除算子定義2:假如用刪除算子DEL(i1)作用于路由R，那么其結(jié)果為：在網(wǎng)絡(luò)中搜尋一條從節(jié)點N(i1-1)到節(jié)點N(i1+1)的不包含節(jié)點Ni1的最短費(fèi)用途徑，然后用它替代路由中N(i1-1)，Ni1和N(i1+1)三個節(jié)點。假如節(jié)點N(i1-1)到節(jié)點N(i1+1)不存在連通的途徑,擴(kuò)大為N(i1-2,i1+1)，假如仍找不到再擴(kuò)大為N(i1-1,i1+2)，以此類推直到找到一條可替代的途徑為止。例2：如圖1中：單播路由R=(3，7，11，9，8),那么R=R+DEL(4)的結(jié)果是，尋找一條節(jié)點11到8的最短費(fèi)用途徑(11,8)，替代11

11、，9，8，最后得到的途徑為3，7，11，8。算子序列定義3：假如有多個算子作用于一條路由，那么由這些算子組成的序列稱為算子序列。如算子序列S=INS1,INS2,DEL1。這里，對各算子的先后順序是敏感的。根本算子序列定義4：不同的算子序列作用于同一條路由，有可能得到一樣的結(jié)果，把有最少操作的算子序列稱為根本算子序列。根據(jù)上面的定義我們設(shè)定根本算子序列的構(gòu)造的準(zhǔn)那么：假設(shè)有兩條路由R1,R2。這里的目的是如何構(gòu)造根本算子序列，使之作用于R2從而得到R1。定義SS=R1-R2,從而，R2=R1+S。構(gòu)造的根本規(guī)那么是：首先對齊節(jié)點數(shù)，假如節(jié)點數(shù)少，那么選擇插入算子，假如節(jié)點數(shù)多，那么選擇刪除算子

12、，假如相等且有不同的節(jié)點，那么隨機(jī)選擇插入或刪除算子。如圖1中：路由B=3,1,4,8,路由A=3,7,11,9,8，求S=A-B。首先是對齊節(jié)點數(shù)，路由A中的第2個節(jié)點7在路由B中不存在，因此可考慮插入算子INS(2,7)，有B1=B+INS(2,7),此時路由在3和7之間尋找到最短費(fèi)用途徑3,7，7和4之間不經(jīng)過源節(jié)點的最短費(fèi)用途徑為(7,11,8,4)，交換后得到B1=(3,7,11,8,4,8)。刪除一樣節(jié)點間的途徑得B1=(3,7,11,8)。此時，B1的節(jié)點數(shù)仍小于A，路由A中的第4個節(jié)點9在路由A中仍不存在因此考慮INS(4,9)，根據(jù)插入算子的定義，最后得到B2=B1+IN(4

13、,9)=(3,7,11,9,8)=A。因此得到根本算子：S=A-B=INS(2,7),INS(4,9)。更新位置和速度由于不再采用實數(shù)編碼方式，因此公式(1)不再滿足要求。根據(jù)上面的討論，作如下修改：(3)這里r1，r2,是介于【，l】之間的隨機(jī)數(shù)，符號定義為：合并兩個算子序列并把他們轉(zhuǎn)換為根本算子序列的操作。的含義是根本算子序列以r1的概率保存下來。具有類似的含義。r1,r2的大小決定了和的影響程度。通過上述設(shè)計，我們就得到了合適于路由算法的離散形式的結(jié)合SE的PS算法。3QS路由的數(shù)學(xué)模型不失一般性,把通信網(wǎng)看成一個有向連通圖G(V,E)，其中為節(jié)點集合，為圖中連接兩個節(jié)點的鏈路的集合，每

14、條鏈路e(u,v)E和一些QS度量相關(guān)，這些度量包括：費(fèi)用、延時、可用帶寬和抖動等。這里用函數(shù)e代表費(fèi)用，它反映了支持QS而需要的資源總數(shù)，它可以是金錢上的也可以是關(guān)于資源的其他任何度量。其他的QS度量用Qi(e)來表示。組播路由問題就是要找到一棵組播斯坦立樹：T(s,D)這里sV是組播應(yīng)用的數(shù)據(jù)源節(jié)點，是一組目的節(jié)點D=,sD是組播組。給定一個組播斯坦立樹，令P(s,di)代表源節(jié)點s和一個目的節(jié)點di之間經(jīng)過的途徑，那么組播樹T(s,D)中的所有途徑可以表示為。從源節(jié)點s到某一目的節(jié)點di的費(fèi)用可表示為：,那么組播樹T(s,D)的總的費(fèi)用即為所有鏈路的費(fèi)用總和，表示為：.令Q1,Qn為所有

15、加性的QS度量，那么整棵組播樹T(s,D)的某個QS度量為該樹中所有鏈路的該QS度量的總和。表示為：,令Q1,Qn為所有凹性的QS度量如帶寬等。那么整棵組播樹T(s,D)的瓶頸QS度量那么為所有鏈路中該度量的最小值：,令1,n,為需滿足的加性QS度量約束，為需滿足的凹性QS度量的約束，那么組播多約束QS路由問題那么可定義為：尋找一棵滿足以下條件的組播樹：(4)4PS組播路由算法4.1編碼及初始化對于使用PS求解組合優(yōu)化問題，一般采用實數(shù)編碼。但對于組播路由問題，采用實數(shù)編碼使得算法編碼、解碼過程復(fù)雜。為克制編碼操作帶來的負(fù)面影響，所設(shè)計的算法采用了節(jié)點序列的編碼機(jī)制，每個個體即每棵組播樹被編碼

16、為源節(jié)點到各目的節(jié)點的節(jié)點系列。如：有n個目的節(jié)點，就有n條節(jié)點系列，那么PS的搜索空間也設(shè)計成n維的空間，搜索空間的每一維坐標(biāo)由所有網(wǎng)絡(luò)節(jié)點的排列組合成的序列構(gòu)成。粒子群的規(guī)模根據(jù)詳細(xì)的網(wǎng)絡(luò)規(guī)模和組播成員規(guī)模決定，本文在進(jìn)展初始化原始粒子時，采用了隨機(jī)深度搜索的方式構(gòu)造：每棵組播樹，由組播源節(jié)點到各個目的節(jié)點的節(jié)點序列構(gòu)成。從而得到一系列個體，k為群體大校我們按7式計算每個個體Ti(s,D)的適應(yīng)度fi，并按適應(yīng)度大小進(jìn)展排序得到隊列：(5)然后按如下規(guī)那么分成個復(fù)形：,每一個復(fù)形包含個個體：(6)4.2.適應(yīng)度函數(shù)在所設(shè)計的算法中,使用了懲罰函數(shù)來處理QS約束，這樣約束優(yōu)化問題就變成了非約

17、束的優(yōu)化問題。算法用到的適應(yīng)度函數(shù)設(shè)計如下：(7)這里，是正的實數(shù)，反映了各QS參量的重要性。為懲罰函數(shù)，r是懲罰的程度。4.3洗牌處理如2.3分析，為了防止停滯現(xiàn)象，本文設(shè)計的算法引入了SE的洗牌處理。其處理如下：首先指定每個復(fù)形經(jīng)過y次迭代后重新進(jìn)展洗牌，按式6進(jìn)展處理，重新形成P個復(fù)形。4.4算法描繪出的結(jié)合SE的PS路由算法的步驟如下：1：編碼和初始化，采用隨機(jī)深度優(yōu)先的搜索方法隨機(jī)產(chǎn)生個體。2：根據(jù)公式(7)計算每個個體的適應(yīng)度，并排序，按式6把他們分為p個復(fù)形。3：每個復(fù)形中有各自的個體最優(yōu)和全局最優(yōu)，根據(jù)公式3和2計算復(fù)形中所有粒子的下一位置，并根據(jù)公式(7)計算其適應(yīng)度，根據(jù)適

18、應(yīng)度值判斷，假如某一粒子新的位置優(yōu)于,那么更新值。4：假如存在最優(yōu)的新位置優(yōu)于,那么用該新位置更新值。5：假如滿足完畢判據(jù)，返回最優(yōu)解，否那么判斷是否到達(dá)指定的迭代次數(shù)y，假如未到達(dá)轉(zhuǎn)3繼續(xù)執(zhí)行，否那么,轉(zhuǎn)2進(jìn)展重新洗牌處理。5仿真結(jié)果本文在P機(jī)上p4,2.4G,256對上述算法進(jìn)展了仿真試驗，仿真使用的網(wǎng)絡(luò)采用了Salaa13網(wǎng)絡(luò)拓?fù)渖伤惴▉砩?。首先，在一樣運(yùn)行條件下，比擬了提出的結(jié)合SE的PS，標(biāo)準(zhǔn)PS12和遺傳算法的運(yùn)行時間。表1各算法運(yùn)行時間的比擬網(wǎng)絡(luò)規(guī)模PS算法結(jié)合se的PS算法GA算法200.110.110.12400.200.190.23600.460.420.51801.3

19、51.141.511001.751.373.35如表1所示。表中組播規(guī)模為網(wǎng)絡(luò)規(guī)模的30%。表中可以看出，SE的PS和標(biāo)準(zhǔn)的PS的運(yùn)行時間均少于GA算法所需的運(yùn)行時間，這是由于PS只在解空間中搜索很小的一部分，因此在全局搜索才能上強(qiáng)于GA，收斂速度也較快。而結(jié)合SE算法的PS算法由于把采用了分散迭代的方法，從而減少了外循環(huán)的次數(shù)，進(jìn)步了算法的效率，因此比PS算法需要更少的運(yùn)算時間。圖2PS和結(jié)合SE的PS延時，費(fèi)用隨迭代次數(shù)變化曲線其次，對圖1所示的網(wǎng)絡(luò)拓?fù)錁?gòu)造進(jìn)展了仿真試驗。圖中的三元組st,bandidth,delay分別表示鏈路上的費(fèi)用，提供的帶寬以及延時。這里考慮了帶寬限制的時延約束費(fèi)

20、用最小的組播路由問題：源節(jié)點3,目的節(jié)點為：5，8，12，13；QS限制為：延時D=38s,這里假設(shè)到每個目的節(jié)點的時延限制都一樣；帶寬限制B=70。圖2顯示了隨迭代次數(shù)變化的延時，費(fèi)用變化的情況。從圖中可以看出，標(biāo)準(zhǔn)PS和結(jié)合SE的PS算法在較少的迭代次數(shù)的情況下都收斂到最優(yōu)解，可見算法是可行的，而結(jié)合SE的PS算法稍優(yōu)于標(biāo)準(zhǔn)PS算法。當(dāng)網(wǎng)絡(luò)規(guī)模較小時，PS與結(jié)合SE的PS差異不大，這是由于搜索空間本身不大，搜索過程中出現(xiàn)部分最小的約束的幾率也不大，但在較大規(guī)模的網(wǎng)絡(luò)中就會有較大時機(jī)出現(xiàn)部分最小，從而導(dǎo)致停滯現(xiàn)象的出現(xiàn)。因此，本文比擬了標(biāo)準(zhǔn)PS和結(jié)合SE的PS在較大規(guī)模網(wǎng)絡(luò)中的收斂測試。其結(jié)

21、果如表2所示：表2標(biāo)準(zhǔn)PS與結(jié)合SE的PS算法收斂情況比擬網(wǎng)絡(luò)規(guī)模根本PS的平均收斂代數(shù)結(jié)合SE的PS的平均收斂代數(shù)根本PS部分收斂的概率結(jié)合SE的PS部分收斂的概率6055450.210.0570120940.220.03801151200.430.02901441190.420.011002211930.510.02表2可以看出，根本PS算法沒有很好的機(jī)制跳出部分最優(yōu)解的約束，陷于部分收斂的概率較大，而結(jié)合SE的PS算法由于增加了利用了各個復(fù)形的信息，通過重新洗牌操作，充分利用理解空間的整體信息，增加了粒子解的多樣性，從而很好地防止了停滯的出現(xiàn)時，因此陷于部分收斂的概率校6結(jié)論本文提出了一

22、種結(jié)合SE的粒子群優(yōu)化的方法用于求解具有NP完全難度的QS路由問題。與遺傳算法的QS路由算法相比，本文的方法更易于實現(xiàn)，需要的內(nèi)存空間和運(yùn)算時間更少。仿真結(jié)果顯示，提出的算法在求解QS組播路由問題上的應(yīng)用是可行的，在尋優(yōu)速度上優(yōu)于采用遺傳算法；SE的引入，增加理解的多樣化，克制了標(biāo)準(zhǔn)PS算法易于陷入停滯階段的缺點，收到較好的效果。參考文獻(xiàn)1ang,Z.,rrft,J.:QualityfserviefrsupprtingultiediaappliatinsJ.IEEEJSA,1996,(14)：1228-1234.2u,J.J.,Hang,R.H.,Liu,H.I.:ultiastrutingi

23、thultipleQSnstraintsinATnetrksJ.InfratinSienes,2000,(124)：2957.3Haghighatab,A.T.,Faezb,K.,Dehghan,.:A.laEib,Y.Ghahreani.GA-BasedheuristialgrithsfrQSbasedultiastrutingJ.Knledge-BasedSystes,2022,(16)：305312.4ang,Z.,Shi,B.:Bandidth-delay-nstrainedleast-stultiastrutingbasednheuristigenetialgrithJ.puteru

24、niatins,2001,(24)：6856925J.Hakkinen,.Lagerhl,.Petersn,andB.Sdrnberg,LalrutingalgrithsbasednPttsNeuralnetrksJ.IEEETransatinsnNeuralNetrks,July2000,11(4)：970-9776王征應(yīng),石冰心,趙爾敦組播路由的啟發(fā)式遺傳算法J電子學(xué)報,Feb.2001,29(2)：253-2567Russel.Eberhart,YushiShi,Partilesarptiizatin:develpents,appliatinsandresures.PreedingsftheIEEEngressnEvlutinaryputtin(E2001),seul,krea,2001：81-848Kan