求解二维装箱问题的强化学习启发式算法
CSTR:
作者:
作者单位:

作者简介:

阳名钢(1998-),男,硕士生,主要研究领域为大数据,人工智能.
陈梦烦(1994-),女,硕士,主要研究领域为大数据,人工智能.
杨双远(1976-),男,博士,副教授,主要研究领域为人工智能,图像处理.
张德富(1971-),男,博士,教授,博士生导师,CCF高级会员,主要研究领域为大数据,人工智能.

通讯作者:

张德富,E-mail:dfzhang@xmu.edu.cn

中图分类号:

TP301

基金项目:

国家自然科学基金(61672439)


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

Fund Project:

National Natural Science Foundation of China (61672439)

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

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

    Abstract:

    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.

    参考文献
    相似文献
    引证文献
引用本文

阳名钢,陈梦烦,杨双远,张德富.求解二维装箱问题的强化学习启发式算法.软件学报,2021,32(12):3684-3697

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2020-07-14
  • 最后修改日期:2020-08-20
  • 录用日期:
  • 在线发布日期: 2021-05-21
  • 出版日期: 2021-12-06
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号