用自适应遗传算法解二维装箱问题

《用自适应遗传算法解二维装箱问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、维普资讯http://www.cqvip.com第25卷第7期计算机应用与软件VoI．25No．72008年7月ComputerApplicationsandSoftwareJu1．2008用自适应遗传算法解二维装箱问题蒋金山林正春(华南理工大学数学科学学院广东广州510640)摘要二维装箱问题是一个NP难问题，用遗传算法来求解任意形状的二维装箱问题。算法模拟生物在面对恶劣环境时的行为，使得交叉率和变异率具有自适应性，克服了人工设定交叉率和变异率的不足；针对个体间适值差相对较小，新产生的好的染色体易丢

2、失的特点，改进了随机选择个体的方法；算法还改进了适值函数，使得收敛速度有了较大的提高。此外，该算法与箱子的具体形状及物体的具体形状无关，当物体的数量增加和箱子与物体形状的复杂程度提高时，收敛速度仍然较快。关键词二维装箱遗传算法自适应任意形状SOIDG2DBIN-PJClNGPROBLEMBASEDoNSELF．ADAITVEGE】旧CAIDRI1=1}IMJiangJinshanLinZhengchun(SchoolofMathematicalSciences，SouthChinaUnivemi0，o

3、fTechnology，GMnOU510640．Guangdong．China)Abstract2Dbin—packingproblemisaNP—hardproblem．Aself-adaptivegeneticalgorithm，whichcanadjustthecrossoverrateandthemutationratebyitself，isproposedinthispapertoresolvethisprobleminarbitraryshapesbysimulatingtheactivi

4、tyofthebiologyconfrontingbadenvironments．Sotheshortageofartificialsettingisovercome．Themethodforrandomchoosingprocessingisimprovedtoprotecttheelitesfrombeinglosinginthenewgroupbystrengtheningthediferencesoffitnessvaluebetweeneachindividua1．Theconvel’gen

5、tspeedoftheproposedalgorithmisimprovedbyalteringthefitnessfunction．Inaddition，theproposedalgorithmissuitabletoarbitraryshapesandbins．AnditsconvergentspeedisstillveryfastwhenthequantityandcomplexityofshapesareincreasedKeywords2Dbin—packingproblemGenetica

6、lgorithmSelf-adaptiveArbitraryshape箱问题等价于式(1)一式(4)。0引言maxP(Ⅱl，Ⅱ2，。一，Ⅱ，．)(1)s．t．Ⅱ。=(，，0。)i=1，2，⋯，n(2)装箱问题是一个经典的组合优化问题，属于NP难问题，有(．，Y)∈Di=1，2，⋯，H(3)着广泛的应用。关于一维装箱问题已有许多报道，而有关二维0∈[0，360)i=1，2，⋯，n(4)装箱问题(2Dbin—packingproblem)的报道则相对较少。二维其中，p(，五：，⋯，)为适值函数物体旋转的角

7、度为0，旋装箱问题广泛应用于服装业，航空航天和计算机的存储分配中。转中心为(，Y)，本文算法中旋转中心的取法如图1所示。箱以往的研究主要是考虑特定形状的箱子和物体，考虑特定子的坐标系如图1所示。当所有的物体都放人箱子中且不重叠的旋转角度(9o。的倍数)，并得到了较好的结果；文献[6]时，适值达到最大值，记为max—fitness，该值可预先计算得到。考虑了任意形状物体所占的矩形区域和任意的旋转角度，用多匹配的方法得到了很好的结果，但该方法受物体形状的复杂程度影响。文献[7]考虑了物体的任意形状和旋转度

8、，并用遗传算法在1000代后得到了较好的结果，通过设定罚参数，较好地口解决了物体越界问题，但物体重叠问题没有得到很好的解决，且算法中的交叉率和变异率不是自适应的。文献[7]用中轴变换得到的图形骨架计算适值来达到减少计算量的目的，但骨架的提取受到物体形状的影响。受文献[7]的启发，本文提出了一种改进的遗传算法，在200代内得到了更好的结果，且每代的计2用自适应遗传算法求解算速度较快。对于第i个图形，考虑三个基因(，，。，0)，共n对基因，采1问题描述用十进