资源描述：
《采用遗传算法的矩形件优化下料模型》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、制造技术/工艺装备现代制造工程2009年第1期采用遗传算法的矩形件优化下料模型陈勇,王玫,熊艳(四川大学制造科学与工程学院,成都610065)摘要:矩形优化排样问题是典型的组合优化问题,具有NPC(NonpolynomialComplete)难度。针对此类问题的复杂性,提出一个实用的遗传算法模型,该模型在选择算子中,提出新的适值函数,采用无回放随机联赛选择,同时引入精英保护策略;在解码中,提出以边和面积匹配同时达到较优的原则,对剩余矩形匹配算法进行改进。最后通过测试,证明此模型能较好地解决下料问题。关键
2、词:遗传算法;优化下料;匹配原则中图分类号:TP391;TH16文献标识码:A文章编号:1671—3133(2009)01—0063—04AgeneticalgorithmforthemodernofrectangularpackingproblemCHENYong,WANGMei,XIONGYan(SchoolofManufacturingScience&Engineering,SichuanUniversity,Chengdu610065,CHN)Abstract:Theoptimallayouto
3、frectangularpartsisatypicalcombinationaloptimizationproblem,andalsoaNPC(NonpolynomialComplete)problem.Accordingtothecomplexityofthisproblem,anutilitarianmodelwasputforward.Fortheselectionopera2tor,thismodelhaspresentedanewfitnessfunction,adoptingstochast
4、ictournamentselectionwithoutputtingback,andtheelitismschemewasintroducedinit.Inordertoimprovetheremainingrectangularmatchingalgorithm,anewmatchingprinciplewhichmakestheareaandedgematchingachieveoptimizationhasbeenpresentedinthedecoder.Finallythroughexper
5、imentaltest,andtheresultsconfirmthatthismodelcanresolverectanglecuttingproblembetter.Keywords:geneticalgorithm;optimalcutting;matchingprinciple来解决矩形件优化下料问题。此模型在已有遗传算0引言法模型的基础上改进:在交叉运算后采用一个简单的“下料问题”又称为“排样问题”或者“切割问修复策略修复非法染色体;为增加种群的多样性、防题”,是指把需要的多种规格、多种类型的
6、零件排放在止早熟,本文以耗用板材的前n-1块板材的利用率规定尺寸的多张矩形板材上,如何确定下料方案,以作为适值函数,评价染色体的优劣;采用无回放随机[123]使板材的耗用量最低或者利用率最大。这类问题联赛法进行选择,同时引入精英保护策略保护优秀染[7]属于NPC难题,至今尚未找到多项式时间算法。针对色体;在解码时,对剩余矩形匹配算法的匹配原则此类问题的复杂性,国内外许多学者从各个方面做了进行改进,使矩形件的排样更快、更优。最后通过测[4]大量深入的研究,相继提出了一些近似算法。到20试,证明此模型能较好
7、地解决下料问题。世纪末期,随着遗传算法、模拟退火算法和神经网络1排样问题描述算法等现代智能优化算法的成熟,一些研究者开始将[5]它们应用于零件排样中,取得了一定成果。遗传算矩形件排样问题是排样问题中研究最多、应用最法属于一种全局优化算法,具有解决非线性问题、鲁广的一类问题,其实质是通过设计一种合适的排样方棒性强、全局最优性不依赖于问题模型、可并行性、高法和一个合理的排样顺序,使零件在板材上的排样能[6]够达到较优。其数学描述如下[7]。效率及全局搜索能力强等特点,但具体运用还存在一些不足,例如文献[1]
8、、文献[3]中用的都是随机性设有各种大小同质矩形零件集合{Pi},i∈[1,较强的“轮盘赌”选择方法。针对遗传算法在下料问n],其面积集合为{bi};另有原材料板材集合{Aj},j∈题中的运用不足,本文设计一个实用的遗传算法模型[1,m],其面积集合为{aj};排样工作就是选出适当的63现代制造工程2009年第1期制造技术/工艺装备板材集合{Aj′},j′∈[1,k],其面积集合为{aj′},将零交叉后的两个染色体中都出现了重复的数字(R1
