基于改进量子进化算法的计算机网络最佳路由选择分析

2016-05-07查道贵许彩芳

宿州学院学报 2016年2期

关键词：仿真计算机网络

查道贵，许彩芳

宿州职业技术学院计算机信息系，安徽宿州，234101

基于改进量子进化算法的计算机网络最佳路由选择分析

查道贵，许彩芳

宿州职业技术学院计算机信息系，安徽宿州，234101

摘要：为了进一步改进网络性能，采用改进量子进化算法优化计算机网络中路由选择问题，运用量子计算方法得出并评估具体状态及相关适应数值，并通过改进量子进化算法的旋转角度、调整函数等手段来优化路由选择和流量分布。算法仿真测试表明改进后的量子进化算法平均时延低、链路利用效率高、降低了拥塞、提升了质量，因此，改进量子进化算法更符合路由选择问题的求解，可使得路由在面临选择的过程中具备更加优越的收敛速度和寻优功能。

关键词：改进量子进化算法；计算机网络；路由选择；仿真

量子计算是利用量子世界的叠加形态以及纠缠性与相干性等特点，促使量子信息系统突破以往经典信息体系的限制。现阶段，用量子计算方法解决经典计算中的NP问题(非图灵机上的多项式时间算法问题)是研究的焦点，其中量子进化算法是最新形成的以量子计算原理为基础的概率优化方法，它以量子计算中的概念、理论为基础，用量子位编码表示染色体，并巧妙借助量子门的功能进行搜索。因其自身的种群规模小，且不会对算法性能产生影响，故有收敛速度快、在全局寻优能力强的优点。本文主要分析用改进量子进化算法的计算机网络最佳路由选择问题，以证明这种算法在路由选择问题方面的可行性。

1路由选择问题

在现代计算机通信网络系统中，用数据包平均传输时延作为衡量网络性能的指标，其中科学合理的路由策略可以促使各个节点发送出的报文按时到达目的地，缩减额外费用，并高效利用网络资源，降低整个运营成本[1]。在已知的网络拓扑、链路容量与各个节点在满足通信要求的条件下，怎样确定节点对通信路由产生的作用，降低网络平均时延，这种路由选择优化问题属于非线性0-1规划问题，其数学模型可表示如下：

(1)

2量子进化算法

这种算法是将量子计算和进化算法有机结合，是在量子态矢量的基础上进行计算，用量子比特编码代表染色体，同时用量子旋转门、量子肺门更新染色体，进一步优化求解目标问题。在量子进化算法中，用下列矩阵代表量子染色体，长度单位m。

(2)

公式(2)中，量子比特|0>态的概率幅度用αm表示，其中|1>态的概率幅度用βm表示，且满足下面归一化要求：

αn2+βn2=1，n=1，2，3，…，m

(3)

为了解空间的全部解叠加情况，借助量子染色体作为坍塌解，可知量子染色体能很好地体现出解的多样性，但要借助量子旋转门完成量子计划算法的进化对策。原理：利用搜索方法把新得出的解无限逼近找出最优解，保留各种概率增加行驶，消除各种无用结果的概率行驶，促使其向进化方向发展[3-4]。

(4)

其中，θi表示旋转角度，具体计算方法为：

θi=Δθis(αi，βi)π

(5)

在这个公式中，量子旋转门的旋转角度数值用Δθi表示，其取值范围如表1所示。主要控制算法收敛速度，其中量子旋转门旋转角度的方向是由函数s(αi，βi)实现，确保算法向最优解方向进行搜索。

表1　函数数值取值表

表1中，最优二进制解搜索b的第i位用bi表示，且解x比解b更优用fx≥fb代表。由于量子染色体可能发生坍塌新城二进制解的概率，继而发生不变解，公式(6)可以化解这种不良情况。

(6)

其中ε表示某一个正数，数值很小。

量子计算方法的程序，首先初始化种群确保Q(t)，其中t为0，开始测量种群的各个个体，得出一组状态P(t)，评估它的适应度，并记录下最佳个体状态的相应适应度数值，当其处于非技术状态下开始计算，要求t=t+1，检测出种群Q(t-1)，得出具体状态并评估，再通过量子门更新Q(t)，得出子代种群Q(t+1)，并记录最佳个体状态及其相关适应度数值[5]。

3改进量子进化算法

在不断更新种群的过程中，改进量子进化法，其中合理调整Δθi以及s(αi，βi)是重点内容。以往算法多先查表，给出不连续性旋转角度，这样，针对各个问题解空间的搜索带有一定的跳跃性，因此需要对其进行动态改进。

