基于最小松弛量的启发式一维装箱算法

发布时间：2021-05-20 16:45

　　一维装箱问题是组合优化中的NP难问题,在有限的时间内获得问题的精确解非常困难。启发式算法和遗传算法是解决装箱问题的两类主要方法,但是,采用经典启发式装箱算法得到的结果在极端情况下非常差,而遗传算法在解决装箱问题的过程中容易出现无效解,致使需要处理的数据量十分巨大。为了获得装箱问题的近似最优解,文中针对目前的装箱问题算法展开分析,提出了一种新型的启发式装箱算法。提出的IAMBS算法允许装箱有一定的松弛量,使用随机思想搜索局部最优,进而获得装箱问题的全局最优解。随机松弛量使该算法不易陷入局部最优,具有较强的发现全局最优解的能力。采用来自两个数据集的1 410个基准测试实例进行实验。最终,IAMBS算法获得了1 152个实例的最优解。实验数据表明,IAMBS算法可以有效地获得近似最优解,比经典装箱算法更有优势。 

【文章来源】：计算机科学. 2019,46(09)北大核心CSCD

【文章页数】：6 页

【文章目录】：
1 引言
2 相关工作
3 解决装箱问题的启发式算法
    3.1 一维装箱问题的数学描述
    3.2 经典的启发式算法
    3.3 MBS算法
    3.4 MBS衍生算法
    3.5 蒙特卡洛算法和拉斯维加斯算法
4 AMBS算法
5 IAMBS
6 实验分析
    6.1 实验环境
    6.2 算法性能评价指标
    6.3 实验数据集
    6.4 实验结果



本文编号：3198093