方位鄰域信息互享差分虛擬網(wǎng)絡(luò)映射算法

梁樹杰，余軼生，黃旭彬

（1.廣東石油化工學(xué)院 高州師范學(xué)院 教育信息技術(shù)中心，廣東 高州525200；2.中山大學(xué) 電子與通信工程系，廣東 廣州510275）

0 引 言

差分進化算法 （DE）相關(guān)研究成果眾多，主要集中在對算法性能的進一步提升及工程應(yīng)用上。對算法性能提升方法主要有以下幾類：一是對算法本身參數(shù)或操作算子的動態(tài)自適應(yīng)改變，例如文獻 ［1］提出了使用合奏變異策略和控制參數(shù)的差分進化算法；二是與其它算法混合實現(xiàn)優(yōu)勢互補，例如文獻 ［2］基于粒子群和差分進化各自特點，設(shè)計了差分進化粒子群混合優(yōu)化算法；三是多種群或鄰域的改進方法，例如文獻 ［3］提出了各種小生境差分進化集成的鄰域變異策略，用來解決多峰優(yōu)化問題。

基于鄰域算法的改進目前已有很多成熟的方法，文獻［4］提出一種基于環(huán)上拓撲組織的個體鄰域概念，并應(yīng)用到差分進化算法改進中；文獻 ［5］采用鄰域引導(dǎo)的選擇方案，采用突變的父代誘變策略，充分利用鄰域和種群信息；文獻 ［6］設(shè)計一種類似于馮·諾依曼結(jié)構(gòu)的鄰域結(jié)構(gòu)對人工魚群算法進行改進。這些鄰域的改進方式都是種群個體與群體中固定的個體進行信息交流，相當(dāng)于把種群個體按結(jié)構(gòu)局部化，有利于種群個體尋找到不同的局部極值，通過全局的對比從而找出全局最優(yōu)值。存在的問題主要是過于固定化的鄰域結(jié)構(gòu)限制了個體與其它局部個體的信息交流，導(dǎo)致種群個體無法享受全局進化的宏利，對于局部探索的重視過于極端化。對此，本文根據(jù)日常的方向定位思想設(shè)計了一種固定和隨機動態(tài)鄰域結(jié)構(gòu)對算法進行改進，稱為基于方位鄰域信息互享差分進化算法 （direction neighborhood information sharing differential evolution algorithm，DNDE）。最后，結(jié)合方位鄰域的隨機動態(tài)信息互享差分進化算法對虛擬網(wǎng)絡(luò)映射問題進行研究。

1 基于方位鄰域的隨機動態(tài)信息互享差分進化算法

1.1 方位鄰域結(jié)構(gòu)思想

方位的概念其實就是我們?nèi)粘Ｋf的各個方向位置，如東、西、南、北、東南、西南等。古時航海家為了準(zhǔn)確把握航行方向，在羅盤上細分為十六分位甚至三十二分位，中國曾經(jīng)也用八卦、地支、天干等表示方位，這些都是傳統(tǒng)的方位分法比較籠統(tǒng)。在現(xiàn)代航空、航海等領(lǐng)域?qū)τ诜轿坏亩x更加嚴格，甚至使用GPS精確定位，方向的說法也相應(yīng)的變?yōu)檎龞|、正西、正南、正北、東偏南∠xo（x ∈0～90）等，在這種定義中，正東、正西、正南、正北是固定的方向，而東南、西南、東北、西北則被細化為帶角度的動態(tài)方向不再固定，基于這種思想利用前者設(shè)計固定的鄰域結(jié)構(gòu)，而利用后者設(shè)計動態(tài)的鄰域結(jié)構(gòu)（如圖1所示）。

圖1 方位鄰域結(jié)構(gòu)

