计算机网络路由选择中改进量子进化算法的应用

史望聪，耿 健

（1.陕西交通职业技术学院 信息工程系，陕西 西安　710018；2.陕西高速公路电子收费有限公司 陕西 西安　710018）

计算机网络路由选择中改进量子进化算法的应用

史望聪1，耿 健2

（1.陕西交通职业技术学院 信息工程系，陕西 西安710018；2.陕西高速公路电子收费有限公司 陕西 西安710018）

科技的发展和计算机技术的进步极大的带动了我国经济的发展，现阶段我国任何行业的发展都离不开对计算机网络的应用。但就目前互联网规划和拓展的实际情况来看，仍然存在着一些亟待解决的问题，其中最为典型的就是如何在满足互联网各节点通讯需求的前提下，选择可以提升互联网通信效率的计算机网络路由问题。与传统计算机网络路由选择算法相比，改进量子进化算法的应用能够有效的互联网通信效率。基于此，本文首先阐述了计算机网络路由选择的含义，然后对量子进化算法进行了分析，最后研究了量子进化算法的改进策略，希望能够引起读者的思考。

计算机网络；路由选择；改进量子进化算法；应用

众所周知，互联网已然成为了人们生活中不可或缺的部分，互联网为人们的衣食住行带来了便捷，同时我国现代经济的发展也离不开互联网的支持［1-3］。近年来，随着互联网的更大规模的规划和拓展，计算机网络路由选择存在的问题日益暴露出来。目前我国计算机网络路由选择算法已经不能满足现代社会发展的需求和计算机网络的正常运行需要，因此对计算机网络路由选择算法进行优化改进是现阶段我国计算机网络发展亟待解决的问题。下面本文就围绕量子进化算法的改进问题进行进一步的研究。

1　计算机网络路由选择的含义

爬山法、梯度法、模拟退算法和列表寻优法是计算机网络路由选择的传统方法，这些方法具有一定程度的局限性，并且受限条件也比较多，致使其作用无法得到有效的发挥［4-5］。计算机网络路由选择的主要含义为：在满足现有的计算机网络拓扑、网络通信容量和网络各节点需求的前提下，对网络各节点的路由进行选择，从而使计算机网络的时延性得到最大程度的缩小。通常情况下，计算机网络路由的选择可以运用一些简化工作：1）假设计算机网络各节点内部缓冲器的容量是足够大的，不可能因为溢出而导致数据包丢失；2）假设报文长度可以按实际指数分布，并且按照泊松到达；3）对节点处理报文的时延性进行忽略；4）所有报文传输均属于同等级服务。

2　量子进化算法的研究

2.1量子进化计算法

量子进化算法实际上是基于量子计划和进化算法的结合，该算法是建立在态矢量的基础之上的，并且以量子的比特编码表示染色体，而染色体的更新依靠量子旋转门和非门来实现，从而进一步完成计算机网络路由的最优化选择［6］。

在量子进化算法中，量子染色体可以用以下矩阵表示：

式中，αi，βi分别代表量子比特|0＞态和量子比特|1＞态的概率幅，并且两者之间满足以下条件：

问题的解可以由一个量子染色体进行表征，其主要原理是通过量子染色体的随机测量结果和概率方式，并通过二进制实现坍塌表现，在实践过程中我们不难发现量子染色体对问题解决有着明显的优越性［7］。然后，量子进化算法的进化是通过利用量子旋转门来实现的，其主要原理是利用搜索法将当前的解逼近至最佳解，利用概率增加或减少的形式对结果进行保留或者剔除，进而实现量子进化算法的进化。

当量子进化算法更新至第t代为P（t）=｛pt1，…，ptN｝，其适应值为：f（t）=｛ft1，…，ftN｝量子染色体ptj上基因位的第 i个值用向量（αi，βi）T进行表示，并采用量子旋转门对其进化，进而得到（α′i，β′i）T，具体进化方法如下式：

其中，θi代表旋转角，计算公式如下：

