基于差分进化和自适应遗传算法的矩形件排样方法研究

摘要

矩形件排样问题广泛存在于如板材加工、航空航天、机械制造、玻璃制造、大规模集成电路、纺织服装等工业设计中，该问题通常有两种情形:一种是在长度和宽度均已确定的矩形板材上排放矩形件，另一种是在定宽不限长的矩形板材上排放矩形件。待排矩形件的尺寸大小及数量有一定的限制，且矩形件在板材上排放时有如下约束:各矩形件间不能相互重叠、所排入的矩形件不能超出板材边界，最终目标是使得矩形板材利用率最大化。矩形件排样的效果直接影响到企业生产的经济效益。然而矩形件排样问题已被证明属于NP完全问题，无法直接计算得到其最优解，目前该问题仍然是国内外研究的一个热点。
　　本文所针对的矩形件排样问题为第二种情形，即在定宽不限长的矩形板材上排放矩形件，在服装、玻璃、皮革、家具等现代工业的生产中均会遇到类似的问题:所需要的板材长度并非确定，必须将所有矩形件全部排放完毕得到对应的排样高度，才能确定所需的板材长度。本文所针对的问题对现代生产中的诸多行业均具有应用价值。
　　针对矩形件排样问题，首先本文运用两种优化算法对排样序列进行求解:一种是自适应遗传算法，通过在进化过程中对交叉概率和变异概率进行自适应非线性调整，并在进化过程的初始种群产生、选择、交叉和变异等环节采用性能较优的算子来实现，以寻找最优排样序列;另一种是离散差分遗传算法，该混合优化算法通过融合差分进化算法和遗传算法各自的优点提高算法的性能。其次，分别设计了多条带策略和集中剩余矩形区域策略作为排样算法中解码方法。最后，采用C#在VS2010编程平台上对所提出的算法加以实现并结合实验案例验证算法的有效性，通过对实验结果的分析与现有方法进行对比，表明将本文所提方法应用于求解矩形件排样问题能获得较高的板材利用率，验证了方法的有效性和合理性，对现代工业生产具有重要的现实意义。

目录

声明

摘要

第一章 绪论

1．1 排样问题的提出

1．2 矩形件排样问题的研究现状

1．2．1 国外研究现状

1．2．2 国内研究现状

1．3 文献综述

1．3．1 矩形件排样优化问题的相关理论及算法

1．3．2 用于解决矩形件排样问题的遗传算法和差分进化算法

1．4 论文创新点

1．5 论文结构

第二章 自适应遗传算法和差分进化算法

2．1 自适应遗传算法

2．1．1 自适应遗传算法的产生及原理

2．1．2 自适应遗传算法的特点

2．1．3 自适应遗传算法的改进

2．1．4 自适应遗传算法的操作流程

2．1．5 自适应遗传算法在本文中的应用

2．2 差分进化算法

2．2．1 差分进化算法的产生及原理

2．2．2 差分进化算法的特点

2．2．3 差分进化算法的改进

2．2．4 差分进化算法的基本步骤

2．2．5 差分进化算法在本文中的应用

2．3 本章小结

第三章 多条带策略及其在矩形件排样问题中的应用

3．1 多条带策略

3．1．1 多条带策略排样方法

3．1．2 多条带策略下的矩形件排样过程

3．2 实验案例与分析

3．3 本章小结

第四章 集中剩余矩形区域策略及其在矩形件排样问题中的应用

4．1 集中剩余矩形区域策略

4．1．1 集中剩余矩形区域策略

4．1．2 集中剩余矩形区域策略下的解码流程

4．2 实验案例与分析

4．3 本章小结

第五章 矩形件排样问题的离散差分遗传算法求解

5．1 离散差分遗传算法的提出

5．2 运用离散差分遗传算法进行排样的流程

5．3 离散差分遗传算法的具体操作

5．3．1 初始种群的编码及产生

5．3．2 适应度值计算

5．3．3 交叉和变异

5．3．4 解码方法

5．4 实验案例与分析

5．5 本章小结

第六章 总结和展望

6．1 全文工作总结

6．2 今后研究展望

参考文献

致谢

攻读硕士学位期间发表的论文及参与的科研项目