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

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

本文的网络模型如图 3 所示,该模型由两个部分组成.首先,嵌入层(embedding)对输入的序列嵌入映射成 D
维的向量空间,使用的是一维卷积层对输入进行嵌入;右边是解码器保存序列的信息,它将利用注意力机制将解
码器的隐藏状态和嵌入的输入指向一个输入元素.

Fig.3 Network model
图 3 网络模型示意图
设输入集为 X={x i ,i=1,…,N},其中,x i =(w i ,h i )是个元组,表示每个物品的宽度和高度.X t 表示在 t 时刻所有输入
的状态集合.从任意的输入 X 0 开始,使用指针 y 0 指向该输入,每一次解码时刻 t,y t+1 将指向当前可用的输入 X t 中
的一个,并将其作为下一个解码器的输入.如此重复,直到所有的序列都被输出.整个过程将产生一个装箱序列,
高度同输入相等为 N,Y={y t ,t=1,…,N}.模型是要找到随机策略π,使得在满足问题约束的同时最小化损失目标的
方式生成序列 Y.我们要做的就是:使得π尽量的接近最优解π′,尽量以百分百的概率生成最优解.使用概率链规
则分解生成序列 Y 的概率 P(Y|X 0 )表示如下:
T
) =
PY 0 ∏ ( P y t+ 1 | ,Y X t ) (1)
(| X
t
t= 0
在解码器的每一步,使用注意力机制生成下一个输入的概率分布.设 x 是嵌入式输入 i,h t 是解码器在 t
it
时刻隐藏层的状态,对齐向量 a it 表示输入的序列在下一个解码时刻 t 中的相关程度,公式如下:
a it =softmax(e it ) (2)
e = v T tanh(W [ ; ])x h (3)
it a a it t
这里的对齐模型采用 concat 映射,“;”表示拼接两个向量.上下文向量 c t 计算公式如下:
t ∑
c = N a x (4)
it it
i= 1
结合 c t 和嵌入式输入,然后使用 softmax 函数归一化结果可得:
( P y t+ 1 | ,Y X = softmax ( )e it (5)
)
t
t
e = v c T tanh(W c [ ; ])x c t (6)
it
it
T
,
其中, vv c T ,W a ,W 是训练参数.
a
c
2.3 模型训练
2.3.1 Actor-Critic
为了训练网络模型,本文采用强化学习的方法.我们使用基于策略梯度的强化学习来优化网络参数θ.策略
梯度的思路是:使奖励越大的动作出现的概率变大,通过反复训练,不断地调整网络参数.本文选择 Actor-Critic
的方法来训练网络,相比传统的策略梯度下降方法,它有以下优点:(1) Actor-Critic 使用了策略梯度的方法,可以
在连续动作或者高维的动作空间中选择适合的动作,采用值函数的方法是做不到的;(2) Actor-Critic 相比单纯的
策略梯度的方法,它结合 Q-learning 的做法,使得 Actor-Critic 可以做到单步更新,比起单纯的策略梯度的回合更
新效率更高.
Actor-Critic 是由两个网络 Actor(执行者网络)和 Critic(评论者网络)组成,如图 4 所示.Actor 网络是基于概