论文部分内容阅读
本文主要研究装箱问题。装箱问题是一类非常经典的组合优化问题,其已被证实为NP难问题。装箱问题涉及的应用领域比较广泛,我们在实际生活中常常可以遇到它的踪影,如工业中物料的切割与裁剪、货物的装载和图文的排版等。此类问题一般不能采用传统的精确算法进行求解,因为当问题规模变大时,精确算法不能在有效的多项式时间内得出问题的最优解。本文将化学反应优化算法框架(chemical reaction optimization,CRO)应用于装箱问题,CRO是近年提出的拥有较好性能的元启发式算法框架。在本文中,通过改进CRO框架以适应多种类型的装箱问题,并提出两种混合元启发式算法分别用于求解一维装箱问题和二维装箱问题。本文具体工作如下:设计并实现了一种求解一维装箱问题的变种混合化学反应优化算法(hybrid chemical reaction optimization,HCRO),此算法整合经典的FF和FFD启发式算法,改进了 CRO框架的四个基本反应操作以适应一维装箱问题。算法借鉴了遗传算法的优势,保存了局部最优解列表,用于动态地加入到算法框架中,从而增加了HCRO算法的全局搜索能力。同时提出一种随机重排列过程来修复迭代过程中产生的解,这很大程度上减少算法的计算时间并提高算法的收敛性。本文将HCRO算法应用于来自多个经典数据集的1615个问题实例,HCRO算法能够求出其中的1605个实例的最优解,并平均计算时间是0.03s。同时本文对算法的收敛能力做了实验测试,结果显示了 HCRO算法具有很强的收敛能力。最后将HCRO算法分别与经典算法和近年优秀算法进行比较,结果显示HCRO在求解质量上比大多数算法表现更好,而在运行时间上也不差,这证明HCRO是一个优秀混合算法。针对二维矩形装箱问题,本文也设计了一种混合化学反应优化算法(chemical reaction optimization with bottom-left-fill,CRO+BLF)。该算法利用了 CRO 框架优秀的搜索能力和收敛能力,并整合了经典的BLF放置策略。其中CRO框架用于搜索问题的解,而BLF策略用于对分子结构进行解码,从而完成问题的装箱。本文改进CRO算法的四个基本反应,结合了经典的相邻搜索和交叉技术,然后在每种反应结束后采用BLF算法完成装箱并求出装箱高度。本文同时编程实现另外两种经典优秀的混合算法:GA+BLF和SA+BLF,并将这些算法应用于经典的C类和N类数据集。实验结果证明,在C类数据集上,CRO+BLF优于另两种算法;在N类数据集上,CRO+BLF优于GA+BLF算法;在N类数据的某些子集上,CRO+BLF优于SA+BLF算法。特别在大规模实例上CRO+BLF表现得更佳。