基于临界多边形的二维不规则排样算法研究

《基于临界多边形的二维不规则排样算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士学位论文基于临界多边形的二维不规则排样算法研究作者姓名徐将将学科专业控制理论与控制工程指导教师吴忻生副教授所在学院自动化科学与工程学院论文提交日期2018年4月ResearchofTwo-DimensionalIrregularNestingAlgorithmBasedonNoFitPolygonADissertationSubmittedfortheDegreeofMasterCandidate：XuJiangjiangSupervisor：AssociateProf.WuXinshengSouthChinaUniversityofTechnolo

2、gyGuangzhou,China分类号：TP391学校代号：10561学号：201520112680华南理工大学硕士学位论文基于临界多边形的二维不规则排样算法研究作者姓名：徐将将指导教师姓名、职称：吴忻生副教授申请学位级别：工学硕士学科专业名称：控制理论与控制工程研究方向：智能优化算法论文提交日期：2018年4月20日论文答辩日期：2018年6月4日学位授予单位：华南理工大学学位授予日期：年月日答辩委员会成员：主席：游林儒委员：吴忻生、陈立定、高红霞、陈安摘要二维不规则排样问题属于平面布局优化问题，是指在给定的原材料空间布局内，排放若干零件，且各个零件

3、间互不重叠。目标是寻找一个最优的排样方案，使原材料的利用率越高越好。排样问题广泛存在于钣金、皮革、服装、木材、石材、航空航天等众多行业中，提高原材料的利用率，对提高经济效益和缓解资源紧张带来的环境压力有重要意义。本文对二维不规则件排样中的关键问题进行了分析研究，主要的研究内容如下：基于矢量线段的临界多边形（NFP）生成算法研究：NFP算法是二维排样中的关键基础性问题，也是二维排样算法发展的瓶颈问题。本文提出基于矢量线段的NFP生成算法，将多边形间的滑动碰撞转化为“角-矢量边”接触判断问题，对可能接触的“角-矢量边”组合生成矢量线段集合，基于最小旋转角策略

4、从矢量线段集合中提取NFP，并对特殊情况如退化点和退化线进行处理。算法有效地解决了NFP的计算正确性，同时其计算速度较移动碰撞算法有较大提高。混合启发式排样算法研究：分析临界多边形在排样中的作用，结合“NFP+IFR”算法提取待排零件可行的候选排放点。在TOPOS算法基础上，提出三种LAO启发式评价标准来评价零件的排放质量，对这些评价标准设计组合出三种混合策略，用于选择下一个排放的零件以及从候选排放点选择最合适的排放位置。基于随机键遗传算法的排样算法研究：分析了随机键遗传算法的特点和流程，结合二维不规则排样问题特点，使用随机键遗传算法优化零件的排放次序、

5、旋转角度和定位策略。对随机键遗传算法中个体的编码和解码、适应度函数、种群的选择、交叉、变异操作等内容进行设计。实验结果表明，算法有较强的全局优化能力，获得比启发式算法和小生境遗传算法更优的排样方案。带缺陷不规则原材料的排样算法研究：分析带缺陷不规则原材料排样问题的数学模型，并引入内靠接临界多边形(INFP)概念，扩展矢量线段法求解INFP。针对缺陷不规则原材料，结合“NFP+INFP”法提取可排放点来避开缺陷区域，分别对混合启发式算法和随机键遗传算法进行改进以适用于带缺陷不规则板材排样问题。实验结果表明，算法使零件能紧凑排放在原材料内部并有效避开缺陷区域

6、，随机键遗传算法比混合启发式能获得更好的原材料利用率。关键词：不规则排样；临界多边形；随机键遗传算法；带缺陷不规则原材料IAbstractThetwo-dimensional(2D)irregularnestingproblembelongstotheproblemofplanarlayoutoptimization.Itcanbedescribedformallyasthatalistofgivenpiecesistobeplacedontoagivenplate,withnooverlapbetweenanytwopieces.Theobjectiv

7、eoftheproblemistofindanoptimalnestingsolutionandimprovetheutilizationofplate.Nestingproblemiswidelyexistsinmanyindustriessuchassheetmetal,leather,clothing,wood,stone,aerospace,etc.Toimprovetheutilizationofplateisofgreatsignificanceforimprovingeconomicefficiencyandalleviatingtheen

8、vironmentalpressurecausedbyresourceshort