在傳統(tǒng)的差分進化算法中，種群個體是并行排列進化的，如P ＝｛xi｜i＝1～r｝。為了使用方位鄰域結(jié)構(gòu)，把這種傳統(tǒng)的并行排列方式修改為網(wǎng)格形式，P ＝｛xi，j｜i＝1～m，j＝1～n｝，滿足條件r＝m×n （如圖1所示）。其中，a1～a8是算法的鄰域視野，α1～α4是動態(tài)鄰域的方向偏角，當(dāng)然鄰域視野的選取直接決定著動態(tài)鄰域方向偏角的大小。為簡化算法對該鄰域結(jié)構(gòu)進行如下修改：一是用鄰域視野代替鄰域方向偏角，簡化參數(shù)選取。二是選取縱向的鄰域視野為固定值，即固定鄰域的鄰域視野是固定的，取a3＝a4＝a7＝a8＝const，令橫向的鄰域視野為相等的隨機整數(shù)值，即a1＝a2＝a3＝a4＝｜rand（l，u）｜，這樣動態(tài)鄰域方向偏角α1～α4將直接決定于橫向的鄰域視野取值，即

通過上述定義可得差分進化個體xij的固定方位鄰域為

其中，i＝1，2，…，m，j＝1，2，…，n。xi′j，xij′，xi″j，xij″為種群個體xij的固定鄰域，分別與xij直接相連。令c＝const則可得xij固定鄰域個體位置參數(shù)為

差分進化個體xlk的隨機動態(tài)鄰域為

其中，l＝1，2，…，m，k＝1，2，…，n。xl′k，xlk′，xl″k，xlk″為種群個體xlk的隨機動態(tài)鄰域與xlk相連。令r ＝可得xlk隨機動態(tài)鄰域個體的位置參數(shù)為

確定了固定鄰域和隨機動態(tài)鄰域后，針對種群個體可以按照定比例的方式確定該個體是參與固定鄰域交流還是參與隨機動態(tài)鄰域交流，設(shè)隨即動態(tài)鄰域交流閾值為yr，則當(dāng)rand（·）≥yr時該個體進行隨機動態(tài)交流以獲得全局進化信息，否則該個體仍然進行固定鄰域交流，側(cè)重于局部探索。

1.2 差分變異方式

DE算法主要包括變異操作、交叉操作和選擇操作。好的變異方式可以防止進化陷于局部極值，有利于保持種群的多樣性和兼顧收斂速度。眾多學(xué)者對差分進化算法的變異方式進行了研究，提出多種改進方式，例如DE/rand/1和DE/best/2［7，8］

式 （8）的變異方式能夠以相對最優(yōu)個體為主體，兼顧相對次優(yōu)個體，是一種很好的改進方法和改進思路。

固定鄰域：在xij的固定方位鄰域中產(chǎn)生兩個隨機個體xr1、xr2∈xijC－neighbors，并計算其個體適應(yīng)值進行對比得到xrbest、xrworst，則可得xij經(jīng)固定鄰域變異后的個體為

動態(tài)鄰域：在xij的動態(tài)鄰域中隨機產(chǎn)生3個個體xr1、xr2、xr3∈xijR－neighbors，并計算其個體適應(yīng)值進行對比得到xrbest、xrmiddle、xrworst，則可得xij經(jīng)固定鄰域變異后的個體為

1.3 DNDE算法流程

方位鄰域結(jié)構(gòu)設(shè)計的主體思想是以固定鄰域為主強化不同局部間的深度開發(fā)，動態(tài)隨機鄰域為輔兼顧全局進化有利信息，以引導(dǎo)局部創(chuàng)新進化，所以上述分析中設(shè)立了一個隨機動態(tài)鄰域進化閾值yr，來判別是否進行動態(tài)鄰域交流。DNDE具體算法步驟如圖2所示。

2 仿真分析

2.1 仿真設(shè)計

選取相關(guān)文獻使用的5個通用標(biāo)準(zhǔn)函數(shù)對算法進行測試，計算機平臺仿真軟件：matlab2012a，操作系統(tǒng)：win7，CPU：AMD Athlon（tm）X4 641，RAM：6G

圖2 DNDE算法流程

