基于NGSA算法的不规则件优化排样系统的研究

摘要

二维零件的优化排样技术广泛应用于装备制造业，同时也是一个具有最高计算复杂度的NP完全问题。本文根据国内外的研究现状、排样问题的自身特点及目前排样算法中存在的问题，针对任意形状的二维不规则零件排样问题的关键技术，进行了深入的研究，提出了一系列解决优化排样问题的算法。本文主要研究包括以下内容： (1)分析并建立了二维不规则件优化排样问题的形式化描述和数学模型。 (2)分析二维不规则件优化排样问题的求解难度，提出了求解该问题的优化策略及求解思路。 (3)通过对各种智能优化算法和启发式算法进行分析，并通过探讨其在不规则件优化排样问题中的应用，将遗传算法、模拟退火算法与小生境技术相结合，互相取长补短，构成小生境遗传模拟退火混合优化排样策略。 (4)研究了矩形排样单元与空白区域填充算法。针对不规则形状零件的矩形排样单元构造过程中的关键技术进行了探讨，并针对在多边形的外轮廓与矩形包络之间容易产生一些空白块，给出了具体算法，克服了以往简单采用最小包络矩形代替零件排样存在空白区域，导致材料利用率过低问题。 (5)提出了基于BLF策略的不规则件的动态扫描定位启发式算法。本算法综合了改进的一步平移法、基于“最低水平线法”策略的动态定位算法与空白区域填充算法。 (6)设计并实现了基于小生境遗传模拟退火算法的不规则件优化排样系统。通过实例验证了算法的有效性和实用性，证明了不规则件优化排样系统完全适合现代制造业的需求，不仅满足材料利用率的要求，也达到了节约原材料的目的。 (7)总结本论文的研究内容，对下一步的工作提出建议。

目录

文摘

英文文摘

1绪论

1.1排样问题概述

1.1.1排样问题的整体描述

1.1.2排样问题的分类

1.1.3排样问题的应用领域

1.2二维不规则件优化排样技术的研究现状及存在的问题

1.2.1国外研究概况

1.2.2国内研究概况

1.2.3排样技术存在的问题

1.3本文的研究目标

1.4本文的主要研究内容

1.5本文的研究特色及创新点

2二维不规则件优化排样问题的描述与建模

2.1二维不规则件优化排样问题的形式化描述与数学模型

2.1.1二维不规则件优化排样问题的形式化描述

2.1.2.二维不规则件优化排样问题的数学模型

2.2二维不规则件优化排样问题的求解难度

2.3二维不规则件优化排样问题的优化策略

2.4二维不规则件优化排样问题的求解思路

2.5本章小结

3小生境遗传模拟退火混合优化策略

3.1混合遗传算法

3.1.1遗传算法

3.1.2模拟退火算法

3.1.3混合遗传算法

3.1.4 GASA混合优化策略

3.1.5 GASA设计思路

3.2小生境技术

3.2.1小生境技术思想

3.2.2小生境技术的实现方法

3.2.3小生境技术的研究与应用

3.3 NGSA算法优化策略

3.3.1 NGSA混合优化策略求解思路

3.3.2 NGSA混合优化策略结构流程

3.3.3 NGSA混合优化策略特点

3.4本章小结

4不规则件优化排样的NGSA混合优化算法设计

4.1 NGSA混合优化算法的基本思路与流程

4.2零件图形处理的相关技术

4.2.1多边形的近似表示

4.2.2多边形顶点顺、逆时针的判断

4.2.3多边形凹凸性的确定

4.2.4排样对象面积的求取

4.2.5多边形外包络矩形的求取

4.2.6改进的矩形排样单元与空白区域的填充算法

4.2.7改进的一步平移法

4.2.8平行线扫描算法

4.3编码机制

4.4解码方法

4.5适应度函数的确定

4.6遗传操作

4.6.1选择运算

4.6.2交叉、变异运算

4.7模拟退火算法的运行参数

4.7.1温度控制

4.7.2接受概率

4.8小生境技术淘汰运算

4.9终止准则

4.10本章小结

5优化排样系统的设计与实现

5.1优化排样系统的总体设计

5.1.1基本功能规划

5.1.2排样系统框架

5.2优化排样系统的实现途径

5.3优化排样系统的用户界面设计

5.4优化排样系统的数据结构设计

5.4.1零件的表示

5.4.2数据结构

5.5优化排样系统的模块设计

5.6优化排样系统的操作流程设计

5.7优化排样系统的操作步骤

5.8运行实例

5.8.1规则板材上优化排样

5.8.2不规则板材上优化排样

5.9本章小结

结论与展望

1全文工作总结

2下一步研究工作

参考文献

致谢

攻读学位期间发表和已录用的学术论文