智能数控裁床的研究与开发——二维不规则零件排样算法的设计与应用

摘要

二维排样问题是希尔伯特提出的23道数学难题之一，它属于 NP 完全问题，也是复杂的非线性约束优化问题，至今在理论上尚未找到答案。然而排样问题广泛存在于诸如板金下料、服装裁剪、报刊排版、大规模集成电路设计等领域，虽然各行业排样模型和约束条件不同，但共同目标是生成合理的材料分割排样方案，即求解NP完全问题的全局最优解，这对提高材料的利用率、降低产业成本有着非常重要的应用价值。人们利用计算机辅助排样(CAN)手段对该问题进行了大量探索，求解方法从最初的数学规划方法到现代的启发式方法，但各种启发式算法有其各自的局限性。因此，探索排样问题的高效优化算法具有重要的研究和应用价值。 研究中，首先利用图形扫描转换技术把二维不规则零件多边形转化为样片的离散化几何表达，使排样脱离多边形几何零件的复杂性，从而避免零件多边形判交的复杂性和最小包络矩排样的低利用率。接着把基于图形扫描转换技术的启发式底左搜索(HBLS)算法作为底层算法，用它来接收上层优化算法传递过来的零件排样的优化参数，为优化排样的高效处理奠定基础。 然后，本文重点研究了两个改进的粒子群优化算法，把它们作为上层优化排样算法。一种是量子行为的粒子群优化算法(QPSO)，另一种为最大速度收缩策略的粒子群优化算法(MVCS-PSO)。通过对二维不规则零件的优化排样进行仿真，结果表明：这两种算法具有良好的非线性和动态搜索性能，在收敛性能和时间复杂度上都优于模拟退火遗传算法(SAGA)；QPSO算法的在稳定性和时间复杂度上优于MVCS-PSO算法，而其收敛性能稍差于MVCS-PSO算法。在此基础上，把改进的算法应用到服装CAD自动排料模块中，结果表明：在面料的利用率和运行时间上都优于SAGA。因此，改进的粒子群算法的研究和应用为求解排样问题提供了的一种高效算法。

目录

文摘

英文文摘

声明

第一章绪论

1.1引言

1.2排样问题的研究意义

1.3排样问题的研究现状

1.3.1矩形件排样情况

1.3.2不规则零件的处理方法

1.3.3基于启发式的现代优化算法

1.4课题的主要工作

第二章启发式底左搜索(HBLS)策略的排样研究

2.1启发式算法在排样问题中的地位

2.2不规则零件的离散化几何表达

2.2.1不规则零件的边表建立

2.2.2样片的扫描区间

2.2.3板料的扫描区间

2.3启发式底左搜索(HBLS)算法

2.3.1启发式底左搜索策略

2.3.2 HBLS策略的基本约束条件

2.3.3 HBLS策略的的算法设计

2.4仿真结果

第三章模拟退火遗传(SAGA)算法的排样研究

3.1二维排样问题的参数优化方法

3.1.1排样参数的确定

3.1.2排样参数的数据结构

3.1.3参数的扰动对排样结果的影响

3.1.4排样参数的优化过程

3.2 SAGA的形成机理

3.3 SAGA的排样优化过程

3.3.1 SAGA的编码及其运算

3.3.2 SAGA的排样优化流程

3.4仿真结果及分析

3.4.1仿真实例1

3.4.2仿真实例2

第四章最大速度收缩策略的粒子群优化算法排样研究

4.1 PSO算法

4.1.1 PSO算法简介

4.1.2 PSO算法的运算过程

4.1.3 PSO算法的参数控制

4.2最大速度收缩策略的粒子群优化(MVCS-PSO)算法

4.2.1 MVCS-PSO算法的参数控制

4.2.2 MVCS-PSO算法的排样粒子构造

4.2.3 MVCS-PSO算法的排样优化过程

4.3仿真结果

4.3.1仿真环境及参数

4.3.2仿真结果比较

4.3.3仿真实例输出

4.3.4收敛性能分析

4.4本章小结

第五章量子行为粒子群优化(QPSO)算法的排样研究

5.1 QPSO算法

5.2 QPSO算法的排样优化

5.2.1 QPSO算法的排样粒子构造

5.2.2 QPSO算法的排样优化过程

5.3仿真结果

5.3.1仿真环境及参数

5.3.2仿真结果比较

5.3.3仿真实例输出及收敛性能分析

5.4本章小结

第六章排样算法在服装CAD自动排料中的应用

6.1服装CAD排料概况

6.2服装CAD自动排料的算法设计

6.3自动排料的仿真实例

第七章总结与展望

7.1总结

7.2展望

致谢

参考文献

附录

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