计算机工程

• 人工智能及识别技术 • 上一篇    下一篇

一种新的自适应量子遗传算法

沙林秀1,2,贺昱曜1   

  1. (1. 西安石油大学陕西省钻机控制技术重点实验室,西安 710065;2. 西北工业大学航海学院,西安 710072)
  • 收稿日期:2012-08-08 出版日期:2013-09-15 发布日期:2013-09-13
  • 作者简介:沙林秀(1978-),女,博士研究生、讲师,主研方向:智能控制;贺昱曜,教授、博士、博士生导师
  • 基金项目:

    国家自然科学基金资助项目(60871080);陕西省自然科学基金资助项目(2012JQ8046);陕西省教育厅专项科研计划基金资助项目(11JK0933)

A New Self-Adaptive Quantum Genetic Algorithm

SHA Lin-xiu 1,2, HE Yu-yao 1   

  1. (1. Shaanxi Province Key Laboratory of Drilling Rigs Controlling Technique, Xi’an Shiyou University, Xi’an 710065, China; 2. School of Marine Science and Technology, Northwestern Polytechnical University, Xi’an 710072, China)
  • Received:2012-08-08 Online:2013-09-15 Published:2013-09-13

摘要:

现有基于Bloch球面坐标的量子进化算法存在收敛速度慢和鲁棒性不稳定的问题。为此,提出基于斐波那契特性更新的自适应量子遗传算法。在最优解的搜索过程中,考虑目标函数在搜索点的变化率,建立自适应因子λ,反映搜索点处目标适应度值相对于相邻两代最佳目标函数值一阶差分的变化,调整λ以改善算法收敛的方向和速度。分析量子旋转门转角步长调整策略,建立基于斐波那契数列特性的转角步长函数Δφ和Δθ的更新规则。应用该算法求解多维复杂函数的极值优化问题,时间复杂度理论分析和仿真结果证明,该算法在收敛速度、效率和稳定鲁棒性等方面均有明显改善。

关键词: 量子计算, Bloch球坐标, 量子遗传算法, 斐波那契数列, 自适应因子, 时间复杂度

Abstract:

The current quantum evolution algorithms based on the Bloch spherical coordinates have slow convergence rate and poor robustness. Aiming at the two shortages, a new self-adaptive Quantum Genetic Algorithm(QGA) which is based on the characteristic of Fibonacci sequence is proposed. In the process of searching the optimal solution, a self-adaptive factor λ is introduced to reflect the relative change rate which is relative to the difference of the best individual’s objective fitness between the parent generation and the child generation. The convergence rate and direction of the algorithm can be improved by adjusting the factor. It is constructed the rule of updating the rotation angle Δφ and Δθ which is based on Fibonacci sequence by studying its properties. Using the new algorithm to deal with the multidimensional complex functions, theoretical analysis of algorithm time complexity and the simulation results show that the new algorithm improves the convergence rate, efficiency and stability robustness.

Key words: quantum computation, Bloch spherical coordinates, Quantum Genetic Algorithm(QGA), Fibonacci sequence, self-adaptive factor, time complexity

中图分类号: