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

Reinforcement Learning Heuristic Algorithm for Solving the Two-dimensional Strip Packing Problem

作　　者：阳名钢 陈梦烦 杨双远 张德富[1] YANG Ming-Gang;CHEN Meng-Fan;YANG Shuang-Yuan;ZHANG De-Fu(School of Informatics,Xiamen University,Xiamen 361005,China)

机构地区：[1]厦门大学信息学院,福建厦门361005

出　　处：《软件学报》2021年第12期3684-3697,共14页Journal of Software

基　　金：国家自然科学基金(61672439)。

摘　　要：二维带形装箱问题是一个经典的NP-hard的组合优化问题,该问题在实际的生活和工业生产中有着广泛的应用.研究该问题,对企业节约成本、节约资源以及提高生产效率有着重要的意义.提出了一个强化学习求解算法.新颖地使用强化学习为启发式算法提供一个初始的装箱序列,有效地改善启发式冷启动的问题.该强化学习模型能进行自我驱动学习,仅使用启发式计算的解决方案的目标值作为奖励信号来优化网络,使网络能学习到更好的装箱序列.使用简化版的指针网络来解码输出装箱序列,该模型由嵌入层、解码器和注意力机制组成.使用Actor-Critic算法对模型进行训练,提高了模型的效率.在714个标准问题实例和随机生成的400个问题实例上测试提出的算法,实验结果显示:提出的算法能有效地改善启发式冷启动的问题,性能超过当前最优秀的启发式求解算法.The two-dimensional strip packing problem is a classic NP-hard combinatorial optimization problem,which has been widely used in daily life and industrial production.This study proposes a reinforcement learning heuristic algorithm for it.The reinforcement learning is used to provide an initial boxing sequence for the heuristic algorithm to effectively improve the heuristic cold start problem.The reinforcement learning model can perform self-driven learning,using only the value of the heuristically calculated solution as a reward signal to optimize the network,so that the network can learn a better packing sequence.A simplified version of the pointer network is used to decode the output boxing sequence.The model consists of an embedding layer,a decoder,and an attention mechanism.Actor-critic algorithm is used to train the model,which improves the efficiency of the model.The reinforcement learning heuristic algorithm is tested on 714 standard problem instances and 400 generated problem instances.Experimental results show that the proposed algorithm can effectively improve the heuristic cold start problem and outperform the state-of-the-art heuristics with much higher solution quality.

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]