优化排料算法国内外发展状况

1、国青徐土学文献综述报告题目基于模拟退火遗传算法的变压器硅钢片优化排样的研究姓名王雪红导师魏福玉教授层次硕士所在学院机械科学与工程学院专业机械工程学号学10414048日期2021年9月20日目"2-一、优化排料算法国内外开展状况-3-1.1、 优化排料算法国外开展现状-.3-1.2、 优化排料算法国内开展现状-.3-二、排料算法的类型与特点-4-2.1、 简单遗传算法-.4-2.2、 遗传算法的特点.-.6-2.3、 标准遗传算法的局限性及其改良方式-6-2.4、 混合遗传算法-.7-三、参考文献-12-、优化排料算法国内外开展状况1.1、 优化排料算法国外开展现状对于优化排样问题,

2、国外进行得比拟早,1939年Kantorovich就提出了一维排样问题.之后,Gilmore和GomoN2提出了解决一维排样的方案并深入分析探讨了二维优化排样问题.Maneri和Silverman4提出运用向量空间的理论处理排样问题.70年代后,越来越多的学者和专家发现了排样问题的经济价值和社会价值,并对其进行了深入研究,提出了许多算法理论和解决排样问题的方案,并取得重大成果.1970年Haims等提出了动态规划理论和相关算法,Herz网提出了一种树叉型搜索策略,并将其用于动态规划理论中.Han和Cintra7®等将零件拆分技术用于求解排样问题,Faina9将模拟退火算法运用于切割下

3、料问题.到了80年代,智能优化算法相继出现,并被广泛运用于求解矩形件和不规那么件排样问题.80年代后,智能算法的研究到达一个快速开展的时期,如模拟退火算法1°第、遗传算法14A7、神经网络18、蚁群算法19、人工免疫算法20等算法,这些算法具有一般搜索算法所不具有的优越性,为了充分利用它们的优越特性,人们开始探索组合算法,以求获得更佳的排样效果.MarcelloBraglia21用模拟退火算法改善遗传算法求解单排排样问题,Troutt和Bingul2273用遗传和模拟退火算法对矩形件排样进行了研究,RameshBabu242等用启发式算法来改善遗传算法求解二维排样优化问题,Crist

4、ina29用免疫算法来改善遗传算法求解二维矩形排样问题.止匕时,对矩形件排样问题的研究已经取得了相当的成就.1.2、 优化排料算法国内开展现状20世纪90年代初国内开始了排样问题的研究,主要是基于简单排样件或矩形件的排样.曹炬博士30*采用背包算法等来研究不同排样环境下的矩形件排样,对矩形件排样算法进行了深入的研究.徐彦欣32采用基于产生式规那么和图形靠接算法进行二维零件的排样,讨论和比拟了移动靠接算法、碰撞靠接算法、临界多边形算法的特点.此处,董长双33深入研究了冲裁件的二维优化排样,周建华34深入研究和探索了不规那么排样技术,滕健35提出用神经网络的相关理论来求解二维不规那么零件的排样问题

5、.2000年以后,排样问题进一步得到广阔学者和专家的重视,排样件从矩形件逐步开展到规那么件和不规那么件,排样算法的运用逐步由单一算法开展二种以上算法的组合,并且算法的运用范围和领域也不断扩大.贾志欣36,7采用遗传算法和模拟退火算法来求解矩形件排样问题,提出了最低水平线排样定位算法.吴浩扬38等提出了基于模拟退火机制的多种群并行遗传算法.智能算法的出现进一步促进了排样问题的开展,它分别从不同的角度模拟人类的智能活动或某些自然现象,被广泛用来解决工程中存在的复杂问题,如求函数最值、TSP问题、自适应限制、机械领域下料问题、机器人限制方面、服装下料等问题.近几年来,智能算法得到更进一步的开展,如在

