计算机工程 ›› 2013, Vol. 39 ›› Issue (7): 247-251,256.doi: 10.3969/j.issn.1000-3428.2013.07.055

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

基于变异概率分析的改进QGA及其应用

戴勇谦1a,张明武1b,祝胜林1b,戴勇新2   

  1. (1. 华南农业大学 a. 公共基础课实验教学中心;b. 信息学院,广州 510642;2. 江西机电职业技术学院,南昌 330013)
  • 收稿日期:2012-07-30 出版日期:2013-07-15 发布日期:2013-07-12
  • 作者简介:戴勇谦(1975-),男,实验师、硕士,主研方向:遗传算法,神经网络;张明武、祝胜林,副教授、博士;戴勇新,副教授
  • 基金项目:
    国家自然科学基金资助项目(61272404)

Improved QGA Based on Mutation Probability Analysis and Its Application

DAI Yong-qian 1a, ZHANG Ming-wu 1b, ZHU Sheng-lin 1b, DAI Yong-xin 2   

  1. (1a. Center of Experimental Teaching for Common Basic Courses; 1b. School of Information, South China Agricultural University, Guangzhou 510642, China; 2. Jiangxi Vocational College of Mechanical & Electrical Technology, Nanchang 330013, China)
  • Received:2012-07-30 Online:2013-07-15 Published:2013-07-12

摘要: 标准量子遗传算法(QGA)在应用于组合优化问题时,会由于早熟收敛而陷入局部最优。为解决该问题,引入k位变异子空间概念分析Q-bit的变异概率分布,指出传统随机变异机制和QGA自有变异机制之间的冲突,提出一种基于观测状态的阶段式大尺度变异机制。将该机制的变异算子嵌入量子旋转策略表,对不同规模的0/1背包问题进行测试,结果表明,该机制能有效避免早熟收敛,跳出局部最优,全局寻优能力优于标准QGA。

关键词: 量子计算, 量子遗传算法, 变异机制, 变异概率分布, 组合优化, 0/1背包问题

Abstract: Standard Quantum Genetic Algorithm(QGA) is premature convergence to local optima when it is applied to combinatorial optimization. To solve this problem, this paper analyzes the mutation probability distribution of Q-bit by introducing the k bit variation subspace conception and points out the conflict of traditional random mutation mechanism and the QGA self-implied variation mechanism. Based on these analysis, a novel Stage Large-scale Variation Mechanism Based on Observation(SLVMBOO) is proposed. Mutation operator of SLVMBOO which is embedded in the quantum rotation policy table is simple to implement and it is highly efficient. The tests results of different scale of 0/1 knapsack problem show that this mechanism can effectively avoid the premature convergence and successfully jump out of local optima when it is applied to combinatorial optimization. The global optimization ability is superior to the standard QGA.

Key words: quantum computation, Quantum Genetic Algorithm(QGA), mutation mechanism, mutation probability distribution, combinatorial optimization, 0/1 knapsack problem

中图分类号: