Abstract: The constraint equations of geometric constraint problem can be transformed into the optimization model, therefore constraint solving problem can be transformed into the optimization problem. Lack of information exchange between the individuals, the traditional quantum genetic algorithm is easy to fall into a local optimum. This paper proposes a dynamic population divided quantum genetic algorithm (DPDQGA) which is applied to geometric constraint solving. The individuals in populations exchange information spontaneously according to certain rules. In the beginning stage of the evolution of each generation, the individual fitness of two initial populations is calculated respectively. After merging the two populations, the league selection method is used to score the individuals in populations, and the populations are ranked according to the score. Finally, the merged populations are re-divided into two sub-populations. The experiments show that DPDQGA for solving geometric constraint problems has better accuracy and solving rate.

Key words: geometric constraint solving, quantum genetic algorithm, dynamic population divide

摘要： 几何约束问题的约束方程组可转化为优化模型，因此约束求解问题可以转化为优化问题。针对传统量子遗传算法个体间信息交换不足，易使算法陷入局部最优的缺点，提出了动态种群划分量子遗传算法（dynamic population divided quantum genetic algorithm，DPDQGA），并将其应用于几何约束求解中。该算法种群中的个体按照一定规则自发地进行信息交换。在每一代进化的开始阶段，分别对两个初始种群中的个体计算个体适应度。将两个种群合并，使用联赛选择的方法为种群中的个体打分，并按照得分对种群进行排序。最后将合并的种群重新划分为两个子种群。实验表明，基于动态种群划分的量子遗传算法求解几何约束问题具有更好的求解精度和求解速率。

关键词: 几何约束求解, 量子遗传算法, 动态种群划分