6、遗传算法393、人工免疫算法44弗、神经网络47等等方面的研究.这些方法在搜索过程中具有随机性,具有比数学规划方法更大的优越性,主要表现在：具有通用性且易于应用；搜索速度快,所需的时间复杂度小,并且能更快地获得较优排样结果.正是由于这些优点使这类算法在工程问题上具有更为广泛的应用前景,吸引了更多学者和专家对其进行研究和探讨.智能算法也有其自身的缺点,因此学者们开始研究智能算法之间的结合,通过取长补短的方法来到达更好解决工程中遇到的排样问题.二、排料算法的类型与特点2.1、 简单遗传算法遗传算法在自然与社会现象模拟、工程计算等方面得到了广泛的应用.在各个不同的应用领域,为了取得更好的结果,人们对

7、GA进行了大量的改良.为了不至于混淆,我们把Holland所提出的算法称为标准遗传算法(CanonicalGeneticAlgorithm),简称GA或SGASGAH一种随机搜索方法,其算法流程如图1所示.与生物种群的进化过程相似,SGA从随机生成的种群(优化问题的解集)开始,根据适者生存的原那么,经过选择、交叉、变异等遗传操作,使种群的整体适应度(优化问题的目标函数值)向着增大的方向进化.SGA勺核心思想包括：(1)优化问题的一个解经过适当的编码与解码算法,与生物种群中个体的染色体对应,种群的进化操作是针对染色体的.(2)优化问题的目标函数用一定规那么表示成具有一定染色体结构的个体对环境的适

8、应程度,进化操作使种群的适应度向着增大的方向进化,即向着优化目标函数增大的方向进化.图1算法流程进化操作,即遗传算子,与生物进化中常见的现象相似,通常使用选择、交叉、变异算子.不同的编码方案、种群组织策略和遗传算子相结合构成不同的遗传算法.根据种群的组织方式有非重叠和重叠种群,以及单种群和多种群的遗传算法;根据遗传算子的执行方式有非重叠和重叠遗传操作的遗传算法.Holland首先用模式定理“解释遗传算法的搜索行为,该研究成果奠定了遗传算法的数学理论根底48.0模式定理指出具有优秀基因片段的个体,即包含低阶的、短的、平均适应度高的模式的个体,会随进化过程呈指数级增长.GA的隐含并行特性说明GA在

9、每一代进化中实际处理的有效模式数量的下限值为群体数量M的立方M3算法可以快速搜索一些比拟好的模式.这是遗传算法能够有效搜索的根本原因之所在.Holland给出的是二进制编码的模式定理,其他编码下的模式定理与之相似51,2.除了模式定理,在关于GA的运行机理的理论中,有两点是普遍接受的：用Markov链的性质可以分析GA的收敛特性；根据NoFreeLunch简称NFL定理可以判断GA寸所有问题求解的平均特性并不比随机搜索好,即GA只对特定问题效果出众.遗传算法的根底理论研究至今还没有取得突破性进展,理论与应用之间还存在着很大的差距.近年来一些学者对模式定理的正确性提出了质疑.模式定理是否成立,甚

10、至模式本身是否存在,都被研究人员疑心50.尽管大量成功的实际应用支持模式定理所依赖的积木块假设,但至今还没有一种方法可以判别“对于一个给定的问题,积木块假设是否成立.2.2、 遗传算法的特点与其他优化技术相比,GAM有如下特点49:(1)遗传算法是对参数的编码进行操作,而不是对参数本身；(2)遗传算法通过目标函数来计算适应度,不需要其它的推导和辅助信息,从而对问题的依赖性较小；(3)遗传算法是从许多初始点开始并行操作,而不是从一个点开始.因而可以有效地预防搜索过程收敛于局部最优,而且有较大的概率求得全局的最优解；(4)遗传算法采用随机转移策略,而不是确定性原那么；(5)遗传算法在解空间内不是盲

11、目穷举或完全随机的测试,而是一种启发式搜索,其搜索效率往往优于其它方法；(6)遗传算法对于待寻优函数根本无限制,它既不要求函数连续,更不要求可微,既可以是数学解析式所表达的显函数,也可以是映射矩阵甚至是神经网络等隐函数,因而应用范围较广；(7)遗传算法具有并行计算的特点,因而可通过大规模并行计算来提升计算速度；2.3、 标准遗传算法的局限性及其改良方式近年的研究和实践说明SGAt一定的局限性.主要白问题,一是理论上SGA不能保证以概率1找到最优解；二是SGA勺收敛速度很低；第三是算法的“早熟问题,即算法可能停在局部最优解处.根据具体应用的要求,许多研究人员对SGA8行了各种形式的改良.常见的改

12、良策略有：(l)改善收敛特性：为解决收敛问题,在选择算子中采用最优保存策略.根据Markov链的性质,采用这一策略的SGAM以在理论上保证以概率1收敛到最优解上52"3.但降低了算法的随机搜索特性,算法容易出现“早熟.(2)改良适应度定义方法：适应度定义方法的改良54,使群体中的特别优秀个体不会导致算法“早熟.具体应用中遗传算子也有多种,对适应度的依赖程度也可调整.(3)优选编码方案：除了二进制编码方案,目前基于十进制和其他符号的编码方案也有很多50训.在精度上十进制比二进制好,在组合优化中也常用符号编码.不同的编码方案需要相应遗传算子来保证算法产生的后代是合法的编码.(4)采用新的

13、遗传算子：为了提升算法搜索水平,提出多种新的遗传算子.例如倒序变异算子、灾变算子55多点交叉算子以及多种选择算子等.但是,多数新算子缺乏有效性的理论根据.(5)自适应化限制参数：采用动态或自适应策略确定算子中的关键参数,提升算法的可靠性和对各类问题的适应水平527.(6)分布式及并行计算：模拟生物种群进化中的独立种族和小生境进化现象,各个独立的进化群体采用复杂的机制相互协作57上9,提升算法的寻优效果.(7)混合遗传算法：将其他优化技术与遗传算法混合使用,以提升算法的综合水平.例如,为了提升算法的全局优化水平,通常在选择机制中融合模拟退火技术59.为了提升算法在最优点附近的局部寻优水平,融合其

14、他启发式搜索或传统优化技术60.(8)新的进化机制：以广义遗传算法61为代表,在GA中引入新的生物进化机制,并试图通过解释其寻优机理来研究进化计算的理论根底.免疫算法61和蚁群算法60作为一种新的进化机制也开始应用于复杂优化问题的求解.尽管GAM有与被求解的问题特性无关的优点,但是所有从SGAa进得到的高级遗传算法,根据NFL定理62,都只能针对某些应用有效.不存在对所有优化问题普遍有效的随机搜索算法.所以在求解实际问题时往往要通过大量的计算实践来确定GA的遗传算子和限制参数.2.4、 混合遗传算法遗传算法由于其运算简单和解决问题的有效水平而被广泛应用到众多的领域.理论上已经证实,遗传算法能从

15、概率的意义上以随机的方式寻求到问题的最优解.但另一方面,应用实践说明,在遗传算法的应用中也会出现一些不尽人意的问题,这些问题中最主要的是它容易产生早熟现象、局部寻优水平较差等.并且一般来说,对很多问题而言,根本遗传算法的求解效果往往不是解决这个问题的最有效的方法,它比专门针对该问题的知识型启发算法的求解效率要差.另外,遗传算法也无法预防屡次搜索同一个可行解,这也是影响遗传算法运行效率的一个因素.另一方面,梯度法、爬山法、模拟退火算法、列表寻优法等一些优化算法却具有很强的局部搜索水平,而另一些含有问题与相关知识的启发式算法的运行效率也比拟高.可以预计,在遗传算法的搜索过程中融合这些优化方法的思想

16、、构成一种混合遗传算法(HybridGeneticAlgorithm)是提升遗传算法运行效率和求解质量的一个有效手段605.由图2可以看出,这种混合遗传算法是在标准遗传算法中融合了局部搜索算法的思想,其特点主要表达在以下两个方面：(l)引入了局部搜索过程.基于群体中各个个体所对应的表现型,进行局部搜索,从而找出各个个体在目前的环境下所对应的局部最优解,以便到达改善群体总体性能的目的.(2)增加了编码变换操作过程.对局部搜索过程所得到的局部最优解,再通过编码过程将它们变换为新的个体,以便能够以一个性能较优的新群体为根底来进行下一代的遗传进化操作.模拟退火算法在金属热加工工艺中,退火是指将金属材料

