Minimum Weight Triangulation Based On Improved Genetic Quantum Algorithm Computer Software And Theory

Triangulation plays a very important role in numerical approach, finite-element approach, numerical analysis, computer aided geometric design, computer graphic, computer vision, robot technology and so on. The minimum weight triangulation (MWT for short), in which the objective is to minimize the weight of triangulation of a set of planar points, is one of the open problems in computational geometry research field.It has been proved that neither the Greedy triangulation nor the Delaunay triangulation approximates the optimum. After diving into the problem of MWT based on traditional genetic algorithms and analyzing the deficiencies of them, the dissertation presents the very popular genetic quantum algorithm. As a new branch of genetic algorithms, it has very powerful capability of exploration and exploitation. Then a novel algorithm based on it for the problem of MWT is developed. New encoding mechanism for triangulation is presented. An original concept of Point Weight is proposed and used to be a link between the qubits and the candidate triangulations. Meanwhile, the genetic quantum algorithm is improved specially for the problem of MWT. The machined-made strategy of chromosome initialization, which easily leads to premature convergence, is discarded and replaced by the new strategy of random initialization. The globally best solution instead of the best solution of each generation is reserved to be the foundation of the qubits evolution so as to escape from the local optimum.Eventually, experimental results are demonstrated. It is proved that compared with the traditional genetic algorithm, the improved genetic quantum algorithm(IGQA for short) for the problem of MWT has much stronger capability of searching the global optimum and rapider convergence. Less parameters need to be ascertained and smaller population size and less iteration can make the algorithm reach the optimum. The results also show that the IGQA can increase the probability of hitting the optimum and get superior results than those which come from the well-known Greedy algorithm.