Page 23 - 《软件学报》2021年第12期

阳名钢 等:求解二维装箱问题的强化学习启发式算法 3687

H: a packing solution.
1 EmptyLayout only have one cave,which consists of the whole strip,with a width equal to W
2 bestSeq=null,H=∞
3 for each sortig rule do
4 sortSeq=using the sorting rule sort Seq
5 tempH=ConstructiveHeuristic(EmptyLayout.cave_list,sortSeq)
6 if tempH<H then
7 bestSeq=sortSeq
8 H=tempH
9 while the stop criterion is not satisfied do
10 tempH=HierachicalSearch(bestSeq)
11 if tempH<H then
12 bestSeq=sortSeq
13 H=SwapRandom(bestSeq)
14 return H
2 强化学习启发式算法

2.1 强化学习求解框架
启发式算法通常会存在冷启动的问题,每次运行算法都需要重新开始缓慢的爬山搜索来寻找最优解,无论
算法运行过多少次,并不能对后续的运行和搜索产生任何帮助.传统的启发式算法不存在学习或者保存原先经
验的能力,而强化学习则可以做到.强化学习是机器学习的一个重要分支,它的算法框架如图 1 所示:Agent 是智
能体,它会根据所接收的环境状态(state)采取相应的动作(action),环境会根据采取动作给予 Agent 不同的反馈
(reward);然后,Agent 根据反馈的情况调整和修正自己的行为.Agent 会反复地与环境互动进行探索和学习,目的
是使获得的奖励最大.因此,我们考虑使用强化学习的方法,通过训练模型来学习装箱经验,为启发式算法寻找
一个较优的初始序列,从而优化冷启动的问题.那么这就需要一个网络模型,能够学习根据输入的物品序列输出
一个初始装箱序列.

Fig.1 Reinforcement learning graph
图 1 强化学习示意图
指针网络非常适合解决输出序列强依赖输入序列的问题.而二维装箱问题也可以看成是序列到序列的问
题,它的装箱序列完全来自输入的物品,因此可以利用指针网络来学习输出一个合适的装箱初始序列.对于训练
好的网络模型,其优势在于当输入全新的数据时,模型可以根据学习到的经验给出一个较理想的初始序列,好的
初始序列不仅可以加快启发式搜索算法的响应速度,还可以节省爬山消耗的时间,提高算法性能.
2DSPP 主要有两个决策变量:(1) 矩形物品放入箱子的顺序;(2) 物品摆放的位置.算法 1.1 可以用于解决输
入物品的序列如何放置物品的问题,而提出的强化学习方法用于优化物品的放入顺序.
本文提出的框架是使用强化学习训练好的模型为启发式方法提供初始的装箱序列,改善冷启动问题.具体