Computer Science and Information Systems 2024 Volume 21, Issue 4, Pages: 1547-1565
https://doi.org/10.2298/CSIS230907047Y
Full text (
374 KB)
A hybrid GA-powell algorithm for geometric constraint solving
Yunlei Sun (Qingdao Institute of Software, College of Computer Science and Technology, China, University of Petroleum (East China) Qingdao, China), sunyunlei@upc.edu.cn
Yucong Li (Qingdao Institute of Software, College of Computer Science and Technology, China, University of Petroleum (East China) Qingdao, China), s21070036@s.upc.edu.cn
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 efficiency 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.
Keywords: genetic algorithm, Powell’s algorithm, geometric constraint solving, similarity calculation
Show references
Ait-Aoudia, S., Bahriz, M., Salhi, L.: 2d geometric constraint solving: An overview. In: 2009 Second International Conference in Visualisation. pp. 201-206. IEEE (2009)
Borning, A.: The programming language aspects of thinglab, a constraint-oriented simulation laboratory. ACM Transactions on Programming Languages and Systems (TOPLAS) 3(4), 353- 387 (1981)
Bose, N., Bose, N.: Gröbner bases: An algorithmic method in polynomial ideal theory. Springer (1995)
Chen, R., Chu, J., Zhang, B.: A coincidental calculation method of some terminal-guided projectile inertial navigation segment ballistic coeffcients based on powell method. Fire Control & Command Control 45(8), 176-180 (2020)
Chunhong, C., Bin, Z., Limin, W., Wenhui, L.: The parametric design based on organizational evolutionary algorithm. In: PRICAI 2006: Trends in Artificial Intelligence: 9th Pacific Rim International Conference on Artificial Intelligence Guilin, China, August 7-11, 2006 Proceedings 9. pp. 940-944. Springer (2006)
Gao, X., Sun, L., Sun, D., et al.: Artificial immune-chaos hybrid algorithm for geometric constraint solving. Inf. Technology J pp. 360-365 (2009)
Hillyard, R., Braid, I.: Analysis of dimensions and tolerances in computer-aided mechanical design. Computer-Aided Design 10(3), 161-166 (1978)
Hillyard, R., Braid, I.: Characterizing non-ideal shapes in terms of dimensions and tolerances. In: Proceedings of the 5th annual conference on Computer graphics and interactive techniques. pp. 234-238 (1978)
Li, C., Li, G., Tan, Y., Xu, X.: Medical image registration algorithm based on powell algorithm and improved genetic algorithm. Journal of Computer Applications 33(3), 640-644 (2013)
Light, R., Gossard, D.: Modification of geometric models through variational geometry. Computer-Aided Design 14(4), 209-214 (1982)
Light, R.A., Gossard, D.C.: Variational geometry: a new method for modifying part geometry for finite element analysis. Computers & Structures 17(5-6), 903-909 (1983)
Lin, V.C., Gossard, D.C., Light, R.A.: Variational geometry in computer-aided design. ACM SIGGRAPH Computer Graphics 15(3), 171-177 (1981)
Liu, X., Yin, X., Li, C.: Improvements of powell mechanical optimization. Journal of Machine Design 36(6), 80-86 (2019)
Lu, M., Qu, L., He, D.: Pathfinder grey wolf algorithm for solving multiple-roots nonlinear equations. Chinese Journal of Engineering Mathematics 39(6), 957-968 (2022)
Michalewicz, Z., Schoenauer, M.: Evolutionary algorithms for constrained parameter optimization problems. Evolutionary computation 4(1), 1-32 (1996)
Nelson, G.: Juno, a constraint-based graphics system. In: Proceedings of the 12th annual conference on Computer Graphics and Interactive Techniques. pp. 235-243 (1985)
Para,W., Bhat, S., Guerrero, P., Kelly, T., Mitra, N., Guibas, L.J.,Wonka, P.: Sketchgen: Generating constrained cad sketches. Advances in Neural Information Processing Systems 34, 5077- 5088 (2021)
Powell, M.J.: An efficient method for finding the minimum of a function of several variables without calculating derivatives. The computer journal 7(2), 155-162 (1964)
Sampson, J.R.: Adaptation in natural and artificial systems (john h. holland) (1976)
Seff, A., Ovadia, Y., Zhou, W., Adams, R.P.: Sketchgraphs: A large-scale dataset for modeling relational geometry in computer-aided design. arXiv preprint arXiv:2007.08506 (2020)
Sutherland, I.E.: Sketchpad: A man-machine graphical communication system. In: Proceedings of the May 21-23, 1963, spring joint computer conference. pp. 329-346 (1963)
Wenjun, W.: Basic principles of mechanical theorem proving in elementary geometries. Selected Works Of Wen-Tsun Wu p. 195 (2008)
Yuan, H., Li, W., Yi, R., Zhao, K.: The tpso algorithm to solve geometric constraint problems. Journal of Computational Information Systems 2(4), 1311-1316 (2006)
Yuan, H., Chang, X.: Combining genetic algorithm with simlex method for geometric constraint solving. In: 2010 International Conference on Computer, Mechatronics, Control and Electronic Engineering. vol. 1, pp. 453-455. IEEE (2010)
Yuan, H., Yu, C.: Optimization genetic algorithm for geometric constraint solving. In: 2010 International Conference on Artificial Intelligence and Education (ICAIE). pp. 590-593. IEEE (2010)
Zbigniew, M.: Genetic algorithms+ data structures= evolution programs. Comput Stat pp. 372- 373 (1996)