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

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