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