学位论文 > 优秀研究生学位论文题录展示

矩形三阶段带排样问题的遗传算法的研究

作　者: 严玄
导　师: 崔耀东
学　校: 广西师范大学
专　业: 计算机应用技术
关键词: 矩形带排样遗传算法三阶段切割下料优化
分类号: TP391.7
类　型: 硕士论文
年　份: 2009年
下　载: 29次
引　用: 0次
阅　读: 论文下载

内容摘要

计算机辅助排样(CAN)是计算机辅助技术最具体的应用之一,是计算机技术与现代经济快速发展的必然产物。它广泛存在于机械加工、家电制造、服装裁剪、国防科技等国民经济行业中,解决好这类问题可以节省原材料,简化生产工艺,降低生产成本,增加企业效益。矩形件带排样问题(RSPP)是矩形排样问题中的一个重要分支,它是指给定n个不同的矩形零件集合R1 , R2,,Rn,将其全部置于定宽无限高的矩形条带Q上,使得所占据条带的高度最小。RSFP在理论上是属于高计算复杂性的NP完全问题,求解这类问题所需要的计算量随着问题规模的增加呈指数级增长,而不是线性增长。因此,研究RSPP具有重要的实用和理论价值。遗传算法是借鉴生物的自然选择和遗传进化机制而开发出来的一种自适应全局优化概率搜索算法,它模拟生物进化的基本过程,通过对群体施加选择、交叉、变异等遗传算子来仿真生物的基本进化过程,逐步使群体进化到所求得的解包含全局最优解或近似最优解。它对于非常复杂、高度非线性的组合优化问题表现出比传统优化方法更加独特和优越的性能。排样问题是一个多目标规划问题,在考虑材料利用率的同时,还需要考虑到生产工艺的要求。为了适应特殊的领域,排样过程中需要满足特定的生产工艺要求,往往会对得到的排样方式加以限制,生成适合的下料方案。基于上述考虑,本文使用一种基于遗传算法求解RSPP的启发式遗传算法,同时要求得到的排样方式为一个三阶段排样方案。本文的主要工作如下:首先,本文使用一种基于递归方法的启发式解码方式,通过对染色体序列进行解码,得到对应的三阶段排样方式。将分段切割的思想引入到解码过程中。在解码过程中根据毛坯的序列将排样方案划分为层,将层划分为堆,层和堆上毛坯的排放遵循贪婪的原则,若当前堆上方不可以继续排放任何毛坯时则产生一个新堆,当前层上不能再产生新堆时划分一个新的层,依循这样的排放规则直到所有的毛坯排放完成。这样所得到的排样方式为一个可剪切下料的方式,即可沿层的方向先把矩形条带切割成比较小的段,然后沿堆的方向再将层切割成若干个小堆,最后将堆切割成所需要的毛坯。其次,依据特定的分层思想,设计交叉算子和变异算子。在进行交叉操作时,交叉的对象设计成以层为单位进行,在对染色体解码以后,通过比较各层的废料率,将废料率较小的层遗传到子代,这样既保留了父代染色体的优良基因片段,又提高了交叉的效率;同样的,变异操作也以层为单位进行,先找出当前个体所对应的排样方式中那些排放不合理的毛坯,先从当前位置删除,将其放在基因队列的最后,然后选择部分待变异的层并拆分这些层,最后将这些毛坯依次插入到未被拆分的层上的合适位置。经过交叉和变异操作后,引入一个新的操作——调整操作,该操作在不改变带的利用率的条件下,用来调整层和堆的相对位置,简化得到的排样方案。然后,规划和设计了排样系统的基本功能模块,开发了一个基于遗传算法的矩形带排样系统。通过大量实验测试,并将实验结果与同类算法的实验结果进行比较和分析,验证了该系统的算法的有效性。最后,论文对己完成的工作进行了总结,指出进一步的研究工作。

全文目录

中文摘要  3-5
ABSTRACT  5-9
第1章绪论  9-13
  1.1 计算机辅助排样简介  9
  1.2 矩形排样问题分类和带排样问题的研究现状  9-11
  1.3 算法的复杂性理论介绍  11
  1.4 本文所做的工作  11-12
  1.5 文章的组织结构  12-13
第2章遗传算法  13-19
  2.1 遗传算法的产生和发展  13
  2.2 遗传算法的特点  13-15
  2.3 遗传算法的基本步骤  15-18
    2.3.1 染色体的编码  15
    2.3.2 初始种群的创建  15
    2.3.3 适应度函数  15-16
    2.3.4 遗传算子  16-18
    2.3.5 参数控制  18
    2.3.6 解码  18
  2.4 混合遗传算法  18-19
第3章矩形件带排样算法研究  19-23
  3.1 矩形带排样问题的数学描述  19
  3.2 最低水平线搜索算法  19-21
  3.3 递归算法  21-22
    3.3.1 启发式递归算法  21-22
    3.3.2 分支定界递归算法  22
  3.4 本章小结  22-23
第4章矩形三阶段带排样问题的遗传算法  23-31
  4.1 三阶段排样方式  23
  4.2 染色体的编码和解码  23-25
  4.3 适应度函数  25
  4.4 遗传算子  25-29
    4.4.1 交叉算子  26-27
    4.4.2 变异算子  27-28
    4.4.3 调整算子  28-29
  4.5 初始种群生成策略  29-31
第5章矩形带排样系统的研制与实验计算  31-38
  5.1 系统的开发  31
  5.2 实验算例  31-36
    5.2.1 第一组数据  32-34
    5.2.2 第二组数据  34-36
  5.3 实验结果分析  36-38
第6章总结和展望  38-39
参考文献  39-42
攻读硕士学位期间发表的论文  42-43
致谢  43-44

矩形三阶段带排样问题的遗传算法的研究

内容摘要

全文目录

相似论文