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

3686 Journal of Software 软件学报 Vol.32, No.12, December 2021

模型,并用该模型求解了各类型的 TSP 和 VRP,以及其他组合优化问题.Hu 等人 [29] 提出了新型的 3D 装箱问题,
受到深度强化学习(DRL),尤其是指针网络在组合优化问题上的应用启发,使用 DRL 方法来优化要装填的物品
的顺序,结合启发式算法,将网络的输出序列转换成解决方案,用于计算奖励信号,实验结果优于之前精心设计
的启发式算法.
可以看到,强化学习在组合优化问题上的研究和应用处于初步研究阶段,性能还不是很好,但是新的思路不
断涌出,研究人员也都在尝试能设计更好的模型来解决组合优化问题.目前,强化学习框架的研究大多只在小规
模的数据集上获得较为良好的解,如果问题规模增大,信息量爆炸,网络存储能力有限,可能无法获得理想的解.
本文研究了如何利用强化学习来生成一个好的初始解,最终提出了强化学习启发式算法,计算结果表明,提
出的方法超过了当前最优秀的算法.最后,也研究了不同初始化策略的影响.

1 启发式算法

由于强化学习需要奖励机制,本文利用构造性算法获得的高度作为奖励机制.矩形的选择方法是整个构造
性启发式算法的关键.本文采用文献[22]提出的矩形选择策略——δ评分规则.算法 1.1 详细地介绍了基于δ评分
规则和红黑树的构造性启发式算法的过程.算法中将迭代放置所有的矩形,在每次选择一个放置空间时,会先判
断放置空间是否可用,否则会进行 cave smooth 操作,将不可使用的空间合并到 y 坐标差异较小的相邻 cave.详细
的构造性启发式算法的介绍见文献[22].
算法 1.1. 构造性启发式算法.
Input:
Layout.cave_list represents all caves in the layout;
Seq: unpacked sequence of rectangles;
Output:
H: a packing solution,which indicates the current highest y-coordinate of packed rectangles.
1 w=the current smallest width of Seq
2 Create two red-black trees based on Seq,T whi and T hwi
3 while Seq.length>0 do
4 get the lowest and most left cave C from Layout.cave_list
5 if C.w<w then
6 cave smooth
7 continue
8 R=RectangleSelection(C,T whi ,T hwi )
9 pack R into the cave C
10 cave smooth if necessary
11 update H
12 return H
文献[22]提出的混合启发式算法 HHA 取得了不错的结果,但是需要一个好的初始解.本文用强化学习帮助
HHA 找到一个更好的初始解.在此给出 HHA 的算法流程,见算法 1.2.其中涉及的函数如构造性算法
ConstructiveHeuristic、分层搜索 HierachicalSearch 等,见文献[22].
算法 1.2. HHA 框架.
Input:
W: the width of the strip;
Seq: unpacked sequence of rectangles;
Output: