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

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

11 calculate reward R = ( R Y X 0 n )
n
,
n
// calculate the actor network gradient
1 N
12 dθ (R − ∑ n V (X ω = 0 n ; )) ∇ θ log ( P Y n | X 0 n )
N n= 1
// calculate the critic network gradient
2
13 dω 1 N ∇ = (R − ∑ V (X ω n ; ))
N n= 1 ω n 0
// update the network parameters
14 update θ using dθ and ω using dω
2.3.2 探索机制
强化学习的探索机制会直接影响采样的性能,本文在模型的训练阶段,会通过根据概率分布按概率进行随
机采样下一步作为输出.在测试期间采用的是贪婪的方法,选择概率分布中概率最高的输出.

3 计算结果

为了验证强化学习启发式算法并评估其有效性,本小节将进行一系列实验分析.首先阐述了实验数据的生
成方法,然后对实验环境和参数设置进行说明,最后对实验结果进行分析.
3.1 实验数据
由于现有的标准数据集都是较为零散且实例的数量较少,目前缺少较大量的装箱问题的数据集来用于强
化学习模型的训练,因此本文采用了 Bortfeldt 和 Gehring [30] 提出的装箱数据生成算法以及 Wang 和 Valenzela [31]
提出的装箱数据生成算法.
Bortfeldt 和 Gehring [30] 生成数据的思路是:通过一些参数,控制生成的矩形的数量、大小、宽高比以及面积
比等.该算法生成的数据是非零浪费率的,因此我们无法知道生成的数据的最优解.算法 3.1 是该算法的流程,该
算法需要输入 6 个参数:wC 表示矩形条的宽度;n 表示矩形总个数;nt 表示要生成的矩形的种类; Δ g 和ρ g 这两个
参数是用于计算矩形的最大边长和最小边长;最后,seed 是随机种子.γ是异质性比,等于 nt/n.首先,算法根据输入
的参数计算生成矩形的边长范围[dmin g ,dmax g ],然后根据随机种子初始化随机数生成器.再循环 nt 次生成 nt 个
类型的矩形 rects,矩形长宽的范围介于[dmin g ,dmax g ].最后,循环 n 次生成 n 个矩形 rect_list,rect_list 依照
rect_list[i]=rects[i%nt],0≤i<n 的规律生成.
算法 3.1. 数据生成算法 1.
Input:
wC: the width of the strip;
n: thenumber of rectangles;
nt: the number of rectangle types;
Δ g ,ρ g ,seed;
Output:
rect_list.
1 dav g =wC/Δ g
2 dmin g =2*dav g /(1+ρ g )
3 dmax g =dmin g *ρ g
4 initialize random number generation by seed
5 rects,rect_list
6 for 0→nt do
7 randomly generated w,w∈[dmin g ,dmax g ]