求解二维装箱问题的强化学习启发式算法

来源：软件学报杂志2021年第12期北京时间：

作者：阳名钢，陈梦烦，杨双远，张德富

单位：阳名钢，厦门大学 信息学院, 福建 厦门 36100511,陈梦烦，厦门大学 信息学院, 福建 厦门 36100502,杨双远，厦门大学 信息学院, 福建 厦门 36100503,张德富，厦门大学 信息学院, 福建 厦门 36100504

摘要：二维带形装箱问题是一个经典的NP-hard的组合优化问题，该问题在实际的生活和工业生产中有着广泛的应用.研究该问题，对企业节约成本、节约资源以及提高生产效率有着重要的意义.提出了一个强化学习求解算法.新颖地使用强化学习为启发式算法提供一个初始的装箱序列，有效地改善启发式冷启动的问题.该强化学习模型能进行自我驱动学习，仅使用启发式计算的解决方案的目标值作为奖励信号来优化网络，使网络能学习到更好的装箱序列.使用简化版的指针网络来解码输出装箱序列，该模型由嵌入层、解码器和注意力机制组成.使用Actor-Critic算法对模型进行训练，提高了模型的效率.在714个标准问题实例和随机生成的400个问题实例上测试提出的算法，实验结果显示：提出的算法能有效地改善启发式冷启动的问题，性能超过当前最优秀的启发式求解算法.

关键词：二维装箱问题;强化学习;指针网络;启发式算法;分层搜索

基金资助：国家自然科学基金（61672439）