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

《二维排样系统的图形匹配、入排控制与碰靠算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、华南理工大学博士学位论文二维排样系统的图形匹配、入排控制与碰靠算法研究姓名：宋亚男申请学位级别：博士专业：控制理论与控制工程指导教师：刘永清;邓飞其20040520摘要排样优化问题普遍存在于饭金、钢结构、船舶、服装、皮革和纸制品、玻璃等行业生产过程中，是制造业自动化中从设计到板料切割中的一个关键环节。实现排样自动化，将有利于节省提高劳动效率和资源利用率，保证制造业自动化的良好实现。排样问题总目标是在给定的几何图形上不重叠地放置更多的满足要求的几何图形(一维、二维)，使材料利用率最大。具体到不同的行业以及切割、排样环境，表现为

2、不同的约束形式。这是一类NP-hard问题。特别的，大规模规则件排样和不规则件排样问题随着问题规模的增大，计算复杂度更是飞速增长。如何缩短排样时间同时提高板料利用率，是该问题研究的难点，也是本文讨论的重点。本文的主要工作和研究成果有:(1)将聚类思想引入排样问题，提取排样图形匹配的有效数据特征，并对该数据特征进行分析，设计了适合于排样图形匹配的聚类算法和分类器算法。(2)为了保证排样图形聚类匹配中的数据特征的有效提取，给出了基于位图的实用外包圆、外包矩形集及近似长短轴的计算算法，提出了选择合适的外包策略的原则。(3)对排样图

3、形进行了编码研究，利用(2)所获得的图形匹配的有效特征，在排样数据库中补充了排样图形的特征信息，提高了排样图形的检索速度。(4)引入免疫机制，针对排样问题提出了更为有效的相似度定义，帮助遗传算法有效避免早熟收敛。(5)为了判断改进免疫遗传算法的免疫算子是否真正起作用，提出了免疫算子假设，并提出和设计了统计分析测试算法对该假设进行测试分析，指导相似度定义及其参数的设定。(6)基于对排样问题编码上位效应分析，通过排样过程中建立对好基因片的反馈信息，指导遗传算法交叉率和变异率大小选择、交叉和变异发生位置选择，有效避免了遗传算法的欺

4、骗问题和链接问题。(7)针对遗传算法不具有良好的局部搜索特性的局限性，建构了遗传算法和邻域搜索算法的混合算法;而因为组合优化问题中，解空间是离散的，邻域搜索算法是否真正起到了良好的局部搜索效果并不是一定的，本文针对遗传算法+邻域搜索算法，进一步提出了邻域假设;并研究了邻域假设是否被满足，给出了设计满足邻域假设的方法和测试已有邻域结构是否满足邻域假设的统计测试算法。华南理工大学博士学位论文(8)针对(7)中邻域假设的满足性难以判断、判断不准确或者出现邻域假设不被满足的情形，本文对遗传算法十邻域搜索算法进行进一步改进，提出了遗传

5、算法十匹配变邻域搜索算法。(9)基于问题分解的思想，本文针对排样优化问题提出了“板宽优先”的动态规划算法+遗传算法的混合算法。(10)为提高排样图形碰靠速度，本文研究比较了基于轮廓和基于位图的碰靠算法，提出了3种基于位图的实现模型，并对这3种实现模型进行对比研究，给出了碰靠算法选择原则。(11)设计和实现了二维图形自动排样系统。关键词排样;免疫一遗传算法;混合算法;图形聚类;碰靠算法AbstractABSTRACTPackingCuttingoftwo-dimensional(2-D)partsfrom2-Dsheetsis

6、acommonprobleminwood-,glass-,steel-,leatherandpaperindustry.Itisakeycomponentfromdesigningtocuttinginautomationofmanufacturing.TorealizetheautomationofpackingwillbehelpfultoincreaseefficiencyoflaborandutilizationofmaterialsandtorealizetheautomationofmanufacturingIt

7、sgoalistoputmorepartswithoutoverlapsinthegivensheetsandgetthemaximalutilizationofmaterials.Therearemanydifferentconstrainsindifferentindustry.However,theyareallNP-hardproblems.Inparticular，withthetheincreasingofdimentionsofregularpacking-graphicsandirregulargraphic

8、s,thecomplexityofcomputationincreasesrapidly.Howtorecreasethetimeofpackingandincreasetheutilizationratioofmaterialsisthefocusthatiscaredaboutbyre