| 【中文题名】 | 基于统计分析的矩形件排样问题遗传算法研究 |
| 【英文题名】 | A Study on Genetic Algorithm for Rectangular Packing Problem Based on Statistical Analysis |
| 【学科专业】 | 应用数学 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2006-7-17 |
| 【中关键词】 | 矩形件优化排样,组合优化,剩余矩形排样算法,单亲遗传算法,统计分析, |
| 【英关键词】 | rectangle packing problem,combination optimization,surplus rectangle fill algorithm,partheno-genetic algorithm,statistical analysis, |
| 【分类导航】 | 数理科学和化学>数学>运筹学>规划论（数学规划）>> |
| 【论文摘要】 | 二维矩形件优化排样问题通常是指在给定矩形板材上排放所需要的矩形件,使板材利用率最高。它属于典型的组合优化问题,已被证明是NP完备的,具有较高的计算复杂性。
本文在分析国内外研究现状以及原有遗传算法局限性的基础上,提出了一种基于统计分析的单亲遗传算法,用于求解矩形件优化排样问题。
首先,提出将剩余矩形排样算法与单亲遗传算法结合起来共同求解矩形件优化排样问题,有效地利用了两种算法的优势,通过实例验证表明,利用此方法所得结果在计算精度或运算时间方面优于目前常用算法。进一步,在上述算法基础上,针对矩形件排样问题本身特点,深入研究了矩形零件数量、大小差异、板材规格等与问题解空间的关系,发现了问题次优解空间所存在的统计规律性。并根据此规律,采用优势群体遍历搜索策略,设计基于统计分析的单亲遗传算法。经实例验证,该算法大大提高了寻找某一特定生产环境下的矩形件排样问题全局最优解的能力,充分表明了算法的有效性。 |
| 【论文题纲】 |
|
摘要 |
4-5 |
|
Abstract |
5-7 |
|
第一章 绪论 |
7-17 |
|
1.1 优化排样问题概述 |
7-11 |
|
1.2 矩形件优化排样问题国内外研究现状及存在的问题 |
11-14 |
|
1.3 研究的主要内容及创新点 |
14-17 |
|
第二章 矩形件优化排样问题 |
17-27 |
|
2.1 矩形件优化排样问题的数学模型 |
17-19 |
|
2.2 矩形件优化排样问题的特点及复杂性 |
19-20 |
|
2.3 常用的排样算法 |
20-26 |
|
2.4 本章小结 |
26-27 |
|
第三章 矩形件优化排样问题的单亲遗传算法求解 |
27-46 |
|
3.1 遗传算法概述 |
27-29 |
|
3.2 单亲遗传算法描述 |
29-32 |
|
3.3 单亲遗传算法的收敛性 |
32-36 |
|
3.4 基于剩余矩形排样法的矩形件排样问题的单亲遗传算法求解 |
36-40 |
|
3.5 实例分析 |
40-44 |
|
3.6 本章小结 |
44-46 |
|
第四章 基于统计分析的矩形件优化排样 |
46-65 |
|
4.1 统计分析思想概述 |
46-48 |
|
4.2 基于统计分析结果的改进单亲遗传算法 |
48-51 |
|
4.3 统计分析思想的逐步实现 |
51-59 |
|
4.4 基于统计分析的矩形件排样问题的单亲遗传算法求解 |
59 |
|
4.5 实例分析 |
59-64 |
|
4.6 本章小结 |
64-65 |
|
第五章 总结与展望 |
65-67 |
|
5.1 结论 |
65-66 |
|
5.2 未来研究方向展望 |
66-67 |
|
参考文献 |
67-71 |
|
致谢 |
71 |
|
| 【DOI】 | LunWen.ID:2.2008.14598 |
