方位鄰域信息互享差分虛擬網絡映射算法

梁樹杰，余軼生，黃旭彬

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

0 引 言

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

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

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

1.1 方位鄰域結構思想

方位的概念其實就是我們日常所說的各個方向位置，如東、西、南、北、東南、西南等。古時航海家為了準確把握航行方向，在羅盤上細分為十六分位甚至三十二分位，中國曾經也用八卦、地支、天干等表示方位，這些都是傳統的方位分法比較籠統。在現代航空、航海等領域對于方位的定義更加嚴格，甚至使用GPS精確定位，方向的說法也相應的變為正東、正西、正南、正北、東偏南∠xo（x ∈0～90）等，在這種定義中，正東、正西、正南、正北是固定的方向，而東南、西南、東北、西北則被細化為帶角度的動態方向不再固定，基于這種思想利用前者設計固定的鄰域結構，而利用后者設計動態的鄰域結構（如圖1所示）。

圖1 方位鄰域結構

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

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

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

差分進化個體xlk的隨機動態鄰域為

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

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

1.2 差分變異方式

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

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

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

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

1.3 DNDE算法流程

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

2 仿真分析

2.1 仿真設計

選取相關文獻使用的5個通用標準函數對算法進行測試，計算機平臺仿真軟件：matlab2012a，操作系統：win7，CPU：AMD Athlon（tm）X4 641，RAM：6G

圖2 DNDE算法流程

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

表1 基準測試函數相關參數

2.2 仿真結果分析

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

表2 3種算法優化結果

圖3 f1最優值對比結果

圖4 f2最優值對比結果

圖5 f3最優值對比結果

圖6 f4最優值對比結果

圖7 f5最優值對比結果

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

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

2.3 閾值實驗及結果分析

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

表3 閾值對算法影響

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

3 方位鄰域隨機動態信息互享差分虛擬網絡映射算法

3.1 問題描述及目標函數

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

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

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

在虛擬網絡映射中，一般控制和轉發網絡是分離的，為了確保高級用戶群體的服務質量，在現有資源約束下，以底層網絡剩余資源最大作為優化目標，則虛擬網絡的優化模型為［10］

約束條件為

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

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

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

步驟3 如果當前差分種群的全局最優值滿足終止條件則終止算法并輸出最優虛擬網絡映射方案。

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

步驟5 轉步驟2。

3.2 實驗評估分析

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

節點資源利用率

鏈路資源利用率

收益成本比

對比算法選用基于貪婪 （GREEDY）算法的虛擬網絡映射方案，式 （14）～式 （16）3個評價指標的仿真結果如圖8～圖10所示。

圖8 節點資源利用率

圖9 鏈路資源利用率

圖10 營運收益成本比

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

4 結束語

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

［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）.［拓守恒，周濤.基于維度分組交叉的自適應差分進化算法 ［J］. 計算機工程與設計，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）. ［王聯國，洪毅.基于馮·諾依曼鄰域結構的人工魚群算法 ［J］.控制理論與應用，2010，27 （6）：775－780.］

［8］Zhu W，Tang Y，Fang 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）.［程祥，張忠寶，蘇森.基于粒子群優化的虛擬網絡映射算法 ［J］.電子學報，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）.［劉新剛，懷進鵬，高慶一.一種保持結點緊湊的虛擬網絡映射方法 ［J］.計算機學報，2012，35 （12）：2492－2502.］