矩形件下料优化排样的多群体杂交遗传算法

摘要

矩形件排样在工业上有广泛的应用，目标是使下料过程中的切割损失减少到最少，使得原材料的利用率最高。优化排样算法的研究既有实际应用价值，又有理论意义。 矩形排样问题属于组合最优化问题和NP完全问题，因为存在计算上的复杂性，在一定时间内求其精确全局最优解是相当困难的。对于矩形排样问题，任何算法都难以保证总能得到最优解，目前解决的方法多为各种启发式算法。 遗传算法是借鉴生物的自然选择和进化机制的一种全局优化自适应概率搜索算法，具有快速随机的全局搜索能力。对于非常复杂、高度非线性问题的优化求解，表现出比其它传统优化方法更优越的性能，是21世纪智能计算中的核心技术之一。 本文所做的主要工作如下： 第一章首先介绍了矩形件排样的相关知识及应用领域，分析了排样问题的研究现状，引出本文的研究目标和工作重点。 第二章对遗传算法进行了详细的介绍，包括遗传算法的特点，实现技术等。并结合矩形件排样优化，来介绍相应的遗传算法的编码方法、适应度函数、交叉方法，变异算子等。 第三章对几种矩形件优化排样算法进行了介绍，分析了它们的排样过程和各自的优缺点，并选择了“最低水平线算法”与遗传算法的复合算法来求解矩形件优化排样问题。 第四章是本文的重点。这章着重介绍了遗传算法的改进方面，这也是本文主要的研究点，先从理论上对最优个体保存策略全局收敛性进行证明，然后从理论上对单纯多种群遗传算法进行了证明，并详细介绍了本文的研究重点——使用多种群阶段性杂交算法对矩形件排样进行的搜索求解过程，并根据提出的算法，编写程序进行大量的数据测试，并与单种群遗传算法进行横向对比，测试数据表明了本文算法的有效性。 第五章总结了本文的工作并展望了今后在短形件优化排样的研究工作。

目录

文摘

英文文摘

声明

第一章绪论

1.1优化排样问题的总体描述

1.2优化排样问题的分类

1.3优化排样的意义

1.4优化排样问题的复杂性

1.5排样问题的国内外研究现状

1.6本文所做的工作

第二章遗传算法

2.1遗传算法的产生和发展

2.2基本遗传算法的实现

2.3基本遗传算法的特点

2.4遗传算法研究的进展

2.5基本遗传算法的改进

2.6矩形件排样遗传算法的基因编码

第三章矩形件优化排样算法分析

3.1矩形件优化排样问题简介

3.2矩形件排样的启发式算法

3.3适合遗传算法的给定排放顺序的排放算法

第四章基于矩形件排样的多群体阶段性杂交遗传算法

4.1标准遗传算法进行排样的效果及分析

4.2最优个体保存策略及变异算子的自适应性

4.3采用EGA的矩形件排样算法分析

4.4多群体遗传算法原理分析

4.5矩形件排样的多群体阶段性杂交遗传算法求解

4.6计算实例

第五章总结与展望

参考文献

致谢