方位邻域信息互享差分虚拟网络映射算法

梁树杰，余轶生，黄旭彬

（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.］