二维不规则零件排样问题的研究

摘要

二维不规则零件排样问题是一个在许多生产实践中都有着关键应用的重要问题，在理论上属于NP完全问题，求解十分困难，因此对该问题的研究有着广泛的应用背景和理论意义。在研究国内外学者提出的方法的基础上，本文主要做了如下工作： 论文分别对排样零件预处理，零件靠接，零件入排算法控制这三个二维不规则零件排样阶段进行了相关分析，主要研究了含空洞的、外廓为弧形的和包络矩形等不规则零件预处理方法；介绍了二维不规则零件在排样空间中的边界表示、旋转空间及几种常见的碰撞靠接算法；着重介绍了遗传算法基本操作及特点，针对遗传算法解决不规则排样问题时在局部优化方面的不足之处，提出了两种改进方法：一、把遗传算法与一种新的可加强局部优化的算法--极值优化算法相结合，使遗传算法局部寻优不佳的缺陷得到改进。二、基于BL排样规则与边界产生式规则，将遗传算法直接用于局部优化，通过与基于序号的一般遗传算法进行比较，本文算法用时更短。

目录

文摘

英文文摘

论文说明：图表目录

声明

致谢

第一章 绪论

1.1 排样问题

1.1.1 排样问题的提出及意义

1.1.2排样问题的分类

1.1.3 排样问题的特点与求解难度

1.2 二维排样问题

1.2.1 二维排样问题的分类及现状综述

1.2.2 二维不规则零件排样问题的难点及解决方法

1.3 本文主要工作和章节安排

第二章 二维不规则零件的预处理

2.1 凹凸点判断及凸多边形

2.2 外廓为圆弧或圆的零件处理

2.3 有空洞的零件处理方法

2.4 形状相同或相近零件的排放方法

2.5 矩形包络

第三章 二维不规则零件排样空间的处理

3.1 不规则零件的空间定位算法——BL排样规则

3.2 零件重叠性的判断

3.2.1 零件的碰撞检测算法

3.2.2零件的靠接

3.3 零件库的建立

3.4 零件的边界表示

3.5 零件坐标变换

3.5.1 零件的平移

3.5.2零件的旋转

第四章 解决二维不规则排样问题的遗传算法

4.1 遗传算法的起源与发展

4.2 遗传算法的一般步骤

4.3 基本遗传算法的描述及实现

4.4 遗传算法的特点和不足

4.5 遗传算法的应用及改进

4.6 遗传算法和极值优化算法相结合

4.6.1 极值优化算法

4.6.2 基于极值优化算法的遗传算法

4.7 基于边界产生式规则和遗传算法的不规则排样

4.7.1 算法思想及主要步骤

4.7.2编码

4.7.3适应度函数

4.7.4选择、交叉、变异

4.7.5 算法实验结果

第五章 总结与展望

参考文献

攻读硕士学位期间发表的论文