A Hybrid GA-Powell Algorithm for Geometric Constraint Solving

Sun Yunlei ; Li Yucong

Computer Science and Information Systems, Tome 21 (2024) no. 4.

Résumé

Geometric constraint solvers are crucial for computer-aided design (CAD), and their algorithms are the focus of research. Current geometric constraint solvers based on traditional numerical methods lack support for multi-solution problems, so we propose a hybrid algorithm that combines the genetic algorithm, which is good at global convergence, and Powell’s method, which is good at local refinement, to address the limitations of traditional numerical methods in geometric constraint solving algorithms (sensitivity to initial values, susceptibility to falling into local optimums, and being only able to obtain a single solution) and the challenges of intelligent optimization algorithms (complex parameter tuning, slow convergence and low accuracy). Our method has a large accuracy improvement over the comparison method in basically all test cases, and its effciency can also meet the needs of real geometric constraint solving scenarios. This research provides new insights into the design of geometric constraint solving algorithms, offers a fresh perspective on improving the performance and generality of solvers, and contributes to technological advances in the CAD field.

Détail

Keywords: genetic algorithm, Powell’s algorithm, geometric constraint solving, similarity calculation