摘要： 标准量子遗传算法(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

中图分类号: 

• TP391