二维排样系统的图形匹配、入排控制与碰靠算法研究

摘要

排样优化问题普遍存在于钣金、钢结构、船舶、服装、皮革和纸制品、玻璃等行业生产过程中,是制造业自动化中从设计到板料切割中的一个关键环节.实现排样自动化,将有利于节省提高劳动效率和资源利用率,保证制造业自动化的良好实现.排样问题总目标是在给定的几何图形上不重叠地放置更多的满足要求的几何图形(一维、二维),使材料利用率最大.具体到不同的行业以及切割、排样环境,表现为不同的约束形式.这是一类NP-hard问题.特别的,大规模规则件排样和不规则件排样问题随着问题规模的增大,计算复杂度更是飞速增长.如何缩短排样时间同时提高板料利用率,是该问题研究的难点,也是该文讨论的重点.

目录

文摘

英文文摘

华南理工大学学位论文原创性声明及学位论文版权使用授权书

第一章绪论

1.1研究背景

1.2排样问题描述与国内外研究现状综述

1.2.1排样问题描述

1.2.2国内外研究现状综述

1.3本文的研究目标和主要工作

1.3.1研究目标

1.3.2主要工作及章节安排

第二章排样问题复杂度分析及优化算法选择

2.1引言

2.2排样优化问题复杂性分析及排样优化算法分析选择

2.2.1排样优化问题计算复杂性分析

2.2.2优化算法特点分析与排样优化算法选择

2.3规则件和不规则件难度分析比较

2.4本章小结

第三章排样系统总体设计、排样数据库设计和排样零件编码研究

3.1排样系统总体设计

3.1.1排样系统设计总目标

3.1.2功能模块设计

3.2排样编码设计

3.2.1船舶排样零件编码研究

3.2.2船舶排样零件编码应用

3.3排样数据库设计

3.3.1排样数据库各表设计及字段的编码设计

3.3.2排样数据库应用

3.4本章小结

第四章基于聚类思想的排样图形匹配技术研究

4.1引言

4.2排样图形聚类匹配中的实用包络算法研究

4.2.1基于位图存储的排样图形

4.2.2有关定义

4.2.3基于位图的外包圆和外包矩形集计算算法

4.3排样图形匹配中的聚类算法研究

4.3.1排样图形匹配中引入聚类思想基于的假设

4.3.2排样图形匹配中的特征提取

4.3.3排样图形匹配中的聚类算法实现

4.3.4带聚类信息的图形排样

4.4排样图形匹配的分类器算法研究

4.4.1排样图形匹配的数据特征分析及分类器算法构建分析

4.4.2排样图形的分类器设计

4.4.3带分类信息的图形排样

4.5本章小结

第五章排样优化算法的改进研究及实现

5.1引言

5.2遗传算法简介

5.3基于免疫机理的遗传算法改进及在排样问题中的应用

5.3.1基于遗传算法的排样算法

5.3.2基于免疫遗传算法的排样算法

5.3.3基于改进的免疫遗传算法的排样算法

5.3.4改进免疫遗传算法应用比较

5.4改进免疫遗传算法中存在的问题及解决方法研究

5.4.1相似度定义的有效性

5.4.2判断相似度定义有效性的统计分析算法设计

5.4.3判断相似度定义有效性的统计测试算法应用与分析

5.5基于上位效应对排样优化算法的改进

5.5.1相关定义

5.5.2基于上位效应对排样优化问题中遗传算法的改进

5.6本章小结

第六章排样优化问题中混合算法的改进研究及实现

6.1引言

6.2邻域搜索算法(NS)与变邻域搜索算法(VNS)

6.3判断邻域假设满足性的：遗传算法+邻域搜索算法(GANS)研究

6.3.1 GANS建立机理分析

6.3.2 GANS中邻域结构的邻域假设满足性研究

6.3.3满足邻域假设的GANS算法设计及应用

6.4不判断邻域假设满足性的：遗传算法+匹配变邻域搜索算法(GAMVNS)研究

6.4.1 GAMVNS建立机理分析

6.4.2 GAMVNS算法设计及应用研究

6.5基于问题分解思想的混合算法：“板宽优先”的动态规划法+遗传算法(DPGA)

6.6本章小结

第七章排样碰靠算法及实现模型比较研究

7.1引言

7.2不规则图形排样问题存在的困难和待解决的关键问题

7.3基于轮廓与基于位图的判交和碰靠算法比较

7.3.1基于轮廓与基于位图的判距-靠接原理比较

7.3.2基于轮廓和基于位图的判距-靠接算法时间复杂度及应用比较

7.3.3基于轮廓与基于位图的判距-靠接算法实例比较

7.4三种基于位图靠接的实现模型比较研究

7.4.1三种基于位图靠接算法原理及实现

7.4.2三种基于位图靠接算法时间复杂度及在排样系统中应用比较

7.4.3三种基于位图靠接算法实例比较

7.5本章小结

结论

附录

附录1遗传算法的基本数学理论

附录2群论的基本知识

参考文献

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

致谢