一种基于量子染色体的遗传算法

A novel genetic algorithm based on the quantum chromosome

将进化理论和量子理论结合,提出一种基于量子计算概念和理论的量子遗传算法.算法借鉴量子比特的叠加性,采用量子编码来表征染色体,能够表示出许多可能的线性叠加状态.模拟量子坍塌的随机观察可带来丰富的种群,量子染色体的进化也能够简单方便地引导进化.因此,它比传统遗传算法具有更好的种群多样性,更快的收敛速度和全局寻优的能力.从理论上证明了它的全局收敛性,仿真计算也表明了此算法的优越性.

The genetic algorithm is an efficient optimization tool for its independence of problems, intrinsic parallelism and inherent learning capacity; however, it has some disadvantages such as slow convergence and prematurity. In this paper, a novel algorithm, called the quantum genetic algorithm—QGA, is proposed based on the combination of the quantum theory with the evolutionary theory. By adopting the qubit chromosome as a representation, QGA can represent a linear superposition of solutions due to its probabilistic representation. The random observation simulating the quantum collapse can bring diverse individuals, and the evolution of quantum chromosome can also pilot the evolution. So it has better diversity than the classical genetic algorithm. Rapid convergence and good global search capacity characterize the performance of QGA. The paper not only proves the global convergence of the QGA, but also some simulation experiments are shown to prove its superiority over other algorithms.