二维装箱问题的一种实现方法

二维装箱问题的一种实现方法武晓今¹　朱仲英º遗传算法(GA)是基于自然淘汰地遗传机制的搜索算法,近年来利用遗传算法解决组合优化问题的研究十分普遍。二维装箱问题是典型的组合优化问题,也是时间复杂度非常高的NP问题之一,如何实现有效的算法流程一直是该类问题的难点,本文在BL算法的基础上,提出一种改进的算法结构和流程,并分析了用GA实现过程中编码的健全性和完备性以及多样性评价问题。二维装箱问题　BL算法　GA算法　健全性完备性,,,,,;;,,,,:,,,;,,,,,,NP,,:,n,2n!,o(N2),TSP80,[1][2],1988Kampke,1995,[4],,,TSP,,GA:,,,,()1980,JacosBottom-Left(BL),1994Hwang(FFDH),1995Chen(ILP)[3],BL,,,1996JakobsBLGA[4],GABL,,,,BL,,,,,,,Bottom-Left(BL),,,,BL,,P,P,P=P(1),P(2),,P(n),:(1)rP(1);(i)rP(i),,,,1,,2-1:20MicrocomputerApplicationsVol.19,No.4,2003微型电脑应用2003194¹º200030200030图1　BL二维装箱问题图例图2　二维装箱问题的表示模型W,H,w,hr(rx,ry)BL,,(rw,rh),(rx,rx+rw)[0,W],Py,y,,Py={[rx,rx+rw]ûryyry+rh}yii,Y={0}{yûPr,y=ryy=ry+rh},2n+1,BL2n+1()BL,,2-1,41,3,:(1)rP(1);(i)rP(i),,,,,31.(structure)(class),:¹º»;:¹º图3　改进BL算法矩形移动图例2.¹,º3.BL,,,,,,,,3-1GA,,TSP,,:1.[6],(0,1),9[0.23,0.820.450.74.0.870.110.560690.78],ii,ii,:6-1-3-7-8-4-9-2-52.,[7][8]21MicrocomputerApplicationsVol.19,No.4,2003微型电脑应用2003194,,,,,:(1)GA,9,(),2:P1:912345678P2:5349728164:¹P1,P2;ºP1,P2;»P1,P2;¼P1,P2;»¼¹º,¹º¹,P1P2P'1P'2P'1:123456789P'2:534972816º,:P'1:123456789P'2:561827943(2)::P'1:123456789P'2:3459728163,(),3.:f(P)=H(P)+S(L(P))/(h(P)*W)H(P)=H-h(P),h(P),,H,,,Wh(P)*W,(4-1)(4-4)m,()n,Vk(k=1,2,,n),tU(t):U(t)=X1(t)={xt11,xt12,,xt1n}{xt11,xt12,,xt1n}X2(t)={xt21,xt22,,xt2n}Xm(t)={xtm1,xtm2,,xtmn}:v1,v2,,vn}(4-1)tV(t),:22MicrocomputerApplicationsVol.19,No.4,2003微型电脑应用2003194V(t)=1n2nk=1Vk(4-2)Fk=ekemax(k=1,2,,n)(4-3)emax=maxek1knek=2mi=12mj=1qkijqkij=1xijxjk0otherwise(4-4),,,,,,[1]B.S.Baker,E.G.CoffmanJr.,R.L.Rivest,Orthogonalpackingintwodimensions,SIAMJournalonComputing9(1980)pp.846-855.[2]Chazelle,TheBottom-LeftBinPackingHeuristic:AnEfficientImplementation,{IEEE}TransactionsonComputers32(1983),pp.697-707[3]C.S.Chen,S.M.Lee,Q.S.Shen,Aanalyticalmodelforthecontainerloadingproblem,EuropeanJournalofOperationalResearch80(1995)pp.68-76.[4]S.Jakobs,Onthegeneticalgorithmsforthepackingofpolygons,EuropeanJournalofOperationalResearch88(1996)pp.165-181.[5]钟清流,BN结构和参数算法改进,微型电脑应用,17(5):2001.5[6]徐琪等,应用遗传算法的DSS模型设计研究,微型电脑应用,18(2):2002.2[7]Goldberg,D.andR.Lingle,Alleles,lociandthetravelingsalesmanproblem,inGrefenstette,(1995)pp.154-159[8]Davis,L.,Applyingadaptivealgorithmstodomains,InProceedingsofInternationalJointConferenceonArtificialIntelligence,(1985)pp.162-164.[9]PatrickHealy,MarcusCreavin,AgoKuusik,Anoptimalalgorithmforrectangleplacement,OperationsResearchLetters24(1999)pp.73-80.(收稿日期:2002年12月31日)(上接第35页)ORACLESQLSERVERINFORMIXFOXPROACCESS,UNIX,WINDOWSLINUX4.(1)C/SB/SC/S,B/S(2)(XML),(3)EJBEJB,,(4)J2EEJAVA,JAVAJ2EE,,,J2EE,[1]钟诚、宋玲、赵明,Java动态数据结构与软构件重用技术的实现。计算机工程,1999年第25卷第10[2]SubrahmanyamAllamaraju等,J2EE服务器端高级编程,机械工业出版社,2001年9月[3]尹秋菊、甘仞初,基于WEB的混合模式信息系统研究与应用,计算机系统应用2002.3(收稿日期:2002年11月20日)23MicrocomputerApplicationsVol.19,No.4,2003微型电脑应用2003194ISSN1007-757XMicrocomputerApplicationsMonthly(Since1985)WuQidiEditor-in-ChiefVol.19.No.4(GeneralNo.120)April20032MicrocomputerApplicationsVol.19,No.4,2003ABSTRACTS&KEYWORDS微型电脑应用2003194