17、加热到某一高温状态,然后让其慢慢冷却下来这样一个金属热处理过程.从统计热力学的观点来说,随着温度的降低,物质的能量将逐渐趋近于一个较低的状态,并最终到达某种平衡.模拟退火算法(simulateAnnealing)66就是基于金属退火的机理而建立起的一种全局最优化方法,它能够以随机搜索技术从概率的意义上找出目标函数的全局最小点.模拟退火算法的构成要素如下：1 .搜索空间搜索空间也称为状态空间,它由可行解的集合所组成,其中一个状态x就代表一个可行解.2 .能量函数E(x)能量函数也就是需要进行优化计算的目标函数,其最小点为所求的最优解.3 .状态转移规那么P状态转移规那么是指从一个状态Xoid(一

18、个可行解)向另一个状态Xnew,(另一个可行解)的转移概率,它与当前的温度参数T有关.4 .冷却进度表T(t)冷却进度表是指从某一高温状态T.向低温状态冷却时的降温治理表.假设时刻t的温度用T(t)来表示,那么经典模拟退火算法的降温方式为：ig(i+n而快速模拟退火算法的降温方式为：这两种方式都能够使得模拟退火算法收敛于全局最小点.另外,在实际应用中,为计算简便起见,也可用下式来进行温度治理：式中,k为略小于1.0的系数.假设图3所示为某一能量函数的描述图形.如果搜索过程陷入局部最优点A,假设要使搜索过程脱离这个局部最优点而到达C点,那么必须使系统至少要具有B点所对应的能量.亦即,这里必须允许

19、能量函数值可以一时增大.I：3能量便数例如假设在状态Xoid时,系统受到某种扰动而可能会使其状态变为Xnew,.与此相对应,系统的能量也可能会从E(Xoid)变成E(X.).系统由状态Xoid变为状态XneW的接受概率可由下面的MeteopoliS规那么来确定：上式的含义是：当新状态使系统的能量函数值减少时,系统一定接受这个新的状态；而当新状态使系统的能量函数值增加时,系统也以某一概率接受这个新的状态.固定温度参数T,反复进行状态转移过程,接收概率P(x)将服从Gibbs分布:式中,Z是使概率值正规化的系数.由上式可见,随着温度参数T的减小,接收概率也逐渐减小,即能量函数增大的可能性也逐渐减小

20、,最后系统会收敛于某一能量最小的状态,该状态就可作为目标函数的全局最小值.二、参考文献1 KantorovichLV.Mathematicalmethodsoforganizingandplanningproduction(AnEnglishtranslationofaRussianpaperpublishedin1939)J.ManagementScience,1960,6:363-3662 GilmorePC,GomoryRE.ALinearprogrammingapproachtothecuttingstockproblem-partIIJ.OperationsResearch,1963

21、,11(5):863-8883 GilmorePC,GomoryRE.MultistagecuttingstockproblemsoftwoandmoredimensionsJ.OperationsResearch,1965,13(1):94-1204 CarlManeri,RobertSilverman.Avector-spacepackingproblem.JournalofAlgebra,Volume4,Issue3,November1966,Pages321-3305 M.J.Haims,H.Freeman.AMultistageSolutionoftheTemplate-Layout

22、Problem.IEEETrans.SystemScienceCybernetics,1970,SSC-6:1451516 J.C.Herz.RecursiveComputationalProcedureforTwo-dimensionalStockCutting.IBMJ.ofRes.AndDevelop,1972,16(5):462-4697 G.F.Cintra,F.K.Miyazawa,Y.Wakabayashi,E.C.Xavier.Algorithmsfortwo-dimensionalcuttingstockandstrippackingproblemsusingdynamicp

23、rogrammingandcolumngeneration.EuropeanJournalofOperationalResearch,Volume191,Issue1,16November2021,Pages61-858 Na,S.J.,Han,G.C.,Kim,D.I.,Kim,S.L.ANewApproachforNestingProblemUsingPartDecompositionTechnology.In:Proceedingsofthe23rdInternationalConferenceonIndustrialElectronics,Control,andInstrument,v

24、ol.3(1997)9 LorisFaina.Anapplicationofsimulatedannealingtothecuttingstockproblem.EurJofOperRes,1999,114,114:542-55610 V.M.M.Marques,C.F.GBispo,J.J.S.Sentieiro.Asystemforthecompactionoftwo-dimensionalirregularshapesbasedonsimulatedannealing.ProceedingsofIECON.1991,:1911-191611 A.MiguelGomes,JosF.OUve

25、ira.SolvingIrregularStripPackingproblemsbyhybridisingsimulatedannealingandlinearprogramming.EuropeanJournalofOperationalResearch,Vlume171,Issue3,16June2006,Pages811-82912 LeungTW,YungCH.Applicationofgeneticsearchandsimulatedannealingtothetwo-dimensionalnon-guillotinecuttingstockproblemJ.Computers&am

26、p;IndustrialEngineering,2001,40(3):202104.13 MhandHifi,VangelisTh.Paschos,VassilisZissimopoulos.Asimulatedannealingapproachforthecircularcuttingproblem.EuropeanJournalofOperationalResearch,Volume159,Issue2,1December2004,Pages430-44814 LiuDe-quan,TengHong-fei.AnimprovedBL-Algorithmforgeneticalgorithm

27、oftheorthogonalpackingofrectangles.EuropeanJournalofOperationalResearch,1999,112(2)413-42015 PothsJC,GiddensTD,YadawSB.Thedevelopmentandevaluationforanimprovedgeneticalgorithmbasedonmigrationandartificialselection.IEEETransonSyst,Man&Cybern,1994,241:73_,24(1):73_:8616 S.Jakobs.Ongeneticalgorithm

28、sforthepackingofpolygons.Eur.J.ofOper.Res,1996,88,88:165-181.17 AndreasBortfeldt.Ageneticalgorithmforthetwo-dimensionalstrippackingproblemwithrectangularpieces.EuropeanJournalofOperationalResearch,Vlume172,Issue3,1August2006,Pages814-83718 Han,G.-C.Na,S.-J.Two-stageapproachfornestingintwo-dimensiona

29、lcuttingproblemsusingneuralnetworkandsimulatedannealing.ProceedingsoftheInstitutionofMechanicalEngineers,PartB:JournalofEngineeringManufacture,v210,nB6,p509-519,199619 Lidong,Liang;Jiawei,Ye;Dong,Wei.Applicationofimprovedantcolonysystemalgorithminoptimizationofirregularpartsnesting.Proceedings-4thIn

30、ternationalConferenceonNaturalComputation,ICNC2021,v7,p507-510,20 Lidong,Liang;Jiawei,Ye.ASolutionofIrregularPartsNestingProblemBasedonImmuneGeneticAlgorithm.Proceedingsofthe2021InternationalSymposiumonComputationalIntelligenceandDesign,ISCID2021,v1,p217-220,202121 MarcelloBraglia.Optimizationofasim

31、ulated-annealing-basedheuristicforsinglerowmachinelayoutproblembygeneticalgorithm.InternationalTransactionsinOperationalResearch,Vlume3,Issue1,January1996,Pages37-4922 T.W.Leung,ChiKinChan,MarvinD.Troutt.Applicationofamixedsimulatedannealing-geneticalgorithmheuristicforthetwo-dimensionalorthogonalpa

32、ckingproblem.EuropeanJournalofOperationalResearch,Vume145,Issue3,16March2003,Pages530-54223 AlevSoke,ZaferBingul.Hybridgeneticalgorithmandsimulatedannealingfortwo-dimensionalnon-guillotinerectangularpackingproblems.EngineeringApplicationsofArtificialIntelligence,Volume19,Issue5,August2006,Pages557-5

33、6724 A.RameshBabu,N.RameshBabu.Agenericapproachfornestingof2-Dpartsin2-Dsheetsusinggeneticandheuristicalgorithms.Computer-AidedDesign,Volume33,Issue12,October2001,Pages879-89125 YoungHaeLee,MoonHwanLee.Ashape-basedblocklayoutapproachtofacilitylayoutproblemsusinghybridgeneticalgorithm.Computers&I

34、ndustrialEngineering,Volume42,Issues2-4,11April2002,Pages237-24826 De-FuZHANG,Sheng-DaCHEN,Yan-JuanLIU.AnImprovedHeuristicRecursiveStrategyBasedonGeneticAlgorithmfortheStripRectangularPackingProblem.ActaAutomaticaSinica,Volume33,Issue9,September2007,Pages911-91627 KevinJ.Binkley,MasafumiHagiwara.App

35、lyingself-adaptiveevolutionaryalgorithmstotwo-dimensionalpackingproblemsusingafourcornersheuristic.EuropeanJournalofOperationalResearch,Vlume183,Issue3,16December2007,Pages1230-124828 杨威,刘胜青.板材排样优化的计算智能方法研究D.中国优秀硕士学位论文全文数据库,2002,(03)29MaraCristinaRiff,XavierBonnaire,BertrandNeveu.Arevisionofrecentap

36、proachesfortwo-dimensionalstrip-packingproblems.EngineeringApplicationsofArtificialIntelligence,Volume22,Issues4-5,June2021,Pages823-82730曹炬,周济,余俊.矩形件排样优化的背包算法J.中国机械工程,1994,5(2):111231曹炬.实用矩形件排样系统的研究与开发J.锻压技术,1999,(05)32徐彦欣.基于产生式规那么的二维不规那么零件的排样算法J.小型微型计算机系统,1998,(10)33董长双,杨楚民,宾鸿赞.冲裁件二维排样优化J.锻压技术,199

37、8,(04)34周建华,赵建军,吴铺.不规那么形状零件排样的关键技术J.现代机械,1998,(02)35滕健,李滨慧,施洪生,张茵麦.用神经网络解决二维不规那么零件的排料问题J.机械设计与制造工程,1999,(06)36贾志欣,殷国富,罗阳等.矩形件排样的模拟退火算法求解J.四川大学学报(工程科学版),2001,33(5):353837贾志欣.面向发电设备制造的下料排样原理与关键技术D.四川大学,200238吴浩扬,常炳国,朱长纯,刘君华.基于模拟退火机制的多种群并行遗传算法J.软件学报,2000,(03)39曾窕俊.二维不规那么图形的排样算法D.广西师范大学,200640徐利娜.二维不规那么

38、零件排样及相关问题研究D.西北工业大学,200741宋亚男.二维排样系统的图形匹配、入排限制与碰靠算法研究D.华南理工大学,200442苏英慧.基于二维不规那么鞋片的自动排料系统研究D.浙江大学,200543相会财.基于遗传算法的二维不规那么图形排料问题的研究与应用D.沈阳工业大学,2007,(05)44赵治国,卢军,贾俐俐.遗传算法和碰撞算法混合求解冲裁件自动排样问题J.工程图学学报,2021,(01)45孙宁.人工免疫优化算法及其应用研究D.哈尔滨工业大学,200646罗小平.人工免疫遗传学习算法及其工程应用研究D.浙江大学,200247郝玲琴.基于神经网络的冲裁件优化排样算法研究D.中国

39、优秀硕士学位论文全文数据库,2007,(03)48StefanJakobs.TheoryandMethodologyOngenetiealgorithmsforthepaekingofpolygonsJ.In:EuropeanJournalofOperationalReseareh88(1996)165181.49刘曙光,费佩燕,侯志敏.遗传算法的进展与展望.现代电子技术2000,(6):8387.50张铃,张钱.遗传算法机理的研究.软件学报.2000,11(7):945952.51唐飞,滕弘飞,孙治国等.十进制编码遗传算法的模式定理研究.小型微型计算机系统.2000,21(4):364367.52唐飞,滕弘飞.一种改良的遗传算法及其在布局优化中的应用.软件学报.1999,10(10):10961102.53戴晓晖,李敏强,寇纪淞.遗传算法理论研究综述.限制与决策.2000,15(3):263268.54侯格贤,吴成柯.遗传算法的性能分析.限制与决策.1999,14(3):257-260.55胡国四,韩生廉.遗传算法