3.1检测初始种群

由于改进后的量子进化算法编码是多维的，操作0、1字符串时，需要将量子进化的编码映射至二进制编码方面，具体测量过程：在一个[0，1]的数值区间范围内，如果壁概率幅度大，检测出来的结果是1，相反则是0，评估解的适应度，将其作为下一步演化的目标数值[6]。

3.2优化调整旋转角度

3.3优化调整函数

采用组合优化法可知，个体基因之间的关联性较弱，对于这种情况定义量子位。

定义1：满足归一化条件，进一步实现(αi，βi)的实数对，得出量子位概率幅度。

定义2：找出定义1中量子位所对应的二维空间，相位角度是arctan(βi/αi)，并用符号ω表示，其中ω∈(-π/2，π/2)。

依照上述两个定义，设计出一种依照量子位且在二维实空间内的象限，并不断调整相位角大小、旋转角度方向。搜索出来的αib，βib是最优个体B中第i个量子位概率幅度，其中相位角度ωib=arctg(βib /αib)，个体中第i个量子位的概率幅度待更新数值，用αix，βix表示，更新以后的量子位方向的变化用s(αix，βix)表示，其中顺时针方向需用+1表示，而逆时针方向用-1表示，进一步促使现行解向最优解方向靠近。随着收敛速度越来越快，列出第一象限的数据，并检查其他各个象限的具体情况，找出不同类型的旋转方向。

3.4变异

通过变异，可以有效阻止没有成熟收敛于各种算法的小范围内搜索功能，由量子非门操作量子变异。具体方法：先从一定概率的种群中选出若干个个体，针对选出的个体依照确定概率决定一个或者多个变异位。针对选中的位量子比特概率幅度进行量子非门操作。量子变异操作实质上改变了比特态叠加状态，促使原来向1方向坍缩方向转变成0，且这种变异操作对于染色体的叠加状态会产生一定效果[8]。

4算法仿真测试

为了进一步证明算法在计算机网络系统中属于最佳选择路径，需要对这种算法进行仿真实验，然后和传统量子进化算法作详细比较，所得实验结果如表2所示。由表2可知，改进的量子进化算法的寻优功能、收敛速度明显优于传统的量子进化算法，且在计算机网络路由选择方面，表现出良好的性能。

表2　路由选择仿真　　　　　%

同时，将改进后的量子进化算法所得结果和改进遗传算法、禁忌搜索算法进行对比可知，前者的平均时延、链路利用效率均优于后二者，且结果稳定。在一定程度上表明了在网络负荷增重、分组长度增加的情况下，改进量子进化算法可以搜索到合理路由，进而把流量从利用率高的链路再次分配至利用率较低的链路，并且确保流量分布均匀，降低拥塞概率，提升解质量。

5结束语

将改进量子进化算法应用于计算机网络系统中，可以让计算机网络路由在遇到选择时获取更加快速的收敛速度、更好的寻优功能。且在一定程度上解决了计算机通信链路需要解决的最优路由难题。同时，还能降低网络平均时延和费用，从而降低网络总体运营费用，提高链路利用效率。将改进量子进化算法应用于优化计算机网络路由选择中，效果良好，可以为其他类型网络的性能优化提供有益借鉴。

参考文献：

[1]宋明红，俞华锋，陈海燕．改进量子进化算法在计算机网络路由选择中的应用研究[J]．科技通报，2014，8(1)：170-173

[2]张大陆，曹孝晶，胡治国．基于用户体验评价模型的最优路由选择算法[J]．计算机应用，2012(10)：2683-2695

[3]杨晓琴，章丽芳，曹庆皇，等．基于链路带宽利用率的路由选择算法[J]．计算机应用，2012(9)：2422-2425

[4]赵清艳，熊茂华．基于改进禁忌搜索算法的无线传感器网络路由选择[J]．计算机测量与控制，2012，2(5)：1442-1444

[5]朱凯．FCoE路由管理模块的设计与实现[D]．北京：北京邮电大学计算机学院，2010：14-18

[6]宋强磊，车阿大．量子进化算法在生产调度中的应用综述[J]．计算机应用研究，2012，6(5)：1601-1605

[7]苏超．基于Kademlia协议的网络模型和路由的研究[D]．成都：西华大学计算机与软件工程学院，2009：36-43

[8]夏礻韦，于舒娟，张昀．基于量子免疫优化的盲检测算法[J]．计算机技术与发展，2014，04(4)：41-44

(责任编辑：汪材印)

中图分类号：TP393.02

文献标识码：A