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

Improved quantum genetic algorithm for routing problem

作　　者：王宝伟[1] 王洪国[1] 刘乐[1] 

机构地区：[1]山东师范大学信息科学与工程学院,济南250014

出　　处：《计算机工程与应用》2008年第23期114-116,126,共4页Computer Engineering and Applications

基　　金：山东省自然科学基金(No.Q2006003)~~

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

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

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]