论文部分内容阅读
二维矩形装箱问题(2-DimensionalRectangularPackingProblem,2DR-PP)属于典型的组合优化问题,在工业领域有着广泛的应用,如新闻组版、布料切割、金属下料等。理论上,该问题属于NPC(NondeterministiePolynomialTimeComplete)问题,其复杂度随着问题规模的扩大呈指数增长。目前,针对2DR-PP,出现了基于不同策略的各种算法,这些算法可以分为三类:精确算法、启发式算法以及超启发式算法。虽然这些算法取得了较好的效果,但是其有效性仍有待提高。因此,进一步开展对二维矩形装箱问题的研究既具有工程应用价值又具有重要的理论意义。
本文提出了一种混合算法,即将该改进的遗传算法(ImprovedGeneticAlgorithm,IGA)与底部左齐择优匹配(Lowest-levelLeftAlignBest-Fit,LLABF)算法相结合来解决2DR-PP。首先,本文对遗传算法进行了改进,即在分析双点交叉和变异操作存在偏向性的基础上,提出了环形交叉算子和环形变异算子,并从数学上证明了该算子对各个基因位置上基因被选中概率的均等性。使用该算子,可使遗传算法的搜索范围更加有效地扩展至整个解空间,从而在一定程度上避免早熟现象的发生。三组对比实验结果也进一步证明了IGA算法的有效性。其次,本文在分析经典布局算-BL、IBL、BLF以及BF算法一的基础上,设计出了一种新的启发式布局算法LLABF。LLABF算法遵循最佳匹配优先原则,即在对矩形的装入过程中,综合考虑完全匹配优先、宽度匹配优先、高度匹配优先及可装入优先等启发式规则。与BL、IBL、BLF、BF等启发式算法相比,LLABF具有以下几个特征:1)LLABF能够在矩形装入过程中自动选择与可装区域相匹配的下一个待装矩形;2)LLABF并不总是将所有较大的矩形优先装入;3)LLABF针对的是某种模式,满足该模式的矩形装入序列,其装箱结果是完全相同的。
为了证明IGA+LLABF算法对二维矩形装箱问题的有效性,本文从不同侧面对该算法进行了对比实验。首先将该算法应用于二维矩形条带装箱问题(2DR-SPP),对该问题的实验分为二部分,一是针对零浪费的实验,主要采用了文献中给出的四组标准数据集;二是针对一般问题的实验,采用了文献中给出的标准数据集与计算机随机生成的数据集两组。其次将该算法应用于二维宽高固定装箱问题(2DR-BPP),对该问题实验所用的标准数据集一组来自文献,一组由计算机随机生成。对二维矩形装箱问题的所有实验皆表明了,相对于已有算法,IGA+LLABF算法具有明显的优势。
最后,本文将该算法运用于图集的自动排版中,由于算法本身具有的优越性,使得图集排版无论在时间上还是效果上都能基本满足工程上的需要。