基于遗传模拟退火算法的二维不规则多边形排样问题

《基于遗传模拟退火算法的二维不规则多边形排样问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、学校代码10699分类号TP391密级学号046110722题目基于遗传模拟退火算法的二维不规则多边形排样问题作者石岩学科、专业计算数学指导教师彭国华教授申请学位日期2007.3西北工业大学硕士学位论文（学位研究生）题目：基于遗传模拟退火算法的二维不规则多边形排样问题作者：石岩学科专业：计算数学指导教师：彭国华2007年3月西北工业大学硕士毕业论文摘要计算机辅助优化排样问题就是将一系列形状各异的零件排放在给定的材料上，找出零件的最优排布，使得给定材料的利用率最高，以达到节约材料，提高效益的目的。从数学计算复

2、杂性理论看，二维不规则样件的排样问题在理论上属于NP完全问题，因为存在实际形状的复杂性和计算上的复杂性，求解十分困难。传统的排样工作都是人工依靠经验进行的，时间长并且效果不理想。由于生产实际的需要，人们迫切需要利用现代科技来解决这一问题。目前研究较多的是规则零件(如矩形)的排样问题，对不规则件的研究较少。本文系统介绍了一种在基于遗传模拟退火算法的前提下，对不规则零件进行直接处理的方法，该方法在通过遗传算法模拟退火算法在空间上搜索优化的排布样件序列。对于每一个待排序列应用启发式定位算法确定其布局，并根据个体适

3、应度评价函数对其布局进行评价，保证在进化过程中良好的排布序列可以保存下来。在分析现有的不规则多边形启发式定位算法的基础之上，本文提出了一种基于平行梯形分割的启发式定位算法，该方法能直接实现不规则多边形的精确定位，并且具有很好的运算效率，这些优越的性能是现有方法所不具有的；对于遗传模拟退火算法，本文根据实际的问题需要确定了染色体的编码方式及相关参数，给出了具体的个体适应度评价函数。本文提出的理论和方法应用到了为XX公司开发的仓库时空优化系统上，项目应用表明该方法满足了实际工程的需要，具有良好的排样效果和实用价

4、值。关键词：不规则样件，排样，启发式算法，遗传模拟退火算法IAbstractAbstractTheaimofthecomputeraidedoptimallayoutofthepartswithdifferentshapesistofindthearrangementofpartsandproducingtheleastwaste.TheproblemofoptimallayoutbelongstotheNP-completeproblemwithtiptopcalculatecomplexity.Itis

5、verydifficulttofindtheoptimalsolutionforsuchaproblembecauseofthehighcomplexityofshapesandcomputation.Conventionallayoutworksalladoptmanualoperationthathavemanyshortcomingssuchaslowyield,inefficientandlongtimeconsuming.Peoplecryforasolutionbythemodemscience

6、andtechnologybecauseoftheneedofproduction.Mostofthepaperspublishedinthisfieldareconcernedwiththepackingproblemofregularshapes(suchasrectangle),onlyafewareabouttheirregularshapes.Amethodfordisposingtheirregularshapesdirectlyisdevelopedbasedongeneticsimulate

7、dannealingalgorithm,whichsearchoptimalshapesequenceinthespace.Thelayoutofeachsequenceisfixedbyheuristiclocationalgorithm,andthenevaluatesitbyfitnessevaluationfunction,toensurethegoodsequencecanbepreservedintheevolutionaryprocess.Inanalyzingtheexistinglocat

8、ionalgorithmsforirregularpolygon,thispaperpresentsanewheuristicalgorithmbasedonparalleltrapeziumdecomposition.Thismethodcandirectlydeterminethepreciselocationoftheirregularpolygon,andhavegoodoperationaleffici