融合蚁群算法和遗传算法的矩形件排样问题研究

论文摘要

矩形件排样是指将若干尺寸相同或不相同的矩形零件在给定的矩形板材上以最优的方式排布。矩形件排样问题普遍存在于工程领域中,如钣金下料、玻璃切割、造船、车辆、家具生产、报刊排版、服装和皮革裁剪等。较好的排样方案可以最大限度地节约原材料,提高原材料利用率,从而降低生产成本,在经济上制造可观的效益。在理论上,矩形件排样问题属于组合最优化问题和具有最高计算复杂性的NP完全问题。用现在常用的计算理论和方法很难精确地求得问题的最优解,只能在一定的时间范围内求其局部最优的近似解。启发式智能优化方法是近年发展起来的非常活跃的研究领域,如遗传算法、模拟退火算法、蚁群算法、神经刚络、粒子群算法等,它们都可以有效的解决组合优化和NP类问题。本文是在介绍了遗传算法和蚁群算法各自特点的基础上,提出将两种算法相融合来求解矩形件排样问题。融合算法的前阶段采用遗传算法,充分利用遗传算法的快速随机性、全局收敛性的优点,获得排样序列的部分优化解,并以此作为下阶段蚁群算法的初始信息素分布；融合算法后阶段采用蚁群算法,利用其优良的正反馈机制和高效收敛性的优点,精确求得最优排样序列。此外,本文在建立矩形件排样问题数学模型的基础上,分析了常见的矩形件给定排放顺序的排放算法的优缺点,提出了一种改进的排放算法。该算法充分考虑矩形件长度和宽度对排样效果的影响,加入了旋转策略,并改进了搜索策略。将此改进算法分别与遗传算法和融合算法结合求解矩形件排样问题,计算实例表明了该改进排放算法更为有效,并能够和融合算法较好的结合,得到更好的排样效果。

论文目录

• 摘要
• Abstract
• 目录
• 1 绪论
• 1.1 排样问题研究的目的与意义
• 1.2 排样问题的分类
• 1.3 排样问题的国内外研究现状
• 1.3.1 国外研究现状
• 1.3.2 国内研究现状
• 1.4 本文的主要研究工作
• 2 矩形件排样问题的数学模型及排放算法的改进研究
• 2.1 矩形件排样问题的数学模型
• 2.1.1 矩形件排样问题的描述
• 2.1.2 数学模型
• 2.2 矩形件排样的定序规则
• 2.3 矩形件排样给定排放顺序的排放算法
• 2.3.1 BL算法
• 2.3.2 下台阶算法
• 2.3.3 最低水平线算法
• 2.3.4 基于最低水平线的搜索算法
• 2.3.5 本文提出的改进排放算法
• 2.4 本章小结
• 3 基于遗传算法的矩形件排样
• 3.1 遗传算法概述
• 3.2 遗传算法的特点
• 3.3 遗传算法的实现技术
• 3.3.1 编码
• 3.3.2 种群的初始化
• 3.3.3 适应度函数
• 3.3.4 遗传算子
• 3.3.5 终止条件
• 3.4 矩形件排样问题的遗传算法设计
• 3.4.1 编码方法
• 3.4.2 解码方法
• 3.4.3 初始种群的产生
• 3.4.4 适应度函数
• 3.4.5 交叉算子
• 3.4.6 变异算子
• 3.4.7 选择算子
• 3.4.8 应用遗传算法求解矩形件排样问题的具体步骤
• 3.5 算例分析
• 3.6 本章小结
• 4 蚁群算法
• 4.1 群智能
• 4.2 蚁群算法概述
• 4.2.1 蚁群觅食的特性
• 4.2.2 人工蚂蚁与真实蚂蚁的异同
• 4.3 基本蚁群算法的原理
• 4.4 基本蚁群算法的数学模型
• 4.5 基本蚁群算法的具体实现
• 4.6 基本蚁群算法的特点
• 4.7 改进的蚁群算法模型
• 4.7.1 蚁群系统
• 4.7.2 最大最小蚂蚁系统
• 4.8 本章小结
• 5 融合蚁群算法和遗传算法的矩形件排样
• 5.1 蚁群算法和遗传算法融合的可行性
• 5.2 蚁群算法和遗传算法的融合
• 5.3 矩形件排样的融合算法设计
• 5.3.1 矩形件排样的遗传算法设计
• 5.3.2 矩形件排样的蚁群算法设计
• 5.3.3 遗传算法与蚁群算法的衔接
• 5.4 求解矩形件排样的融合算法具体实现
• 5.5 算例分析
• 5.6 本章小结
• 6 总结与展望
• 6.1 工作总结
• 6.2 工作展望
• 参考文献
• 个人简历及在学期间发表的学术论文
• 致谢