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

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

的框架图 2 所示.强化学习方法是一种自我学习驱动的过程,该过程仅依赖输出序列所计算获得的奖励值来训
练网 络 . 网络模 型 ( 即图 2 中的 Net) 采 用简化 版的 指针网 络输 出一个 初始 的装箱 序列 , 然后 调 用
ConstructiveHeuristic(即算法 1.1)计算该装箱序列所获得的解,将该解获得的高度值作为奖励信号来验证网络
的可行性,根据奖励值不断的调整网络,使网络能以最大的概率输出较好的装箱序列.训练好的模型将为 HHA
提供初始序列,整体的算法本文称为强化学习启发式算法(reinforcement learning heuristic algorithm,简称
RLHA),详细的算法流程见算法 2.1.

Fig.2 Reinforcement learning heuristic algorithm framework
图 2 强化学习启发式算法框架
算法 2.1. 强化学习启发式算法.
Input:
W: the width of the strip;
Seq: unpacked sequence of rectangles;
Output:
H: a packing solution.
1 Load the trained reinforcement learning model
2 EmptyLayout only have one cave,which consists of the whole strip,with a width equal to W
3 H=∞
4 Obtaining initial solution bestSeq from reinforcement learning
5 while the stop criterion is not satisfied do
6 tempH=HierachicalSearch(bestSeq)
7 if tempH<H then
8 bestSeq=sortSeq
9 H=SwapRandom(bestSeq)
10 return H
2.2 网络模型
网络模型使用的是简化版的指针网络,该模型结构与 Nazari 等人 [27] 使用的结构一致,其框架考虑了静态和
动态的元素.针对二维装箱问题,我们仅考虑了静态元素,因为装箱问题与 VRP 不同,2DSPP 不存在动态的元素,
比如 VRP 的配送点除了坐标,还有配送点的货物量,这个值是会动态改变的.模型由循环神经网络(GRU)和注意
力机制组成,每一步把输入元素的嵌入(embedding)直接作为解码器的输入,解码器的输出会传递给注意力机制,
获得输出的概率分布.Nazari 等人 [27] 认为: 循环神经网络编码器增加了额外的复杂性,因为只有当输入需要传
递顺序信息的时候才需要循环神经网络.比如文本翻译,需要知道词的先后顺序才能准确翻译.但是在组合优化
中输入集并没有顺序之说,任何随机排列都包含与原始输入相同的信息.因此在简化版指针网络中,忽略了编码
器,直接使用了嵌入层(embedding layer)代替编码器.本文同样使用了简化版指针网络,因为通过这种修改减少
了计算的复杂性,提高了性能.