DNDE算法參數(shù)設(shè)置：種群大小NP＝96，交叉概率因子CR＝0.85，縮放因子F＝0.75［8，9］。DNDE 算法增加了兩個參數(shù)分別是：動態(tài)鄰域進化閾值yr和動態(tài)鄰域視野rdl，設(shè)置yr＝0.25，rdl為區(qū)間 ［1，23］范圍內(nèi)的隨機整數(shù)。原始并列種群重組為8行12列的網(wǎng)格種群。f1～f5各基準(zhǔn)測試函數(shù)的搜索區(qū)間 （S）、全局最優(yōu)值 （P）和目標(biāo)精度 （vtr）見表1。選取對比算法為標(biāo)準(zhǔn)DE（DE/rand/1）、AFSAVNN 及DNDE算法，最終的測試結(jié)果為各算法獨立運行30次的平均值。

表1 基準(zhǔn)測試函數(shù)相關(guān)參數(shù)

2.2 仿真結(jié)果分析

3種算法在表1參數(shù)設(shè)置下以目標(biāo)精度vtr為算法終止條件，為防止算法早熟收斂無法滿足目標(biāo)精度終止條件導(dǎo)致算法無法停止，設(shè)置種群的最大終止迭代次數(shù)T ＝2000［10］。3種算法在目標(biāo)測試函數(shù)上分別運行30次，以得到的平均迭代次數(shù)、平均收斂值和運行時間為算法性能評價的主要衡量指標(biāo)［11，12］。如表2及圖3～圖7所示。

表2 3種算法優(yōu)化結(jié)果

圖3 f1最優(yōu)值對比結(jié)果

圖4 f2最優(yōu)值對比結(jié)果

圖5 f3最優(yōu)值對比結(jié)果

圖6 f4最優(yōu)值對比結(jié)果

圖7 f5最優(yōu)值對比結(jié)果

表2給出3種算法在5個基準(zhǔn)測試函數(shù)上運行30次所得到的平均收斂值、迭代次數(shù)及迭代時間的數(shù)據(jù)，收斂值體現(xiàn)的是算法的收斂精度，迭代次數(shù)及迭代時間代表算法的收斂速率及算法的時間復(fù)雜性。標(biāo)準(zhǔn)DE （DE/rand/1）算法在測試函數(shù)f1、f2、f4、f5 上均出現(xiàn)早熟收斂現(xiàn)象或收斂速度過慢，導(dǎo)致在設(shè)定的終止迭代次數(shù)時，算法的收斂精度仍然很差。對比算法AFSAVNN 的情況稍好，只在測試函數(shù)f1、f5上出現(xiàn)早熟收斂現(xiàn)象，在其它測試函數(shù)上的表現(xiàn)不錯，但也存在迭代次數(shù)過多，收斂時間略長的問題。DNDE算法在函數(shù)f5上出現(xiàn)早熟收斂現(xiàn)象，但是總體情況是DNDE算法在測試函數(shù)上的表現(xiàn)無論是收斂精度還是收斂速度上均要好于對比算法。圖3～圖7以收斂曲線的形式展現(xiàn)3種算法的運算過程，從中可以更加直觀的判斷出算法的性能優(yōu)劣。

DNDE算法中的鄰域結(jié)構(gòu)設(shè)計使算法增加了兩個參數(shù)：分別是動態(tài)鄰域進化閾值yr和動態(tài)鄰域視野rdl，其中動態(tài)鄰域視野rdl是在一定范圍內(nèi)產(chǎn)生的隨機數(shù)，文中已給出該數(shù)據(jù)的變換公式。另一個參數(shù)動態(tài)鄰域進化閾值yr理論上講對算法的性能有很重要的影響，下面主要是分析該值的選取對算法性能的影響程度，并試圖給出該算法選取的實驗室證據(jù)。

2.3 閾值實驗及結(jié)果分析

閾值yr的主要作用是判別種群進化個體選取固定鄰域結(jié)構(gòu)還是隨機動態(tài)鄰域結(jié)構(gòu)，從前述分析中可知，固定鄰域結(jié)構(gòu)側(cè)重的是局部深度探索，隨機動態(tài)鄰域側(cè)重的是全局信息的共享，因此閾值yr越大代表種群個體選取隨機動態(tài)鄰域結(jié)構(gòu)的可能性越大，閾值yr越小越側(cè)重于局部的搜索。為驗證動態(tài)閾值yr的不同取值對DNDE算法性能的影響，分別取yr＝ ［0.05：0.1：0.95］，起始值為0.05間隔0.1到0.95共10個閾值每個獨立運行30次的平均算法收斂成功率，平均收斂精度及平均迭代次數(shù)，收斂目標(biāo)值和防早熟最大迭代次數(shù)分別是vtr＝10－4及T＝2000。以f1為對象進行仿真，實驗結(jié)果見表3。

表3 閾值對算法影響

表3數(shù)據(jù)可以看出，當(dāng)yr值取值過小時，雖然算法的收斂成功率很高但是平均迭代次數(shù)過慢，例如yr＝0.05時平均成功率為92.3%，平均收斂代數(shù)卻要1356，雖然與yr＝0.25時的平均成功率相差不大，但是平均迭代次數(shù)卻相差很大，這意味著前者算法的收斂速度很慢。主要原因是算法過于注重局部搜索，在保持種群多樣性方面做的很好，所以成功搜索到全局最優(yōu)值的概率很高，但是對于全局進化信息提取過少，各自為政收斂速度很慢。隨著yr的不斷增大，算法由注重局部搜索到注重全局搜索逐漸過渡，導(dǎo)致算法被局部最優(yōu)峰值吸引的概率逐漸增加，所以算法早熟收斂的可能性逐漸增大，導(dǎo)致算法的平均搜索成功率降低，隨之算法的平均迭代步數(shù)相應(yīng)增加。從實驗對比結(jié)果看，yr＝0.25是相對較好的一個取值。

3 方位鄰域隨機動態(tài)信息互享差分虛擬網(wǎng)絡(luò)映射算法

3.1 問題描述及目標(biāo)函數(shù)

定義1 底層網(wǎng)絡(luò)：Gp＝（Np，Lp，，）表示一個加權(quán)的不帶方向性的底層拓撲網(wǎng)絡(luò)，Np為該虛擬映射底層網(wǎng)絡(luò)的所有節(jié)點的集合，Lp為網(wǎng)絡(luò)中所有節(jié)點連接路線的集合，為虛擬網(wǎng)絡(luò)節(jié)點屬性的集合。定義∈Np包括和分別是網(wǎng)絡(luò)節(jié)點的控制和計算資源，∈Lp是帶寬資源Bp）。

定義2 虛擬網(wǎng)絡(luò)請求：Gv＝（Nv，Lv，，）表示一個加權(quán)的不帶方向性的虛擬拓撲網(wǎng)絡(luò)，Nv為該虛擬映射虛擬網(wǎng)絡(luò)的所有節(jié)點的集合，Lv為網(wǎng)絡(luò)中所有虛擬節(jié)點連接路線的集合，為虛擬網(wǎng)絡(luò)節(jié)點約束條件的集合。定義∈Nv包括和分別是網(wǎng)絡(luò)節(jié)點的控制和計算約束，∈Lv是帶寬資源約束Bv），VNRk（Gv，tb，tr）即為虛擬網(wǎng)絡(luò)請求k。

定義3 虛擬網(wǎng)絡(luò)映射：Gv（Nv，Lv）→Gp（N′p，L′p）表示一個虛擬網(wǎng)絡(luò)映射問題，其中，N′pNp，LpL′p。

在虛擬網(wǎng)絡(luò)映射中，一般控制和轉(zhuǎn)發(fā)網(wǎng)絡(luò)是分離的，為了確保高級用戶群體的服務(wù)質(zhì)量，在現(xiàn)有資源約束下，以底層網(wǎng)絡(luò)剩余資源最大作為優(yōu)化目標(biāo)，則虛擬網(wǎng)絡(luò)的優(yōu)化模型為［10］

約束條件為

該模型中Oij為虛擬和物理節(jié)點間的映射關(guān)系，Path ＝M）為線路能夠映射到Gp上的線路集合，α、β、χ為3種資源對資源總值的貢獻系數(shù)，、為低階用戶資源需求量，、為高階用戶資源需求量。Sgrabbed表示已被占用并且無法再次映射的資源。則方位鄰域隨機動態(tài)信息互享差分虛擬網(wǎng)絡(luò)映射算法步驟如下：

