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

Improved QGA Based on Mutation Probability Analysis and Its Application

作　　者：戴勇谦[1] 张明武[2] 祝胜林[2] 戴勇新[3] 

机构地区：[1]华南农业大学公共基础课实验教学中心,广州510642 [2]华南农业大学信息学院,广州510642 [3]江西机电职业技术学院,南昌330013

出　　处：《计算机工程》2013年第7期247-251,256,共6页Computer Engineering

基　　金：国家自然科学基金资助项目(61272404)

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

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

分 类 号：TP391[自动化与计算机技术—计算机应用技术]