CLC number: TP391.72
On-line Access: 2024-08-27
Received: 2023-10-17
Revision Accepted: 2024-05-08
Crosschecked: 0000-00-00
Cited: 1
Clicked: 4995
LIU Sheng-Li, TANG Min, DONG Jin-Xiang. Solving geometric constraints with genetic simulated annealing algorithm[J]. Journal of Zhejiang University Science A, 2003, 4(5): 532-541.
@article{title="Solving geometric constraints with genetic simulated annealing algorithm",
author="LIU Sheng-Li, TANG Min, DONG Jin-Xiang",
journal="Journal of Zhejiang University Science A",
volume="4",
number="5",
pages="532-541",
year="2003",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.2003.0532"
}
%0 Journal Article
%T Solving geometric constraints with genetic simulated annealing algorithm
%A LIU Sheng-Li
%A TANG Min
%A DONG Jin-Xiang
%J Journal of Zhejiang University SCIENCE A
%V 4
%N 5
%P 532-541
%@ 1869-1951
%D 2003
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.2003.0532
TY - JOUR
T1 - Solving geometric constraints with genetic simulated annealing algorithm
A1 - LIU Sheng-Li
A1 - TANG Min
A1 - DONG Jin-Xiang
J0 - Journal of Zhejiang University Science A
VL - 4
IS - 5
SP - 532
EP - 541
%@ 1869-1951
Y1 - 2003
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.2003.0532
Abstract: This paper applies genetic simulated annealing algorithm (SAGA) to solving geometric constraint problems. This method makes full use of the advantages of SAGA and can handle under-/over- constraint problems naturally. It has advantages (due to its not being sensitive to the initial values) over the Newton-Raphson method, and its yielding of multiple solutions, is an advantage over other optimal methods for multi-solution constraint system. Our experiments have proved the robustness and efficiency of this method.
[1]Aldefeld, B., 1988. Variation of geometries based on a geometric-reasoning method. CAD, 20(3):117-126.
[2]Borning, A.H., 1981. The programming language aspects of ThingLab, a constraint oriented simulation laboratory. ACM TOPLAS, 3(4):353-387.
[3]Bose, N.K., 1985. Multidimensional Systems Theory. D. Reidel Publishing Co., p.184-232.
[4]Bouma, W., Fudos, I., Hoffmann, C.M., Cai, J. and Paige, J., 1994. A geometric contraint solver. CAD, 27:487-501.
[5]Bruderlin, B., 1990. Symbolic Computer Geometry for Computer Aided Geometric Design. In: Advances in Design and Manufacturing Systems, NSF conference, AZ, USA.
[6]Davis, L., 1991. Handbook of Genetic Algorithms. Van Nostrand Reinhold, New York.
[7]David, P. and Borut, Z., 2001. A Geometric Constraint Solver With Decomposable Constraint Set. Skala, V.Eds., The 9th International Conference in Central Europe on Computer Graphics and Visualisation'01 - WSCG'01, Plzen, Czech Republic, University of West Bohemia, 2:222-229.
[8]De Jong, K., 1975, An Analysis of the Behavior of a Class of Genetic Adaptive Systems. PhD Dissertation, University of Michigan. Dissertation Abstract International, 36(10), 5140B.(University Microlms No.76-9381).
[9]Dennis, J.E. and Schnabel, R.B., 1983. Numerical Methods for Unconstrainted Optimization and Nonlinear Equations. Prentice-Hall Inc., New Jersey.
[10]Durand, C., 1998. Symbolic and Numerical Techniques for Constraint Solving. PhD thesis, Department of Computer Sciences, Purdue University, IN, USA.
[11]Durand, C. and Hoffmann, C.M., 1999. Variational Constraints in 3D. Proc. Intl Conf on shape Modeling and Appl, Aizu, Japan, p.90-97.
[12]Durand, C. and Hoffmann, C.M., 2000. A systematic framework for solving geometric constraint analytically. J. of Symbolic Computing,30:483-520.
[13]Emiris, I.Z. and Verschelde, J., 1997. How to count efficiently all affine roots of a polynomial system. Discrete Applied Mathematics, 93(1).
[14]Fudos, I., 1993a. Editable Representations for 2D Geometric Design, Master's Thesis, Purdue University, Dept. of Computer Science.
[15]Fudos, I. and Hoffmann, C.M., 1993b. Correctness proof of a geometric constraint solver. Intl. J. Comp Geometry and Applic, 6: 405-420.
[16]Fudos, I. and Hoffmann, C.M., 1997. A graph-constructive approach to solving systems of geometric constraints. ACM Transactions on Graphics,16:179-216.
[17]Ge, J.X., Gao, X.S. and Chou, S.C., 2000. Geometric constraint satifaction using optimization methods. Computer Aided Design,31:867-879.
[18]Goldberg, D.E., 1989. Genetic Algorithms in Search, Optimization and Machine Learning. Addison Wesley Publishing Company, New York, p.1-88.
[19]Hoffmann, C.M. and Vermeer, P., 1995a. Geometric Constraint Solving in R2 and R3. In: Computing in Eulidean Geometry Second Edition. World Scientific Publishing, Singapore, p.266-298.
[20]Hoffmann, C.M. and Vermeer, P., 1995b. A Spatial Constraint Problem. In: Computational Kenematics's 95,J.P. Merlet and B.Ravani,Eds.,Kluwer Academic Publ.,p.83-92.
[21]Hoffmann, C.M. and Joan-arinyo, R., 1997. Symbolic constraints in constructive geometry. Journal of Symbolic Computation,23:287-300.
[22]Hoffmann, C.M. and Yuan, B., 2000. On Spatial Constraint Solving Approaches. Proc.ADG 2000, Springer verlag, ETH Zurich.
[23]Ivan, S.E., 1963. Sketchpad: A Man-Machine Graphical Communication System. In: Proceedings-Spring Joint Computer Conference, Michigan, 23:329-346.
[24]Joan-Arinyo, R. and Soto, A., 1997a. A correct rule-based geometric constraint solver. Computer and Graphics,21(5):599-609.
[25]Joan-Arinyo, R. and Soto, A., 1997b. A Ruler-and-Compass Geometric Constraint Solver. In: M.J., Pratt,R.D., Sriram and M.J., Wozny,editors,Product Modeling for Computer Integrated Design and Manufacture, Chapman and Hall,London, p.384-393.
[26]Kondo, K., 1992. Algebraic method for manipulation of dimensional relationships in geometric models. CAD,24(3):141-147.
[27]Kirkpatrick, S., Gelatt Jr., C.D. and Vecchi, M.P., 1983. Optimization by simulated annealing. Science, 220:671-680.
[28]Lazard, D., 1999. On theories of triangular sets. Journal of Symbolic Computation, 28:105-124.
[29]Michalewicz, Z., Krawczyk, J., Kazemi, M. and Janikow, C., 1990. Genetic Algorithms and Optimal Control Problem. In: Proc. of 29th IEEE Conf. On Decision and Control,p.1664-1666.
[30]Morgan, A., 1992. Polynomail Continuation and its Relatoinship to the Symbolic Reduction of Polynomial Systems. In: B.Donald,D.Kapur, and J.Mundy,editors,Symbolic and Numerical Computation for Artificial Inteligence. Academic Press.
[31]Song, P., Tang, M. and Dong, J.X., 2000. A Constraint Solving Approach Based on Graph Decomposition. China Graph'2000, Hangzhou.
[32]Sturmfels, B., 1997. Introduction to Resultants. Lecture Notes at the AMS Short Course on Applications of Computational Algebraic Geometry,San Diego.
[33]Verroust, A., Schonek, F. and Roller, D., 1992. Rule-oriented method for parametrized computer-aided design. Computer Aided Design,24(10):531-540.
[34]Wang, D., 1998. Decomposing polynomial systems into simple systems. Journal of Symbolic Computation,25:295-314.
[35]Wu, W.T., 1986. Principles of mechanical theorem proving. J. of Automated Reasoning,2:221-252.
Open peer comments: Debate/Discuss/Question/Opinion
<1>