几何约束多解问题  

Multi-solutions problem in geometric constraint

作　　者：易荣庆[1] 李文辉[1] 袁华[1] 王铎[1] 郭武[1] 

机构地区：[1]吉林大学计算机科学与技术学院,长春130012

出　　处：《吉林大学学报（工学版）》2008年第4期871-875,共5页Journal of Jilin University:Engineering and Technology Edition

基　　金：国家自然科学基金项目(60573182);吉林省科技发展计划项目(20060527;20040531);高等学校博士学科点专项科研基金项目(20060183042)

摘　　要：针对几何约束求解的多解性问题,将约束分成两个集合:原约束集合和增加的额外约束集合。用求解器求解出全部解后,利用提出的混合遗传蚂蚁算法,搜索全部解空间,在算法的初始阶段采用遗传算法,产生信息素的初始分布;在算法的后期采用蚂蚁算法。由于在遗传算法中使用随机的种群,不仅提高了蚂蚁算法的速度,而且在求解时能避免陷入局部最优解。通过启发式搜索算法使增加的额外约束得到最大化满足,从而寻找到符合用户意图的解。To solve the constraint multi-solution problem, the constraints are separated to two sets, the original constraint set and the additional constraint set. First, the solver finds out multiple solutions. Then genetic algorithm and ant algorithm are combined in the process of searching optimal solution. We adopt genetic algorithm in the former process to produce the initiatory distribution of information elements, and then ant algorithm in the latter process. The random colony is adopted in genetic algorithm, which can not only accelerate the convergence process of ant algorithm but also avoid the local best solution. The heuristic searching algorithm maximizes the fitness of the additional constraint set, thereby reaches the final result that can satisfy the user＇s expectation.

关 键 词：计算机软件 几何约束求解 解的选择 蚂蚁算法 

分 类 号：TP31[自动化与计算机技术—计算机软件与理论]