| 【中文题名】 | 基于遗传模拟退火算法的二维不规则多边形排样问题 |
| 【英文题名】 | |
| 【学科专业】 | 计算数学 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-5-23 |
| 【中关键词】 | 不规则样件,排样,启发式算法,遗传模拟退火算法,, |
| 【英关键词】 | Irregular shapes,optimal layout,Heuristic algorithm,Genetic simulated annealing algorithm, |
| 【分类导航】 | 工业技术>自动化技术、计算机技术>自动化基础理论>人工智能理论>> |
| 【论文摘要】 | 计算机辅助优化排样问题就是将一系列形状各异的零件排放在给定的材料上，找出零件的最优排布，使得给定材料的利用率最高，以达到节约材料，提高效益的目的。从数学计算复杂性理论看，二维不规则样件的排样问题在理论上属于NP完全问题，因为存在实际形状的复杂性和计算上的复杂性，求解十分困难。传统的排样工作都是人工依靠经验进行的，时间长并且效果不理想。由于生产实际的需要，人们迫切需要利用现代科技来解决这一问题。目前研究较多的是规则零件(如矩形)的排样问题，对不规则件的研究较少。
本文系统介绍了一种在基于遗传模拟退火算法的前提下，对不规则零件进行直接处理的方法，该方法在通过遗传算法模拟退火算法在空间上搜索优化的排布样件序列。对于每一个待排序列应用启发式定位算法确定其布局，并根据个体适应度评价函数对其布局进行评价，保证在进化过程中良好的排布序列可以保存下来。
在分析现有的不规则多边形启发式定位算法的基础之上，本文提出了一种基于平行梯形分割的启发式定位算法，该方法能直接实现不规则多边形的精确定位，并且具有很好的运算效率，这些优越的性能是现有方法所不具有的：对于遗传模拟退火算法，本文根据实际的问题需要确定了... |
| 【论文题纲】 |
|
摘要 |
3-4 |
|
Abstract |
4-7 |
|
第一章 绪论 |
7-13 |
|
1.1 引言 |
7 |
|
1.2 排样问题的研究背景和意义 |
7-8 |
|
1.3 优化排样问题的研究现状 |
8-11 |
|
1.4 本文的主要内容及安排 |
11-13 |
|
第二章 优化排样问题简介 |
13-21 |
|
2.1 排样问题分类 |
13-14 |
|
2.2 优化排样问题相关算法 |
14-18 |
|
2.3 排样问题的技术难点 |
18-19 |
|
2.4 排样问题的发展趋势 |
19-21 |
|
第三章 遗传算法和模拟退火算法 |
21-31 |
|
3.1 遗传算法 |
21-23 |
|
3.1.1 遗传算法基本操作 |
21-22 |
|
3.1.2 遗传算法的步骤 |
22 |
|
3.1.3 遗传算法的特点和不足 |
22-23 |
|
3.2 模拟退火算法 |
23-26 |
|
3.2.1 模拟退火算法的原理 |
23-25 |
|
3.2.2 模拟退火算法的步骤 |
25 |
|
3.2.3 模拟退火算法的特点和不足 |
25-26 |
|
3.3 遗传模拟退火算法 |
26-28 |
|
3.3.1 遗传模拟退火算法简介 |
26-27 |
|
3.3.2 遗传模拟退火算法的特点 |
27-28 |
|
3.4 算法的并行实现 |
28-31 |
|
第四章 二维不规则多边形的启发式定位算法 |
31-44 |
|
4.1 引言 |
31-32 |
|
4.2 启发式算法简介 |
32-33 |
|
4.3 BL算法及其改进 |
33-34 |
|
4.4 等间距扫描法 |
34-37 |
|
4.4.1 排样对象等间距扫描的几何表达 |
34-35 |
|
4.4.2 基于等间距扫描的启发式定位算法 |
35-36 |
|
4.4.3 等间距扫描算法的优缺点分析 |
36-37 |
|
4.5 多边形的平行梯形分割法 |
37-42 |
|
4.5.1 排样对象平行梯形分割的几何表达 |
37-38 |
|
4.5.2 基于平行梯形分割的启发式定位算法 |
38-40 |
|
4.5.3 样件上移距离的计算方法 |
40-41 |
|
4.5.4 平行梯形分割算法的优缺点分析 |
41-42 |
|
4.6 实例分析 |
42-44 |
|
第五章 遗传模拟退火算法在二维不规则排样中的应用 |
44-53 |
|
5.1 引言 |
44 |
|
5.2 基于遗传模拟退火的启发式排样算法 |
44-51 |
|
5.2.1 染色体编码 |
44-46 |
|
5.2.2 个体适应度评价 |
46-47 |
|
5.2.3 参数的选择 |
47 |
|
5.2.4 交叉运算 |
47-49 |
|
5.2.5 变异运算 |
49 |
|
5.2.6 模拟退火 |
49-50 |
|
5.2.7 终止条件 |
50 |
|
5.2.8 算法的总体步骤 |
50-51 |
|
5.3 工程应用实例 |
51-53 |
|
5.3.1 问题描述 |
51 |
|
5.3.2 应用效果 |
51-53 |
|
第六章 总结和展望 |
53-55 |
|
6.1 本文总结 |
53 |
|
6.2 进一步研究工作展望 |
53-55 |
|
参考文献 |
55-60 |
|
硕士期间发表的论文及科研项目 |
60-61 |
|
致谢 |
61-62 |
|
| 【DOI】 | LunWen.ID:2.2008.388529 |
