有效的混合量子遗传算法

An Effective Hybrid Quantum Genetic Algorithm

提出了一种可控旋转门操作及新的算法终止条件.可控旋转门操作使得几率幅值不仅可以收敛到0或1,还可以收敛到ε(1-ε),有利于算法跳出局部最优;而新的终止条件是利用种群的聚拢因子和量子位收敛因子而设定,使得终止参数γ尽可能地少受几率幅值干扰,更好地控制所得好解与其运行时间的关系.另外,把单纯形法作为局部搜索策略,利用其强方向性,使得算法效率有较大提高.最后的理论分析证明了新算法的全局收敛性,而数值实验在相应指标性能的对比上再次表明该算法有较快的收敛速度和较高的收敛精度.

It was indicated from the recent research that Quantum Genetic Algorithm （QGA） outperformed conventional genetic algorithm in its lower running time and ability of finding better solution when it solved a class of numerical and knapsack of combinatorial optimization problems. However, with quthit of quantum individual interfering, parameter γ of the termination criterion is difficult to determine. The rotate gate which can promote the population is difficult to change its state of qutbit, and this phenomenon often induces premature. To improve the performance of the QGA, a controllable rotate gate and a new termination criterion are proposed in this paper. The controllable rotation gate can induce the convergence of qutbit not only to either 0 or 1, but also to either √ε or √1-ε）, and make the proposed algorithm to escape the local optimum. Based on gathering factor and qutbit convergence factor, a new termination criterion is proposed. The qutbit decreases the impact on parameter γ and the new terminate criterion can efficienfly control the relation of better solution and its running time. In addition, the Simplex method is introduced as a local searching scheme, which greatly improves the performance of algorithm. At last, the global convergence of the proposed algorithm is proved in theory, and comparable numerical experiments show that the proposed algorithm is more powerful than the compared algorithm in solution quality and speed.