式中Δθi，s（αi，βi）的取值见表1，Δθi代表的是量子旋转门的旋转角值，主要作用是控制量子进化算法的收敛速度，而s（αi，βi）主要是完成对旋转门旋转角方向的控制，从而为算法向着最优解的方向开展搜索提供保障。

表1　函数查询表

表1中，xi代表第i位量子染色体的二进制解，bi表示第i位搜索的最佳二进制解，fx≥fb表示解x比解b更优。当量子染色体出现坍塌为二进制解而出现不变解的时候，可以采用下式进行处理：

其中，ε是一个正数，但是其数值比较小。

2.2量子进化算法的流程

1）初始化种群Q（t），t=0；

2）对初始种群中各个体进行测量，并得到一组状态P（t）。

3）评估P（t）的适应度

4）对最优的个体状态及其适应度值进行记录

5）如果处于非结束状态，然后继续进行以下步骤：

Begin

①t=t+1；

②测量种群Q（t-1），进而得到状态P（t）；

③评估P（t）的适应度

④利用量子门对Q（t）进行更新，得到子代种群Q（t+1）；

⑤将最优个体状态及其适应度值记录下来。

End

End

3　量子进化算法的改进研究

3.1调整优化旋转角

传统的量子进化算法应用过程中，旋转角的确定通常是利用查表的方式，故而旋转角是不连续的，在空间搜索方面具有跳跃性，导致搜索不够全面和精细［8-9］。文中从动态调整的角度出发对量子进化算法进行改进。其中，Δθi改进后的调整式为：

式中，fb表示搜索的最佳个体B及其使用度，fx表示当前个体X及适用度。通过对式（6）进行分析可得，Δθi代表的是一个区间，与其个体相适应。Δθi值越大，就表示当前个体与最佳个体之间的距离越远，搜索网络就越大。因此搜索速度需要进一步的提高。反之，Δθi值越小就表示当前个体与最佳个体之间的具体就越近，搜索网络就越小，能够采用个细搜索实现对最优解的寻找。

3.2函数调整优化

鉴于个体基因间的相关性不是很强的特点，量子位可以定义为：1）在满足归一化条件的前提下，而实现（αi，βi）的实数对，然后再对应到一个量子位相应的概率幅［10-12］。（2）将（1）中的量子位对应到相应的二维空间，其相位角为arctan（βi/αi），并用符号w进行表示。在上述定义的基础上，文中提出了一种通过二维空间中量子位的象限和相位角的大小来对旋转角的方向进行调整的方法，如表2所示。

表2　旋转角方向调整方法

最优个体B的第i个量子位的概率幅用表2中的αbi，βbi表示，其相位角为ωbi=arctg（βbi/αbi）；αxi，βxi表示个体第i个量子位概率幅的更新值，其相应的相位角为：ωxi=arctg（βxi/αxi）。量子位的更新旋转方向为：s（αxi/βxi），其中+1表示顺时针方向，-1表示逆时针方向［13］。通过对表2进行分析可得，通过这种方法可以有效的使当前的解无限逼近最优解，而且提高了收敛速度。

4　改进量子进化算法的仿真测试

为了进一步的说明本文所提出的改进量子进化算法在计算机网络路由选择中的优越性，下面进行了仿真实验，并且和传统的算法进行了比较，实验结果如图1所示。

图1　改进算法和传统算法性能对比

根据图1可知，文中所研究的改进量子进化算法与传统的量子进化算法相比具有明显的优越性，其寻优能力和收敛速度都有了很大程度的提升［14］。通过仿真测试，可以有效的为改进后量子进化算法在实际计算网络路由选择的应用提供指导作用，保证改进后的算法在实际应用过程中发挥其最大的作用。通过利用这种改进方法可以保证选择的路由能够很好的处理计算机网络运行过程中出现的问题，从而维护计算机网络的正常运行，有效提高工作人员的工作效率［15］。实际计算机网络路由选择的应用过程中，文中所研究的改进方法也得到了证实。

