CAJ | 학술논문

几何约束问题的约束方程组可转化为优化模型，因此约束求解问题可以转化为优化问题。针对传统量子遗传算法个体间信息交换不足，易使算法陷入局部最优的缺点，提出了动态种群划分量子遗传算法（dynamic population divided quantum genetic algorithm，DPDQGA），并将其应用于几何约束求解中。该算法种群中的个体按照一定规则自发地进行信息交换。在每一代进化的开始阶段，分别对两个初始种群中的个体计算个体适应度。将两个种群合并，使用联赛选择的方法为种群中的个体打分，并按照得分对种群进行排序。最后将合并的种群重新划分为两个子种群。实验表明，基于动态种群划分的量子遗传算法求解几何约束问题具有更好的求解精度和求解速率。
궤하약속문제적약속방정조가전화위우화모형，인차약속구해문제가이전화위우화문제。침대전통양자유전산법개체간신식교환불족，역사산법함입국부최우적결점，제출료동태충군화분양자유전산법（dynamic population divided quantum genetic algorithm，DPDQGA），병장기응용우궤하약속구해중。해산법충군중적개체안조일정규칙자발지진행신식교환。재매일대진화적개시계단，분별대량개초시충군중적개체계산개체괄응도。장량개충군합병，사용련새선택적방법위충군중적개체타분，병안조득분대충군진행배서。최후장합병적충군중신화분위량개자충군。실험표명，기우동태충군화분적양자유전산법구해궤하약속문제구유경호적구해정도화구해속솔。
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.