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

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

生成 400 000 组数据;(2) 矩形块数为 100 生成 300 000 组数据;(3) 矩形块数为 50 的块数共生成 300 000 组数
据.同时生成 100 000 组数据集作为测试样本.通过随机种子生成较大的训练数据集,是为了能尽可能地涵盖不
同的样本,使得模型能学习到丰富的样本.

3.2 实验环境和参数设置
强化学习模型主要通过 pytorch 实现,实验运行环境如下:Ubuntu 16.04 LST,处理器为 Intel Core E5-2620 v4,
处理器频率 2.10GHz,内存 62G,显卡为 NVIDIAGeForceRTX2080Ti,显存为 11G.
在实验中,我们使用了 1 000 000 组的训练数据和 100 000 组的测试数据.在实验过程中,每批训练的样本量
是 128,解码器中 GRU 的隐层单元数量为 128,输入数据也将被嵌入到 128 的向量中.本文使用 Xavier [38] 初始化
方法对 Actor 和 Critic 网络进行初始化,使用 Adam 优化器,学习速率为 0.0001,同时,为了防止过拟合的问题,使
用了 L2 范数对梯度进行裁剪.在解码器中使用了 0.1 的 dropout,dropout 可以比较有效地缓解过拟合的产生.模
型在单个 GPU 上训练 1 000 个时期.
训练好的模型将为 HHA 提供初始解,接下来,我们将把 RLHA 和目前优秀的启发式算法 GRASP [17] ,SVC [32] ,
ISA [19] ,SRA [20] ,CIBA [21] 和 HHA [22] 算法进行实验对比,验证算法的效果.每个算法将在所有的数据集上运行 10
次,每个实例的运行时间限制为 60s,部分大规模数据集运行时间会超过 60s.对比算法的实验结果直接取自原文
献(原文献中的参数设置都是原作者通过实验选择的最优参数),以保证算法对比的公平性.
3.3 实验结果
为了验证 RLHA 的有效性,我们将训练好的模型框架同当前著名的启发式算法进行对比分析.本节进行对
比分析的实验数据一部分来自标准的数据集,为了更合理地说明 RLHA 的性能,另一部分是由算法 3.1 和算法
3.2 生成的数据.由于训练的数据集与强化学习的算法性能还是存在一定关联的,因此另一部分实验分析将在数
据生成算法生成的数据上进行,可以更客观的展现算法的性能.
(1) 标准数据集的对比分析
[9]
我们将在 C [12] ,N ,NT [33] ,2SP [17] ,BWMV [34,35] 和 Nice&Path [36] 这 6 个标准数据集上进行实验(见表 1),对比 7
个算法的实验效果,用粗体标出最佳解的数据.之所以没有考虑标准数据集 ZDF [37] 的原因在于:这个数据集存在
大规模的实例,目前强化学习模型在处理大规模的实例时,运行时间会过长.由于计算能力和运行时间的限制,
这两个包含大规模问题实例的数据集就不做实验分析.
Table 1 Benchmark data
表 1 标准数据集
Dataset Instances n zero-waste
C 21 16~197 Yes
N 13 10~3152 Yes
NT 70 17~199 Yes
2SP 38 7~200 No
BWMV 500 20~100 No
Nice&Path 72 25~5000 No

从表 2 的实验结果可以看出,RLHA 在 N 数据集上的表现同 HHA 表现一样.N 数据集是一个零浪费率的数
据集,我们的算法在大部分实例上都已经取得最优解,因此两个算法在这个数据集上表现并无差别.RLHA 在
2SP 数据集上的表现与 HHA 获得的结果持平.出现这个情况的原因可能与该数据的特点有关系,该数据矩形个
数较少且存在一些比较特殊的实例,需要更精细的策略来改善.我们的启发式设计的规则在这个数据集上的表
现可能陷入了瓶颈,因此并没有取得更优的结果.对其余数据集,RLHA 均超过了 HHA,在所有数据集的表
现,RLHA 均显著超过了其他 5 个算法.
RLHA 在 C,NT,BWMV,Nice 和 Path 上的表现都比 HHA 略提升了一些,虽然提升的幅度不大,但是可以看
到,强化学习模型的加入的确提升了实验结果.这也可以说明强化学习模型能有效地改进启发式获得解的质量.