求解路由选择问题的改进量子遗传算法

doi:10.3778/j.issn.1002-8331.2008.23.035

计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (23): 114-116.DOI: 10.3778/j.issn.1002-8331.2008.23.035

求解路由选择问题的改进量子遗传算法

王宝伟,王洪国,刘乐

山东师范大学信息科学与工程学院，济南 250014

收稿日期:2007-10-23 修回日期:2008-01-09 出版日期:2008-08-11 发布日期:2008-08-11
通讯作者: 王宝伟

Improved quantum genetic algorithm for routing problem

WANG Bao-wei,WANG Hong-guo,LIU Le

School of Information Science & Engineering，Shandong Normal University，Jinan 250014，China

Received:2007-10-23 Revised:2008-01-09 Online:2008-08-11 Published:2008-08-11
Contact: WANG Bao-wei

摘要/Abstract

摘要： 网络中存在许多设计和优化问题，其中相当一部分属于NP类型，传统的解法由于计算复杂度过大而失效；提出了一种求解路由选择问题的改进量子遗传算法（IQGA），该算法首先在量子个体上实施量子交叉，这一操作有利于保留相对较好的基因段；其次，采用量子比特相位法更新量子门和自适应调整搜索网格的策略；最后，进行局部搜索操作策略，使得种群的多样性强，解得收敛精度高，收敛速度快；通过路由选择实验标明此算法的质量和效率都强于传统的遗传算法，并且具有较强的实用性和鲁棒性。

关键词: 量子遗传算法, 量子杂交, 旋转量子门, 路由选择

Abstract: There exists many design and optimization problems in network，and parts of them belong to NP type.This paper proposes an Improved Quantum Genetic Algorithm（IQGA）.First，the quantum crossover is used which can maintain the relatively good gene blocks.Second，the strategies of updating quantum gate using qubit phase approach and adjusting search grid adaptively are introduced.Third，the local searching scheme method is introduced，which is characterized by rapid convergence，good global search capability and short computing time.As can be seen from the outcome of the routing experiment，the quantum genetic algorithm gains an advantage over the conventional genetic algorithm.Its search speed is faster and its efficiency is higher.Furthermore，it has stronger practicality and robustness.

Key words: quantum genetic algorithm, quantum crossover, quantum gate, routing

王宝伟,王洪国,刘乐. 求解路由选择问题的改进量子遗传算法[J]. 计算机工程与应用, 2008, 44(23): 114-116.

WANG Bao-wei,WANG Hong-guo,LIU Le. Improved quantum genetic algorithm for routing problem[J]. Computer Engineering and Applications, 2008, 44(23): 114-116.

[1]	李胜1，张培林1，李兵2，吴定海1，胡浩3. 基于通用量子门的量子遗传算法及应用[J]. 计算机工程与应用, 2017, 53(7): 54-59.
[2]	曹芳波，吕娜，陈柯帆，张步硕，刘创. 航空集群网络可靠性估计路由选择策略[J]. 计算机工程与应用, 2017, 53(24): 129-135.
[3]	费凯，杨任农，黄震宇，李秋妮. 考虑时间约束的空战编队协同火力分配研究[J]. 计算机工程与应用, 2016, 52(13): 259-264.
[4]	刘名武1，2，万谧宇1，彭冠军3. 绩效保障模式下的装备可修部件售后保障策略[J]. 计算机工程与应用, 2015, 51(17): 245-249.
[5]	刘章1，谭阳2. 改进遗传算法的WSN节点最优路由选择策略[J]. 计算机工程与应用, 2015, 51(13): 101-105.
[6]	胡积宝. 基于QoS的光网络路由选择算法的研究[J]. 计算机工程与应用, 2014, 50(10): 101-104.
[7]	易正俊，侯坤，何荣花. 自适应Bloch球面的量子遗传算法[J]. 计算机工程与应用, 2012, 48(35): 57-61.
[8]	沙林秀1，贺昱曜1，陈延伟2. 一种变步长双链量子遗传算法[J]. 计算机工程与应用, 2012, 48(20): 59-63.
[9]	周敏. 量子遗传算法优化神经网络的MIMO-OFDM检测研究[J]. 计算机工程与应用, 2011, 47(27): 161-163.
[10]	赵敏1，张路1，孙棣华1，阳树洪2. 模糊Renyi熵与QGA结合的快速图像分割[J]. 计算机工程与应用, 2011, 47(16): 172-175.
[11]	袁正午，梁均军. 累积链路质量无线传感器网络路由算法研究[J]. 计算机工程与应用, 2011, 47(14): 66-69.
[12]	邓长春. 基于量子进化算法的路由选择[J]. 计算机工程与应用, 2010, 46(23): 103-105.
[13]	廉侃超，宣士斌，李永胜，古明家. 改进人口迁移算法用于QoS路由优化[J]. 计算机工程与应用, 2010, 46(10): 94-96.
[14]	叶奇明¹，梁根². 量子遗传算法的模糊K-prototypes聚类[J]. 计算机工程与应用, 2010, 46(1): 112-115.
[15]	李成¹,李飞². 改进量子遗传算法及其在FIR滤波器设计中的应用[J]. 计算机工程与应用, 2009, 45(4): 239-241.

求解路由选择问题的改进量子遗传算法

Improved quantum genetic algorithm for routing problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics