| 【中文题名】 | 矩形件下料优化排样的遗传算法 |
| 【英文题名】 | Optimizing Cutting Pattern in Rectangular Packing Problem by Genetic Algorithm |
| 【学科专业】 | 计算机软件与理论 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2005-11-4 |
| 【中关键词】 | 优化排样,矩形件,遗传算法,下料问题,组合优化,启发式算法 |
| 【英关键词】 | Optimizing Nesting,Rectangle Part,Genetic Algorithm,Cutting Stock Problem,Combinatorial Optimization,Heuristic algorithm, |
| 【分类导航】 | 工业技术>自动化技术、计算机技术>自动化基础理论>人工智能理论>> |
| 【论文摘要】 | 随着中国加入WTO,制造行业的企业面临着更为激烈的市场竞争。为了在竞争中立于不败之地,企业必须想方设法提高经济效益,而提高经济效益的重要途径之一就是通过提高材料的利用率来降低成本。
矩形件排样在工业上有广泛的应用,目标是使下料过程中的切割损失减少到最少,使得原材料的利用率最高。优化排样算法的研究既有实际应用价值,又有理论意义。
矩形排样问题属于组合最优化问题和NP完全问题,因为存在计算上的复杂性,在一定时间内求其精确全局最优解是相当困难的。对于矩形排样问题,任何算法都难以保证总能得到最优解,目前解决的方法多为各种启发式算法。
提高原材料利用率问题是一个系统工程问题,需要从生产管理、优化下料、支持决策等方面提供完备的一体化解决方案。其中优化下料环节中,构造有效的优化算法是关键。
矩形件排样不仅适用于矩形零件的排放,而且也是不规则零件排放的基础。本文研究的问题是无约束非剪切单一卷材矩形件的优化下料,其中卷材为定宽无限长,要排放的矩形件数量和规格都是已知的,要求在排放完所有给定矩形件的前提下使所消耗的卷材长度最小。
遗传算法是借鉴生物的自然选择和进化机制的一种全局优化自适应概率搜索算法,具有快速... |
| 【论文题纲】 |
|
摘要 |
2-4 |
|
Abstract |
4-8 |
|
第一章 绪论 |
8-14 |
|
1.1 计算机辅助优化排样简介 |
8-9 |
|
1.2 排样问题的分类 |
9-10 |
|
1.3 排样问题的国内外研究现状 |
10-11 |
|
1.4 算法复杂性理论简介 |
11 |
|
1.5 常见优化算法 |
11-12 |
|
1.6 选题背景及意义 |
12-13 |
|
1.7 本文的研究内容及所做的工作 |
13-14 |
|
第二章 遗传算法 |
14-27 |
|
2.1 引言 |
14-15 |
|
2.2 基本遗传算法的实现技术 |
15-16 |
|
2.3 基本遗传算法的特点 |
16-17 |
|
2.4 遗传算法研究的进展 |
17-20 |
|
2.4.1 启发式搜索法 |
17-18 |
|
2.4.2 混合遗传算法 |
18-19 |
|
2.4.3 基本遗传算法的改进 |
19-20 |
|
2.5 矩形件优化排样的遗传算法设计 |
20-27 |
|
2.5.1 基因编码 |
20-21 |
|
2.5.2 初始种群的产生 |
21-22 |
|
2.5.3 染色体的交叉 |
22-23 |
|
2.5.4 染色体的变异 |
23-24 |
|
2.5.5 适应度函数 |
24-25 |
|
2.5.6 染色体的选择 |
25-27 |
|
第三章 矩形件优化排样算法分析 |
27-42 |
|
3.1 矩形件优化排样问题简介 |
27-29 |
|
3.1.1 矩形件排样的形式化描叙 |
27-28 |
|
3.1.2 矩形件的切割方式 |
28-29 |
|
3.2 排样问题的复杂性理论 |
29-30 |
|
3.3 矩形件排放的定序规则 |
30-31 |
|
3.4 矩形件排样的启发式算法 |
31-34 |
|
3.4.1 BFDH 算法 |
32 |
|
3.4.2 堆栈算法 |
32-33 |
|
3.4.3 组合算法 |
33-34 |
|
3.5 给定排放顺序的排放算法 |
34-42 |
|
3.5.1 BL算法 |
34-35 |
|
3.5.2 DP算法 |
35-37 |
|
3.5.3 下台阶算法 |
37-38 |
|
3.5.4 最低水平线法 |
38-39 |
|
3.5.5 基于最低水平线的搜索算法 |
39-42 |
|
第四章 基于最低水平线的空闲区域可再利用搜索算法 |
42-61 |
|
4.1 引言 |
42-44 |
|
4.2 改进算法的基本思想 |
44-46 |
|
4.3 基于最低水平线的空闲区域可再利用搜索算法 |
46-51 |
|
4.3.1 空闲区域填充的必要性 |
46 |
|
4.3.2 实现空闲区域填充的关键技术 |
46-49 |
|
4.3.2.1 空闲矩形位置的记录 |
46-47 |
|
4.3.2.2 空闲矩形相邻的判断 |
47-48 |
|
4.3.2.3 相邻空闲矩形的合并 |
48-49 |
|
4.3.3 算法的具体步骤 |
49-51 |
|
4.4 计算实例 |
51-61 |
|
第五章 总结与展望 |
61-62 |
|
参考文献 |
62-65 |
|
攻读硕士学位期间发表的论文 |
65-66 |
|
致谢 |
66 |
|
| 【DOI】 | LunWen.ID:2.2008.387502 |
