Cao Chunhong, Yi Rongqing, Cao Hailong, Han Chunyan. Solving geometric constraint based on the interactive update mode quantum genetic algorithm[J]. Journal of Image and Graphics, 2016, 21(4): 499-509. DOI: 10.11834/jig.20160412.
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. 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 employed 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 transformation. The process not only increases information exchange between two individual but also makes full use of the information of immature individuals and improves the converge speed of the algorithm. The comparison of nonlinear equations 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. The IUMQGA can be used to solve the geometric constraint problem.