| 【中文题名】 | 基于遗传算法的二维不规则图形排料问题的研究与应用 |
| 【英文题名】 | Research and Application of Two-dimensional Irregular Packing Problem Based on Genetic Algorithm |
| 【学科专业】 | 计算机应用技术 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-9-27 |
| 【中关键词】 | 排料,遗传算法,临界多边形,凸包,NP完全问题, |
| 【英关键词】 | Nesting,Genetic Algorithm,No-fit Polygon（NFP）,Convexhull,NP Complete Problem, |
| 【分类导航】 | 工业技术>自动化技术、计算机技术>计算技术、计算机技术>计算机的应用>信息处理(信息加工)>模式识别与装置 |
| 【论文摘要】 |
排料问题应用范围非常广泛，如服装行业、皮革行业、机械行业。提高板材利用率能降低企业的生产成本，会给企业带来经济效益，所以，排料问题的研究具有重要的经济价值。二维不规则排料问题具有很高的复杂性，属于NP完全问题，即不能在多项式时间内找到问题的最优解，所以，排料问题的研究具有重要的理论价值。
遗传算法(GA)是一种全局优化的现代启发式算法，通过交叉、变异来避免陷入局部极小。与传统优化方法相比，遗传算法仅仅利用个体的适应度进行群体的进化，不需要优化模型中目标函数和约束函数的导数信息，因而具有极强的鲁棒性，适合于解决各种优化问题。本文从遗传算法的产生背景、基本思想以及收敛性理论方面进行了细致的说明。
本文将遗传算法应用到二维不规则排料领域中，得到了很好的效果。出于对带圆弧图形的考虑，本文应用了自动提取零件数据的算法和求解逼近多边形的方法。
在自动排料计算的过程中，如何找到零件之间在什么位置靠接紧密并且不重叠是一个关键的问题。为了减少多边形之间重叠性判断的计算量，提高算法效率，在本文中采用了临界多边形算法，并对现有的临界多边形算法进行了改进，主要是针对两个凹多边形临界多边形的改进，首先... |
| 【论文题纲】 |
|
摘要 |
5-6 |
|
Abstract |
6-10 |
|
1 绪论 |
10-17 |
|
1.1 研究背景及意义 |
10-11 |
|
1.2 排料问题的分类 |
11-13 |
|
1.3 国内外研究现状 |
13-15 |
|
1.4 二维不规则排料问题分析 |
15-16 |
|
1.5 本文研究重点 |
16-17 |
|
2 遗传算法 |
17-27 |
|
2.1 遗传算法的产生背景与发展历史 |
17-20 |
|
2.2 遗传算法的基本思想 |
20-21 |
|
2.3 遗传算法的收敛性分析 |
21-25 |
|
2.4 遗传算法的应用情况 |
25-27 |
|
3 系统总体设计 |
27-35 |
|
3.1 系统功能设计 |
27-28 |
|
3.2 自动排料主要算法 |
28-30 |
|
3.3 零件的文件结构 |
30-31 |
|
3.4 系统类设计 |
31-33 |
|
3.5 带圆弧的多边形以及加工余量处理 |
33 |
|
3.6 系统的开发环境及工具 |
33-35 |
|
3.6.1 软件开发环境 |
33 |
|
3.6.2 系统开发工具 |
33-35 |
|
4 遗传算法求解不规则排料问题 |
35-41 |
|
4.1 染色体编码方法 |
35 |
|
4.2 目标函数和适应度函数 |
35 |
|
4.3 遗传算子的选用 |
35-39 |
|
4.3.1 选择算子 |
35-36 |
|
4.3.2 交叉算子 |
36-37 |
|
4.3.3 变异算子 |
37-39 |
|
4.4 遗传算法的运行参数及解码过程 |
39-41 |
|
5 二维不规则图形排料主要算法 |
41-62 |
|
5.1 任意多边形面积 |
41 |
|
5.2 多边形顶点凹凸性判断 |
41-45 |
|
5.3 凸包算法 |
45-47 |
|
5.4 合成多边形算法 |
47-48 |
|
5.5 矢量边角度求解 |
48 |
|
5.6 改进的临界多边形算法 |
48-61 |
|
5.6.1 临界多边形的概念 |
49-51 |
|
5.6.2 Minkowski sum的定义以及它与临界多边形的关系 |
51 |
|
5.6.3 两个凸多边形的临界多边形 |
51 |
|
5.6.4 凹多边形和凸多边形的临界多边形 |
51-56 |
|
5.6.5 两个凹多边形的临界多边形 |
56-61 |
|
5.7 多张板材排料 |
61-62 |
|
6 基于遗传算法的二维不规则排料系统 |
62-66 |
|
6.1 排料系统简介 |
62 |
|
6.2 排料实例 |
62-66 |
|
7 结论 |
66-67 |
|
参考文献 |
67-71 |
|
在学研究成果 |
71-72 |
|
致谢 |
72 |
|
| 【DOI】 | LunWen.ID:2.2008.388870 |