5　结束语

总而言之，在计算机网络技术飞速发展的今天，计算机网络路由的选择显得尤为关键，这就进一步推动了对计算机量子进化算法的改进研究。文中所提出的量子进化算法的改进方法的建立在传统量子进化算法的基础之上的。通过仿真模拟，证实了文中所提出的改进方法无论是在寻优搜索还是在收敛速度上都表现出了明显的优势，有效的解决了目前计算机网络路由选择面临的问题，提高了互联网通信效率。

［1］文孟飞，彭军，张晓勇.无线传感器网络中基于同心圆树的路由选择算法［J］.中南大学学报：自然科学版，2012，43 （9）：3490-3495.

［2］张大陆，曹孝晶，胡治国.基于用户体验评价模型的最优路由选择算法［J］.计算机应用，2012，32（10）：2683-2688.

［3］杨晓琴，章丽芳，曹庆皇.基于链路带宽利用率的路由选择算法［J］.计算机应用，2012，20（9）：2422-2425.

［4］雷华军，秦开宇.基于改进量子进化算法的测试优化选择［J］.仪器仪表学报，2013（4）：838-844.

［5］赵荣香.改进量子进化算法在计算机网络路由选择中的应用探究［J］.科技传播，2014（24）：148-152.

［6］宋明红，俞华锋，陈海燕.改进量子进化算法在计算机网络路由选择中的应用研究［J］.科技通报，2014（1）：170-173.

［7］刘宏艳，王伟，翟颖.计算机网络路由优化及优化算法的运用［J］.赤子，2014（17）：241.

［8］宋强磊，车阿大.量子进化算法在生产调度中的应用综述［J］.计算机应用研究，2012，29（5）：1601-1605.

［9］魏娜，黄学宇，刘守东.量子进化算法原理及改进策略研究［J］.计算机工程，2011，37（20）：223-226.

［10］叶庆波.量子Grover算法的改进及其在Ad Hoc网络路由选择中的应用［D］.南京：南京邮电大学，2013.

［11］赵清艳，熊茂华.基于改进禁忌搜索算法的无线传感器网络路由选择［J］.计算机测量与控制，2012，20（5）：1442-1444.

［12］丁文.基于免疫多目标优化的网络组播路由选择［J］.计算机应用研究，2012，29（4）：1477-1479.

［13］田园，张杰.基于SpaceWire的链路状态算法研究与设计［J］.计算机工程，2011，37（23）：113-115.

［14］申晓宁.一种新型的多目标优化混合量子进化算法［J］.计算机应用研究，2012，29（12）：4441-4444.

［15］郑建国，钱洁.采用灰色码观测的量子进化算法［J］.信息与控制，2012，41（3）：350-355.

Application of computer network routing improved quantum evolutionary algorithm

SHI Wang-cong1，GENG Jian2
（1.Information Engineering of Shaanxi Vocational and Technical College，Xi'an 710018，China；2.Shaanxi Expressway Electronic Toll Co.，Ltd.，Xi'an 710018，China）

Progress and development of science and technology and computer technology greatly promoted China's economic development，the development of any industry are inseparable from our present stage of computer network applications. However，the current situation and to expand the Internet planning point of view，there are still some problems to be solved，the most typical is how to meet the needs of Internet communication nodes premise，select the computer network can improve the efficiency of Internet traffic routing problem.And conventional computer network routing algorithm，the improved application of quantum evolutionary algorithm can effectively Internet communications efficiency.Based on this，this paper describes the computer network routing meaning，then quantum evolutionary algorithms are analyzed，the final study of quantum evolutionary algorithm improvement strategies，hoping to arouse the reader ponder.

computer network；routing selection；improved quantum evolutionary algorithm；application

TNO

A

1674－6236（2016）09-0045-03

2015-09-17稿件编号：201509125

交通运输部科技计划项目（2015319G02190）

史望聪（1981—），男，陕西户县人，讲师。研究方向：计算机应用及交通信息化的教学与科研工作。