Journal of Frontiers of Computer Science and Technology ›› 2014, Vol. 8 ›› Issue (4): 397-405.DOI: 10.3778/j.issn.1673-9418.1308011

Previous Articles     Next Articles

Geometric Constraint Solving Based on Dynamic Population Divided Quantum Genetic Algorithm

CAO Chunhong1,2+, WANG Peng1   

  1. 1. College of Information Science and Engineering, Northeastern University, Shenyang 110819, China
    2. Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China
  • Online:2014-04-01 Published:2014-04-03

动态种群划分量子遗传算法求解几何约束

曹春红1,2+,王  鹏1   

  1. 1. 东北大学 信息科学与工程学院,沈阳 110819
    2. 吉林大学 符号计算与知识工程教育部重点实验室,长春 130012

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),并将其应用于几何约束求解中。该算法种群中的个体按照一定规则自发地进行信息交换。在每一代进化的开始阶段,分别对两个初始种群中的个体计算个体适应度。将两个种群合并,使用联赛选择的方法为种群中的个体打分,并按照得分对种群进行排序。最后将合并的种群重新划分为两个子种群。实验表明,基于动态种群划分的量子遗传算法求解几何约束问题具有更好的求解精度和求解速率。

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