Computer Engineering and Applications ›› 2008, Vol. 44 ›› Issue (23): 114-116.DOI: 10.3778/j.issn.1002-8331.2008.23.035

• 网络、通信、安全 • Previous Articles     Next Articles

Improved quantum genetic algorithm for routing problem

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

  1. 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

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

王宝伟,王洪国,刘 乐   

  1. 山东师范大学 信息科学与工程学院,济南 250014
  • 通讯作者: 王宝伟

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

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

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