矩形件排样问题的遗传算法求解

1912Vol.19No.12199812MINI-MICROSYSTEMSDec.1998*刘德全*　滕弘飞(CAD/CAM110003)*(116024)本文研究了求解矩形件正交排样优化问题的遗传算法。同时,将矩形件正交排样问题转化为一个排列问题,提出了求一个排列所对应的排样图的下台阶算法(改进的BL算法)将下台阶算法与遗传算法相结合,用于矩形件排样问题的求解,给出了该算法的实现。用该算法对文献中的两个算例进行了求解,结果表明该算法获得了比BL算法更好的解,是一种较为行之有效的方法。O2241,,,,,,11,2,,NP,,,,,17,(),5,,,BL,,,11997-09-26*(69573004),,1965,,,CAD/CAM,,1936,,CAD/CAM,BL,,5,,5,2BL,,BL(Bottom-Leftcondition),,,BLBL,5,3,,,8,9,P={p1,p2,p3,,pn},n,pi,,1ûpiûn,,pi90,()4(),,(),,,5BL:¹p1,p190,ºpi(i=2,3,,n),pi,,,pi(),,,2,,BL,º,BL:¹p1,p190,ºpi(i=2,3,,n),pi,,pi(),,,2112:3,,,2BL3,BL,BL1,P={-1,2,3,4,-5,6,7,8).5n,n!2nn4n!,,n!2n,n!2n,,4,,,n=25,25!2251025107.5103266.1,,,,,,,5,,,P2P1,P2,,,f(P)=H(P)+Aera/(h(P)Width),H(P)=H-h(P),h(P),H,,H(P);Area,Width,h(P)Width6.22219986.2.1　初始化m,,5,,6.2.2　交叉算子m,,m,:P={p1,p2,,pn}Q={q1,q2,,qn},1npq,p,PqPøq,n-qQPø,Pø,Qø6.2.3　变异算子,,pm1;,1npq,pm2pq6.2.4　选择算子m,,m6.2.5　终止准则º»¼,,,7,562571154025,6,,Popt={1,-9,11,-15,17,-24,-25,-22,-23,-10,-14,18,-2,-3,-5,7,-8,-12,19,-20,21,16,13,4,6}40,2312:517,5,:n=25,m=20,Width=40,H=40,pm1=0.4,pm2=0.4,10016,72154050,8,,Popt={-1,2,-14,-16,-23,-24,-27,-28,30,-49,-50,29,47,-48,22,-25,-26,31,32,45,46,3,5,-11,13,15,21,12,18,20,-33,34,-38,42,43,44,-39,-40,-41,-35,36,37,4,6,-9,-10,17,19,7,8}40,517,5,:8509n=50,m=20,Width=40,H=40,pm1=0.4,pm2=0.4,100.16,9,,5,90%,8,,241998(BL),,5,,,,,1M.AdamowiczandA.Albano.Asolutionoftherectangularcutting-stockproblem.IEEETrans.onSys.Man.andCybernetic,1976,SMC-6(4):302-3102...1989,11(2):11-143...1995,7(3):190-1954B.Bengtsson.Packingrectangularpieces----AheuristicApproach.TheCmputerJournal,1982,25(3):353-3575S.Jakobs.Ongeneticalgorithmsforthepackingofpolygons.Eur.J.ofOper.Res.,1996,88:165-1816....1995,20(4):19-227...1995,35(4):487-4928D.B.fogel.Anintroductiontosimulatedevolutionaryoptimization.IEEETrans.onNeuralNetworks,1994,5(1):3-149...1995,22(2):47-5ONGENETICALGORITHMFORTHEORTHOGONALPACKINGOFRECTANGLESLIUDequanTENGHongfei(OpenLaboratoryofCAD/CAMTechnologyforAdvancedManufacturing,AcademiaSinicaShengyang110003)(DepartmentofMechanicalEngineering,DalianUniversityofTechnologyDalian116024)AbstractThispaperstudiesthegeneticalgorithmfortheorthogonalpackingofrectangles.A'downstairs'algorithmfordecodingpermutationofrectanglestopackingpattern(im-provedBLalgorithm)ispresented.Theimplementationofgeneticalgorithmfortheorthog-onalpackingofrectanglesisdiscussed.Bycomparing,thesolutionsoftwonumericalexam-plesshowtheeffectivenessofthisalgorithm.KeywordsRectangleOrthogonalpackingproblemGeneticalgorithm2512: