基于遗传算法的二维不规则图形排料问题的研究与应用

摘要

排料问题应用范围非常广泛，如服装行业、皮革行业、机械行业。提高板材利用率能降低企业的生产成本，会给企业带来经济效益，所以，排料问题的研究具有重要的经济价值。二维不规则排料问题具有很高的复杂性，属于NP完全问题，即不能在多项式时间内找到问题的最优解，所以，排料问题的研究具有重要的理论价值。 遗传算法(GA)是一种全局优化的现代启发式算法，通过交叉、变异来避免陷入局部极小。与传统优化方法相比，遗传算法仅仅利用个体的适应度进行群体的进化，不需要优化模型中目标函数和约束函数的导数信息，因而具有极强的鲁棒性，适合于解决各种优化问题。本文从遗传算法的产生背景、基本思想以及收敛性理论方面进行了细致的说明。 本文将遗传算法应用到二维不规则排料领域中，得到了很好的效果。出于对带圆弧图形的考虑，本文应用了自动提取零件数据的算法和求解逼近多边形的方法。 在自动排料计算的过程中，如何找到零件之间在什么位置靠接紧密并且不重叠是一个关键的问题。为了减少多边形之间重叠性判断的计算量，提高算法效率，在本文中采用了临界多边形算法，并对现有的临界多边形算法进行了改进，主要是针对两个凹多边形临界多边形的改进，首先通过将一个凹多边形进行凸化，然后求出凹多边形和凸多边形的临界多边形，再把凸化得到的边转化成对应的凹边，进而得到两个凹多边形的临界多边形。由于实际生产中往往需要用到多张板材，所以本文也考虑了多张板材的排料。 此外，本文设计了自动排料算法中其它一些相关的图形学算法，如凸包算法和合成多边形算法。 基于上述算法的研究，设计了二维不规则零件自动排料系统，该系统具有友好的界面。系统可以对AutoCAD零件图纸直接处理，通过对板材参数的设定和零件的选择，可以自动生成零件的排料图。

目录

文摘

英文文摘

声明

1绪论

1.1研究背景及意义

1.2排料问题的分类

1.3国内外研究现状

1.4二维不规则排料问题分析

1.5本文研究重点

2遗传算法

2.1遗传算法的产生背景与发展历史

2.2遗传算法的基本思想

2.3遗传算法的收敛性分析

2.4遗传算法的应用情况

3系统总体设计

3.1系统功能设计

3.2自动排料主要算法

3.3零件的文件结构

3.4系统类设计

3.5带圆弧的多边形以及加工余量处理

3.6系统的开发环境及工具

3.6.1软件开发环境

3.6.2系统开发工具

4遗传算法求解不规则排料问题

4.1染色体编码方法

4.2目标函数和适应度函数

4.3遗传算子的选用

4.3.1选择算子

4.3.2交叉算子

4.3.3变异算子

4.4遗传算法的运行参数及解码过程

5二维不规则图形排料主要算法

5.1任意多边形面积

5.2多边形顶点凹凸性判断

5.3凸包算法

5.4合成多边形算法

5.5矢量边角度求解

5.6改进的临界多边形算法

5.6.1临界多边形的概念

5.6.2 Minkowski sum的定义以及它与临界多边形的关系

5.6.3两个凸多边形的临界多边形

5.6.4凹多边形和凸多边形的临界多边形

5.6.5两个凹多边形的临界多边形

5.7多张板材排料

6基于遗传算法的二维不规则排料系统

6.1排料系统简介

6.2排料实例

7结论

参考文献

在学研究成果

致 谢