步驟1 初始化種群及參數(shù)，種群規(guī)模為Np，動態(tài)鄰域進化閾值yr＝0.25，交叉概率因子CR＝0.85，縮放因子F＝0.75。

步驟2 根據(jù)式 （12）計算所有種群個體的適應(yīng)值f（xi），得到差分種群的個體最優(yōu)位置xpbest與全局最優(yōu)位置xgbest。

步驟3 如果當(dāng)前差分種群的全局最優(yōu)值滿足終止條件則終止算法并輸出最優(yōu)虛擬網(wǎng)絡(luò)映射方案。

步驟4 根據(jù)方位鄰域算法進行種群變異，交叉操作，并結(jié)合限制條件 （13）進行選擇操作。

步驟5 轉(zhuǎn)步驟2。

3.2 實驗評估分析

根據(jù)GT－ITM 規(guī)則設(shè)置虛擬網(wǎng)絡(luò)的底層結(jié)構(gòu)有100個節(jié)點及其之間相互連接的500條線路，帶寬資源為50－100均勻分布的值。以100為一個時間單元，每個時間單元內(nèi)虛擬網(wǎng)絡(luò)請求到達為λ＝5的泊松過程，網(wǎng)絡(luò)的壽命呈指數(shù)分布，平均壽命為500個時間單元。針對網(wǎng)絡(luò)中發(fā)生的每一次請求，網(wǎng)絡(luò)節(jié)點都滿足2－20均勻分布，節(jié)點之間的連接概率為0.5。網(wǎng)絡(luò)內(nèi)每個點的CPU 與帶寬資源均滿足0－50均勻分布。虛擬網(wǎng)絡(luò)的結(jié)構(gòu)及其位置屬性使用GT－ITM工具生成，坐標(biāo)x、y 滿足0－100均勻分布，在虛擬網(wǎng)絡(luò)映射過程中，對于每個請求的位置信息約束量D 設(shè)為恒值。這樣在每次虛擬網(wǎng)絡(luò)映射過程中會產(chǎn)生大約50000個時間單元和2500個網(wǎng)絡(luò)請求［12］。虛擬網(wǎng)絡(luò)評價指標(biāo)：

節(jié)點資源利用率

鏈路資源利用率

收益成本比

對比算法選用基于貪婪 （GREEDY）算法的虛擬網(wǎng)絡(luò)映射方案，式 （14）～式 （16）3個評價指標(biāo)的仿真結(jié)果如圖8～圖10所示。

圖8 節(jié)點資源利用率

圖9 鏈路資源利用率

圖10 營運收益成本比

從圖8～圖10可以看出方位鄰域隨機動態(tài)信息互享差分虛擬網(wǎng)絡(luò)映射算法方案的節(jié)點利用率和鏈路利用率要高于基于GREEDY 算法的虛擬網(wǎng)絡(luò)映射方案，并且隨著時間的增加，這種占用率總體非常平穩(wěn)，在運行一段時間后達到平衡。這種平衡會伴隨著虛擬網(wǎng)絡(luò)映射到較大或較小的虛擬網(wǎng)絡(luò)而產(chǎn)生上揚或下探趨勢。較高的虛擬網(wǎng)絡(luò)資源占用率，說明對于物理鏈路資源的消耗降低，會保持較高的物理網(wǎng)絡(luò)資源剩余。最后網(wǎng)絡(luò)運營收益成本比直接說明了方位鄰域隨機動態(tài)信息互享差分虛擬網(wǎng)絡(luò)映射算法方案具有更高效的資源利用效率，映射同等規(guī)模的虛擬網(wǎng)絡(luò)所占用的物理資源較低。

4 結(jié)束語

