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

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

Table 2 Computational results on benchmark data
表 2 标准数据集的实验结果
average_gap_rate (%)
Dataset
GRASP SVC ISA SRA CIBA HHA RLHA
C 0.95 1.03 0.76 0.69 0.58 0.39 0.32
N 0.96 0.63 0.41 0.23 0.13 0.12 0.12
NT 2.32 2.27 2.24 1.60 1.37 0.97 0.96
2SP 2.68 2.80 3.02 3.07 2.87 2.7 2.7
BWMV 1.77 1.80 1.66 1.63 1.55 1.45 1.42
Nice 1.84 1.14 1.00 0.54 0.56 0.56 0.54
Path 1.68 1.00 0.77 0.40 0.35 0.35 0.34
Average 1.74 1.43 1.35 1.13 1.04 0.93 0.91
值得注意的是:由于目前现有的针对组合优化问题提出的神经网络模型 [26−28] 在解决 TSP、VRP、装箱等问
题时,其数据集规模大部分都是针对少于 200 个节点的问题实例.这是由于处理大规模实例的数据集时会导致
模型训练的时间过长.由于实验条件等限制,本文训练数据集的矩形块数分别是 50,100,200.本文的强化学习模
型与解决问题的规模是无关的,也就是说,可以把训练好的模型用于不同规模的数据集上.我们将训练的模型用
于处理矩形块数为 1000~5000 的数据集 Nice 和 Path,从表 2 中 Nice 和 Path 的实验结果可以看出:虽然模型并
没有训练过矩形块数大于 200 块的数据集,但是训练之后的模型在中小规模的数据集上的表现也有一定的提
升.这也说明模型可以根据保存的装箱经验,为启发式算法提供一个有效的初始解序列,帮助算法更好地运行,
提高算法性能.
(2) 生成数据集的对比分析
表 3 是生成数据集的明细,分别生成矩形块数为 50,100,200 以及 1 000 的数据集各 100 组,用于对比实验的
数据集.由于算法 3.1 生成的数据集的最优解不确定,因此这里分别将算法在这 4 组数据上运行,将获得的最优
解的装箱高度的平均值作为比较指标.表 4 为实验的结果,avg_height 表示装箱高度的平均值,更优的解将用粗
体标出.
Table 3 Details on generated data set
表 3 生成数据集明细
Dataset Instances n
Test50 100 50
Test100 100 100
Test200 100 200
Test1000 100 1 000

Table 4 Computational results on generated data set
表 4 生成数据集实验结果
average_height
Dataset
HHA RLHA
Test50 1 263 1 263
Test100 4 965.60 4 959.79
Test200 1 275.05 1 239.8
Test1000 1 246.29 1 242.98
Average 2 187.48 2 176.39
上节实验结果表明,HHA 和 RLHA 显著的超过了其他 7 个算法.这节只将两个最好的 HHA 和 RLHA 算法
进行对比.表 4 是 HHA 和 RLHA 在 4 组数据集上获得的平均装箱高度的数据,从中可以看出:在数据集 Test50
上,HHA 和 RLHA 获得平均装箱高是一样的.这是因为在较小的数据集上,两个算法框架的搜索能力都足够,因
此实验表现一样.在数据集 Test100,Test200 和 Test1000 上,RLHA 的表现均优于 HHA 的表现,说明了训练的强
化学习模型能使 HHA 获得更好的性能.
图 5 是 Test200 某个实例上分别运行 RLHA 和 HHA 的结果,两个算法分别运行 240 秒,每秒钟输出当前获
得最优解的值.图中横坐标是时间(s),纵坐标是最优解的值,也就是装箱的高度.从图中曲线趋势我们可以观察
到:RLHA 获得的初始解比 HHA 获得的初始解更好,虽然开始优势并不是特别明显,但经过一段时间的运