遗传模拟退火算法在约束求解中的应用  

Geometric Constraint Satisfaction Using Genetic Simulated Annealing Algorithm

作　　者：刘生礼[1] 唐敏[1] 董金祥[1] 

机构地区：[1]浙江大学人工智能研究所CAD/CG国家重点实验室,杭州310027

出　　处：《中国图象图形学报（A辑）》2003年第8期938-945,共8页Journal of Image and Graphics

基　　金：浙江省自然科学基金项目 (60 0 110 7);国家教育部博士点基金项目 (2 0 0 0 0 3 3 5 5 4)

摘　　要：将遗传模拟退火算法应用于约束求解中 ,提高了约束系统求解的鲁棒性和效率 .与 Newton- Raphson数值方法相比 ,由于遗传模拟退火算法是一种单纯的数值迭代方法 ,不涉及到矩阵求逆 ,因此克服了 Newton- Raphson法对初始值敏感的缺点 ,具有很强的鲁棒性 ;与其他利用 BFGS的优化算法相比 ,由于遗传模拟退火算法是在一个初始的解空间中搜索所有可能的解 ,因此克服了 BFGS优化算法对良约束多解情况只能求出一个解的缺点 ;由于遗传模拟退火算法是将约束问题转化为优化问题后才进一步求解 。This paper applies genetic simulated annealing algorithm (SAGA) to solving the geometric constraint problems. Genetic simulated annealing algorithm itself has many merits, such as implicit parallelism, stability of numerical computation and the global searching ability together with the local fast converging ability, etc. This paper takes the special characters of constraint solving into consideration and integrates the SAGA well with it. After the geometry constraint problem is transformed into the optimal one, it is solved by SAGA that making full use of the advantages of SAGA. This approach can deal with the over-/under-constraint problems because of this conversion. It also 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 BFGS(Broyder\|Fletcher\|Goldfard\|Shanno) for multi-solution constraint system. Our experiments have proved the robustn.

关 键 词：遗传模拟退火算法 几何约束求解 鲁棒性 良约束 过约束 约束不足 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术] TP183[自动化与计算机技术—计算机科学与技术]