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

摘要：

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

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

所属期刊栏目：32

分类号：TP301(计算技术、计算机技术)

在线出版日期：2021-12-13（万方平台首次上网日期，不代表论文的发表时间）

页数：共14页

页码：3684-3697