鄰域結(jié)構(gòu)應(yīng)用到進化算法中，對于算法種群多樣性保持，種群局部搜索能力以及算法性能提升具有重要作用。針對傳統(tǒng)固定鄰域結(jié)構(gòu)的優(yōu)點和不足，基于方位概念設(shè)計了一種結(jié)合固定鄰域和動態(tài)鄰域的差分進化算法，新算法兼顧固定鄰域和動態(tài)鄰域的優(yōu)勢，能夠保持種群多樣性的同時，吸收全局進化的有利信息，有效提升算法的尋優(yōu)成功率、搜索精度，加快算法的收斂速度，大幅提升算法的性能，計算機仿真驗證了上述觀點。下一步工作主要是對鄰域結(jié)構(gòu)的進化算法進一步研究，特別是改進算法雖然性能得到大幅提升，但在某些測試函數(shù)上仍難以避免出現(xiàn)早熟收斂，爭取尋找到一種更加合理高效的鄰域結(jié)構(gòu)使算法的性能達到相對最優(yōu)。目前對于差分進化算法的工程應(yīng)用已有很多研究成果，本文采用方位鄰域隨機動態(tài)信息互享差分進化算法對虛擬網(wǎng)絡(luò)映射方案優(yōu)化進行了研究，同GREEDY 算法的虛擬網(wǎng)絡(luò)映射方案的仿真對比結(jié)果反映了本文所提算法的有效性。

［1］Mallipeddi R，Suganthan P N，Pan Q K.Differential evolution algorithm with ensemble of parameters and mutation strategies［J］.Applied Soft Computing，2011，11 （2）：1679－1696.

［2］Zhang C S，Ning J X，Lu S.A novel hybrid differential evolution and particle swarm optimization algorithm for unconstrained optimization ［J］.Operations Research Letters，2009，37（2）：117－122.

［3］Qu B Y，Suganthan P N，Liang J J.Differential evolution with neighborhood mutation for multimodal optimization ［J］.IEEE Transactions on Evolutionary Computation，2012，16（5）：601－614.

［4］TUO Shouheng，ZHOU Tao.Self－adaptive differential evolution algorithm based on dimensionality group cross ［J］.Computer Engineering and Design，2011，32 （9）：3174－3177 （in Chinese）.［拓守恒，周濤.基于維度分組交叉的自適應(yīng)差分進化算法 ［J］. 計算機工程與設(shè)計，2011，32 （9）：3174－3177.］

［5］Piotrowski A P.Adaptive memetic differential evolution with global and local neighborhood－based mutation operators ［J］.Information Sciences，2013，241 （20）：164－194.

［6］Cai Y Q，Wang J H.Differential evolution with neighborhood and direction information for numerical optimization ［J］.IEEE Transactions on Cybernetics，2013，43 （6）：2202－2215.

［7］WANG Lianguo，HONG Yi.Artificial fish－swarm algorithm based on Von Neuman neighborhood ［J］.Control Theory ＆Applications，2010，27 （6）：775－780 （in Chinese）. ［王聯(lián)國，洪毅.基于馮·諾依曼鄰域結(jié)構(gòu)的人工魚群算法 ［J］.控制理論與應(yīng)用，2010，27 （6）：775－780.］

［8］Zhu W，Tang Y，F(xiàn)ang J A.Adaptive population tuning scheme for differential evolution ［J］.Information Sciences，2013，223 （20）：164－191.

［9］Falco I D.Differential evolution for automatic rule extraction from medical databases ［J］.Applied Soft Computing，2013，13 （2）：1265－1283.

［10］CHENG Xiang，ZHANG Zhongbao，SU Sen.Virtual network embedding based on particle swarm optimization ［J］.ACTA Electronica Sinica，2011，39 （10）：2240－2244 （in Chinese）.［程祥，張忠寶，蘇森.基于粒子群優(yōu)化的虛擬網(wǎng)絡(luò)映射算法 ［J］.電子學(xué)報，2011，39 （10）：2240－2244.］

［11］Zhou Y Z，Li X Y，Gao L.A differential evolution algorithm with intersect mutation operator ［J］.Applied Soft Computing，2013，13 （1）：390－401.

［12］LIU Xingang，HUAI Jinpeng，GAO Qingyi.A virtual network embedding approach to preserving node closeness ［J］.Chinese Journal of Computers，2012，35 （12）：2492－2502（in Chinese）.［劉新剛，懷進鵬，高慶一.一種保持結(jié)點緊湊的虛擬網(wǎng)絡(luò)映射方法 ［J］.計算機學(xué)報，2012，35 （12）：2492－2502.］