吉林大学学报(工学版)

• • 上一篇    下一篇

几何约束多解问题

易荣庆,李文辉,袁华,王铎,郭武   

  1. 吉林大学 计算机科学与技术学院,长春 130012
  • 收稿日期:2007-03-06 修回日期:2007-08-10 出版日期:2008-07-01 发布日期:2008-07-01
  • 通讯作者: 李文辉

Multi-solutions problem in geometric constraint

YI Rong-qing, LI Wen-hui, YUAN Hua, WANG Duo, GUO Wu   

  1. College of Computer Science and Technology, Jilin University, Changchun 130012, China
  • Received:2007-03-06 Revised:2007-08-10 Online:2008-07-01 Published:2008-07-01
  • Contact: LI Wen-hui

摘要: 针对几何约束求解的多解性问题,将约束分成两个集合:原约束集合和增加的额外约束集合。用求解器求解出全部解后,利用提出的混合遗传蚂蚁算法,搜索全部解空间,在算法的初始阶段采用遗传算法,产生信息素的初始分布;在算法的后期采用蚂蚁算法。由于在遗传算法中使用随机的种群,不仅提高了蚂蚁算法的速度,而且在求解时能避免陷入局部最优解。通过启发式搜索算法使增加的额外约束得到最大化满足,从而寻找到符合用户意图的解。

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

Abstract: 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.

Key words: computer software, constraint solving, solution selection, ant algorithm

中图分类号: 

  • TP31
[1] 马健, 樊建平, 刘峰, 李红辉. 面向对象软件系统演化模型[J]. 吉林大学学报(工学版), 2018, 48(2): 545-550.
[2] 罗养霞, 郭晔. 基于数据依赖特征的软件识别[J]. 吉林大学学报(工学版), 2017, 47(6): 1894-1902.
[3] 李文辉, 孙明玉, 许光星, 曹春红. 基于二部图模型的欠、过约束几何约束系统的识别和处理[J]. 吉林大学学报(工学版), 2017, 47(5): 1583-1590.
[4] 李文辉, 孙明玉, 曹春红. 几何约束求解的扩展C-树分解法[J]. 吉林大学学报(工学版), 2017, 47(4): 1273-1279.
[5] 应欢, 王东辉, 武成岗, 王喆, 唐博文, 李建军. 适用于商用系统环境的低开销确定性重放技术[J]. 吉林大学学报(工学版), 2017, 47(1): 208-217.
[6] 李勇, 黄志球, 王勇, 房丙午. 基于多源数据的跨项目软件缺陷预测[J]. 吉林大学学报(工学版), 2016, 46(6): 2034-2041.
[7] 王念滨, 祝官文, 周连科, 王红卫. 支持高效路径查询的数据空间索引方法[J]. 吉林大学学报(工学版), 2016, 46(3): 911-916.
[8] 特日跟, 江晟, 李雄飞, 李军. 基于整数数据的文档压缩编码方案[J]. 吉林大学学报(工学版), 2016, 46(1): 228-234.
[9] 康辉, 王家琦, 梅芳. 基于Pi演算的并行编程语言[J]. 吉林大学学报(工学版), 2016, 46(1): 235-241.
[10] 陈鹏飞, 田地, 杨光. 基于MVC架构的LIBS软件设计与实现[J]. 吉林大学学报(工学版), 2016, 46(1): 242-245.
[11] 刘磊, 王燕燕, 申春, 李玉祥, 刘雷. Bellman-Ford算法性能可移植的GPU并行优化[J]. 吉林大学学报(工学版), 2015, 45(5): 1559-1564.
[12] 冯晓宁, 王卓, 张旭. 基于L-π演算的WSN路由协议形式化方法[J]. 吉林大学学报(工学版), 2015, 45(5): 1565-1571.
[13] 李明哲, 王劲林, 陈晓, 陈君. 基于网络处理器的流媒体应用架构模型(VPL)[J]. 吉林大学学报(工学版), 2015, 45(5): 1572-1580.
[14] 王克朝, 王甜甜, 苏小红, 马培军. 基于频繁闭合序列模式挖掘的学生程序雷同检测[J]. 吉林大学学报(工学版), 2015, 45(4): 1260-1265.
[15] 黄宏涛,王静,叶海智,黄少滨. 基于惰性切片的线性时态逻辑性质验证[J]. 吉林大学学报(工学版), 2015, 45(1): 245-251.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!