交互更新模式的量子遗传算法的几何约束求解  

Solving geometric constraint based on the interactive update mode quantum genetic algorithm

作　　者：曹春红[1,2,3] 易荣庆[4] 曹海龙[1,2,3] 韩春燕[1,2,3] 

机构地区：[1]东北大学信息科学与工程学院,沈阳110819 [2]东北大学医学影像计算教育部重点实验室,沈阳110819 [3]南京大学计算机软件新技术国家重点实验室,南京210023 [4]国网吉林省电力有限公司,长春130012

出　　处：《中国图象图形学报》2016年第4期499-509,共11页Journal of Image and Graphics

基　　金：国家自然科学基金项目(61300096);中央高校基本科研业务费专项基金项目(N130404013)~~

摘　　要：目的针对传统量子遗传算法无法充分利用种群中未成熟个体信息的不足,提出了基于交互更新模式的量子遗传算法(IUMQGA)并应用于几何约束求解中。方法几何约束问题的约束方程组可转化为优化模型,因此约束求解问题可以转化为优化问题。采用将遗传算法与量子理论相结合的量子遗传算法,使用双串量子染色体结构,使用交互更新策略将遗传算法中的交叉操作利用量子门变换来实现,根据不同情况采用不同的交互更新策略。这里的交互,指的是两个个体进行信息交换的过程,该过程用以产生新的个体。这不仅增加了个体间信息的交换而且充分利用了种群中未成熟个体的信息,提高了算法的收敛速度。结果通过非线性方程实例和几何约束实例测试并与其他方法比较表明,基于交互更新模式的量子遗传算法求解几何约束问题具有更好的求解精度和求解速率。双圆外公切线问题实例中,IUMQGA算法比QGA算法稳定;单圆填充问题和双圆外公切线问题实例中,通过实验求得各变量的最优值与其相应的精确值的误差在1E-2以下。结论采用交互更新模式的量子遗传算法可以很好地求解几何约束问题。Objective Given that the traditional quantum genetic algorithm cannot make full use of immature individuals in a population, we proposed and used the quantum genetic algorithm based on interactive update mode （IUMQGA） in solving geometric constraints. Method The constraint equations of the geometric constraint problem can be transformed into the optimization model; therefore, constraint-solving problems can be transformed into the optimization problem. A quantum genetic algorithm, which combines genetic algorithm and quantum theory, using the double strand quantum chromosome structure, is emoloved to achieve the crossover operation of the genetic algorithm using quantum gate transformation.According to different situations, different interactive update strategies are adopted. The term ＂interactive＂ refers to the process of information exchange between two individuals. The process is used to generate new individuals. The IUMQGA uses the interactive update mode to achieve the crossover operation of the genetic algorithm using the quantum gate transfor- mation. The process not only increases information exchange between two individual but also makes full use of the informa- tion of immature individuals and improves the converge speed of the algorithm. Result The comparison of nonlinear equa- tions and geometric constraints with other methods shows that IUMQGA for solving geometric constraint problems has better accuracy and solving rate. The IUMQGA algorithm is more stable than the QGA algorithm in the case of the double circle tangent problem. The experiments reveal that the error of the optimal value of the variables and the corresponding accuracy is below 1E-2. Conclusion The IUMQGA can be used to solve the geometric constraint problem.

关 键 词：关键词:计算机辅助设计 几何约束求解 量子遗传算法 量子染色体 交互模式更新 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]