基于并行遗传算法的矩形件排样优化.pdf

《基于并行遗传算法的矩形件排样优化.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第3期组合机床与自动化加工技术NO．32011年3月ModularMachineTool＆AutomaticManufacturingTechniqueMar．2011文章编号：1001—2265{2011)03—0078—05基于并行遗传算法的矩形件排样优化隗平平，刘斌(华侨大学机电与自动化学院，福建厦门361021)摘要：利用遗传算法对待排零件进行编码，将矩形件正交排样问题转化为排列问题。然后采用一种新的解码排样算法——基于最低水平线的改进算法，将每一个体编码转化为排样图，进行适应度评价，以

2、驱动遗传进化，最终寻找出最优排样图。对遗传算法进行了并行性改进，较好地维持了种群的多样性，增强了算法的搜索效率。对文献中的两个算例进行了求解，结果表明该算法是有效的。关键词：矩形件；排样优化；并行遗传算法中图分类号：TP391．72文献标识码：ATheRectangularPackingandOptimizationOilParallelGeneticAlgorithmWEIPing—ping，LIUBin(CollegeofMechanicalEngineeringandAutomation，

3、HuaqiaoUniversity，XiamenFujian361021，China)Abstract：Usinganimprovedparallelgeneticalgorithmstoencodetherectangleparts，conve~theorthog-onalrectangularpackingproblemintotheproblemofpermutation．AnewdecodingalgorithmfornestiIl一theimprovedLowestHorizontal

4、LineAlgorithm-isproposedfordecodingeveryindividualpermutationintoapackingpatternforfitnessevaluation，SOastodrivegeneticevolution，andeventuallyf'mdingouttheoptimalpackingpattern．Inordertomaintainthediversityofpopulationandincreaseitssearcheficiency，ma

5、kingaparallelimproveforgeneticalgorithm．Solutionstotwoexamplesshowthevalidityandeficiencyofthealgorithm．Keywords：rectangleparts；packingoptimization；parallelgeneticalgorithms(PGA)一类问题，近几十年来，国内外众多学者都是以矩形0引言件排样优化问题为基础，深入研究各种不规则零件排样优化普遍存在于钣金、钢结构、航空、船舶、的排

6、样问题。到目前已经提出多种切实可行的用于服装、皮革和纸制品以及玻璃加工等行业生产过程排样优化的近似算法1-7]。Baker等人在1980年最中，是制造业自动化中从设计到板料切割过程中的早提出了最下最左(bottom—left，BL)算法¨，之后的一个关键环节。排样优化是指在给定规格的原材料一些学者在BL算法的基础上进行了改进，提出了基上，互不重叠地尽可能多地排放各种形状的待排零于BL的填充(bottom—leftfilling，BLF)算法、下台阶件，使原材料的利用率最高。因此，实现排样优化将算

7、法及最低水平线法等排样算法。随着智能优最大限度地节约材料，提高工业生产效率，具有重要化算法的日益成熟及其在TSP问题、空间分配等组的现实意义。合优化问题上的成功应用，遗传算法(GA)、模拟在数学计算复杂性理论上，排样优化问题属于退火算法(SA)、粒子群算法(PSO)⋯等优化算法NP完全问题。对于这类问题，以目前已成熟的计算与以上排样算法相结合，广泛应用于矩形件排样问理论和算法，或者根本无法求解，或者求解的计算量题的求解，并取得了很好的效果。是爆炸性的。文献[2]研究了矩形件正交排样的遗传算法求矩

8、形件排样优化是排样优化问题中较为基础的解，其基本思想是将个体的编码视作一个排列，通过收稿日期：2010一O9一l7基金项目：福建省科技计划重点项目(2009H0032)作者简介：隗平平(1985一)，男，湖北武汉人，华侨大学机电与自动化学院硕士生，研究方向为数字化设计与制造技术，(E—mail)wpwow@hqu．edu．cn。2011年3月隗平平，等：基于并行遗传算法的矩形件排样优化·79·BL(BottomLeh)算法将编码转化为相应的排样图。3解码排样算法但是，BL算法并不能求解某些问题的