基于遗传模拟退火算法的约束求解研究

摘要

参数化设计是现代CAD技术的一个极为重要的组成部分，它的基础是几何图形的多约束条件的求解。几何约束求解技术的好坏和成熟与否是衡量一个基于约束的参数化设计系统的优良的关键。
　　 本文首先回顾了CAD技术发展的历史，分析了国内外一些典型的参数化技术和约束求解技术，熟悉现行的参数化系统和参数化设计的主要实现方法。指出约束求解是参数化技术的关键所在。
　　 接着深入分析了约束及约束求解的相关概念，剖析了约束求解中包含的元素，分析约束求解的核心所在。对目前流行的四种约束求解方案进行对比分析，探讨了其可行性及不足。
　　 然后根据约束求解中在过约束、欠约束、多解时存在的问题，采用了具有全局搜索能力的遗传算法和局部最优性的模拟退火算法相结合的思路，提出遗传模拟退火混合算法来进行几何约束求解。由于将约束问题首先转化为优化问题的过程中，并没有要求约束变量的数目与约束的数目相等，因此可以自然地求解欠约束问题和过约束问题。因为遗传模拟退火算法本身具有很多优点：很强的计算鲁棒性、隐含的内在并行性、全局搜索与局部快速收敛能力，所以将遗传模拟退火算法与约束求解相结合大大提高了约束求解的鲁棒性和效率。由于遗传模拟退火算法不涉及到矩阵求逆和对方程的求偏导等运算，因此文中将约束方程组转化为优化模型时，将方程的绝对值简单相加得到优化模型，而大多数优化算法中都是利用约束方程组平方相加得到优化模型，与这些约束模型相比，文中的约束模型更加简单，并且使得计算量大大减少。仿真实验结果表明，该算法具有良好的有效性和可行性。
　　 最后以算法设计为主线，在’Visual Studio2005开发环境下，以面向对象思想，结合C++语言对算法进行实现，验证了算法的正确性及可行性。实验证明，该算法能很好地解决良约束、过约束和欠约束的问题。它改变了传统遗传算法易早熟，局部寻优能力差的缺点；弥补了模拟退火算法全局搜索能力差的不足；大大提高了算法的效率。

目录

文摘

英文文摘

插图索引

附表索引

第1章 绪论

1.1 课题背景

1.2 CAD技术现状及发展方向

1.3 参数化技术与约束求解

1.4 国内外研究现状

1.5 主要工作内容和意义

1.6 本文的组织结构

第2章 参数化技术研究

2.1 参数化设计思想的提出

2.2 参数化理论概述

2.2.1 常用术语

2.2.2 参数化设计

2.3 参数化设计方法分类

2.3.1 程序参数化

2.3.2 交互式参数化

2.3.3 离线式参数化

2.4 参数化设计的主要实现方法

2.5 小结

第3章 约束与约束求解

3.1 约束的概念和类型

3.2 几何元素

3.3 几何约束的类型和约束度

3.4 几何约束求解技术综述

3.4.1 数值方法

3.4.2 符号方法

3.4.3 规则方法

3.4.4 图论方法

3.4.5 几何约束求解中的常见问题

3.5 小结

第4章 关键技术研究

4.1 遗传算法

4.1.1 遗传算法

4.1.2 遗传算法的思想

4.1.3 遗传算法的特点

4.2 遗传模拟退火混合算法

4.2.1 模拟退火算法

4.2.2 遗传模拟退火混合算法

4.3 基于遗传模拟退火混合算法的约束求解

4.3.1 数学模型

4.3.2 编码与解码方法

4.3.3 运行参数

4.3.4 中止条件

4.3.5 算法调试与算子选择

4.4 遗传模拟退火混合算法的实例分析

4.4.1 良约束情形

4.4.2 欠约束情形

4.4.3 过约束情形

4.5 小结

第5章 关键技术的实现

5.1 约束求解流程图

5.2 系统开发环境

5.2.1 操作系统

5.2.2 开发语言的选择

5.3 元素类和约束类

5.4 图形元素输入

5.5 小结

结论

参考文献

附录A 攻读学位期间所发表的学术论文目录

致谢