船舶板材规则件套料优化设计方法研究

摘要

船舶板材套料过程需要处理大小不一，形状各异的板材零件，存在着大量的工作量。而合理的板材排样方案直接影响了生产过程的经济效益。船舶板材套料优化设计的目的是为了提高船舶板材的利用率。船舶板材套料问题，按研究对象的不同，可分为规则件排样问题和不规则件排样问题。本文主要对船舶板材件中的规则件（矩形零件和直角三角形零件）进行排样优化。因为直角三角形零件又可以通过组合的方式转换为矩形零件。因此本文中的船舶板材套料优化设计是将大小不一，数量不同的船舶矩形板材零件，在一定的约束条件下合理排放，以达到板材利用率的最大化。 首先，针对船舶板材套料问题，本文在研究总结了相关矩形件排样优化问题及现有的排样算法基础上，提出了解决矩形件排样的最大剩余矩形算法。在该算法的框架下，设计实现了五种不同的启发式策略，来有效引导矩形件的排样，提高算法的适应能力。在此基础上，将排样源从单一矩形扩展到矩形和直角三角形，嵌入直角三角形的排样算法，并完成CAD宏命令出图编撰。同时选取合适的测试样本，通过测试结果证明，该算法能够给出令人满意的排样结果。 其次，考虑到算法在全局范围内搜索的不足，在分析总结现有智能算法的前提下，引入基本遗传算法。首先确定了先启发式搜索后遗传算法优化的总体算法框架，接着确定遗传算法中的重要参数。同时选取了十组具有代表性的测试数据进行算法嵌入前后的对比，得到的计算结果表明，遗传算法的嵌入在最大剩余矩形算法启发式搜索结果较优的基础上，可进一步提升板材排样利用率。 最后，对基本遗传算法进行改进，提升遗传算法模块的效率。针对遗传算法的三个重要操作过程，引入小生境遗传策略来提高选择过程的高效性，以及自适应概率策略来提升交叉过程和变异过程的合理性。通过相同的测试数据，得出的排样结果证明，改进后的算法整体表现出更优秀的最优解搜索质量以及更强的全局搜索能力。 本文提出的板材排样算法通过排样结果的对比证明了相较于现有的相关排样算法的优越性。在一定程度上减少了船舶生产过程中，板材排样的生产工作，同时提高了船舶板材的利用率。

目录

声明

1 绪论

1.1 问题的提出

1.2 国内外研究现状

1.3 本文研究内容

1.4 创新点论述

1.5 本章小结

2 矩形排样模型和算法分析

2.1 矩形排样模型

2.1.1 问题描述

2.1.2 数学模型

2.2 常用优化算法

2.2.1 枚举法

2.2.2 贪心算法

2.2.3 模拟退火算法

2.2.4 遗传算法

2.2.5 蚁群算法

2.2.6 启发式算法

2.3 现有算法的总结

2.4 本章小结

3 基于五种启发式策略的最大剩余矩形算法

3.1 最大剩余矩形算法

3.1.1 基本原理

3.1.2 空白链表更新除冗

3.2 最大剩余矩形算法结构

3.2.1 数据存储结构

3.2.2 算法实现流程

3.3 三角形零件在最大剩余矩形算法中的嵌入

3.3.1 基本原理

3.3.2 嵌入流程图

3.4 CAD宏命令出图

3.5 五种启发式策略的提出

3.5.1 基于BOTTOM-LEFT原则的最大剩余矩形算法

3.5.2 基于最小面积原则的最大剩余矩形算法

3.5.3 基于最小短边原则的最大剩余矩形算法

3.5.4 基于最小长边原则的最大剩余矩形算法

3.5.5 基于最大接触周长原则的最大剩余矩形算法

3.6 最优结果输出

3.7 计算实例

3.8 本章小结

4 结合遗传算法的最大剩余矩形算法再优化

4.1 遗传算法的简介及最优个体保留策略

4.2 遗传算法在矩形排样中的具体应用

4.2.1 基因编码

4.2.2 初始化种群

4.2.3 染色体选择

4.2.4 染色体交叉

4.2.5 染色体变异

4.2.6 适应度函数

4.2.7 结合最大剩余矩形算法的遗传算法流程图

4.3 计算实例

4.4 本章小结

5 改进遗传算法的最大剩余矩形算法

5.1 遗传算法的改进

5.1.1 小生境遗传

5.1.2 自适应概率遗传

5.2 综合算法流程图

5.3 计算实例

5.4 本章小结

6 结论与展望

6.1 结论

6.2 展望

参考文献

攻读硕士学位期间发表学术论文情况

致谢

大连理工大学学位论文版权使用授权书