Page 245 - 《软件学报》2025年第8期

3668 软件学报 2025 年第 36 卷第 8 期

表 4 在 NDR 实例上的实验结果

CPLEX MWCDS MA GRASP GRASP_impLS FPLS
实例 |V| |E|
Solu Stat Best Avg Time Best Avg Best Avg Best Avg Best Avg
ba_1k_30k 1 000 30 039 N/A N/A 114 121.5 <0.01 34 35.2 21 21.7 21 21.0 21 21.0
ba_1k_6k 1 000 5 964 N/A N/A 273 284.0 <0.01 172 176.0 89 133.3 82 83.0 79 79.9
c-fat200-1 200 1 534 N/A N/A 18 18.0 <0.01 18 18.0 18 18.0 18 18.0 18 18.0
DD_g140 560 2 710 N/A N/A 164 167.6 <0.01 137 137.5 131 137.0 131 131.6 118 118.7
DD_g142 288 1 290 N/A N/A 88 90.6 <0.01 73 73.5 72 73.3 70 71.0 64 64.0
DD_g143 414 2 088 N/A N/A 112 116.4 <0.01 93 94.2 96 98.2 91 91.3 83 83.9
DD_g144 288 1 514 N/A N/A 77 79.3 <0.01 60 60.2 60 60.0 58 58.0 56 56.1
DD_g145 404 2 320 N/A N/A 96 99.7 <0.01 76 76.8 79 79.3 74 74.6 70 70.8
DD_g146 327 1 506 N/A N/A 95 99.2 <0.01 77 79.0 78 79.4 76 76.5 69 69.8
delaunay_n11 2048 6 127 N/A N/A 515 520.7 0.01 458 459.0 394 395.6 387 388.0 333 335.4
delaunay_n12 4 096 12 264 N/A N/A 1 034 1 043.5 0.03 965 969.0 801 803.7 786 791.3 681 683.3
delaunay_n13 8 192 24 547 N/A N/A 2 062 2 090.3 0.13 2003 2 004.0 1 596 1 751.6 1 635 1 721.5 1 369 1 375.0
DSJC500-5 500 125 248 N/A N/A 8 8.8 <0.01 5 5.0 5 5.0 5 5.0 5 5.0
er_graph_1k_6k 1 000 6 000 N/A N/A 198 213.1 <0.01 153 158.0 127 127.3 118 118.6 108 109.4
socfb-Haverford76 1 446 59 589 N/A N/A 190 206.2 0.01 115 116.2 101 103.3 85 89.0 58 58.5
str_0 363 2 454 N/A N/A 104 127.7 <0.01 59 60.0 58 58.7 57 57.0 55 55.0
str_200 363 3 068 N/A N/A 102 110.8 <0.01 52 53.2 50 50.7 48 48.3 47 47.0
str_400 363 3 157 N/A N/A 106 113.4 <0.01 53 53.8 51 51.0 48 48.0 46 46.0
str_600 363 3 279 N/A N/A 98 108.2 <0.01 44 46.5 44 45.1 42 42.3 41 41.0
SW-1000-6-0d3-trial3 1 000 3 000 N/A N/A 267 278.7 <0.01 227 227.5 197 197.9 183 183.4 168 168.6
SW-100-6-0d3-trial3 100 300 N/A N/A 26 27.3 <0.01 16 16.0 16 16.0 16 16.0 16 16.0
t3dl_a 20 360 265 113 N/A N/A 2 219 2 262.0 1.12 2 089 2 108.5 1 368 1 884.0 1 415 1 636.0 1 044 1 049.4
tube1 21 498 459 277 N/A N/A 1 007 1 037.8 1 939 944.2 743 755.5 689 690.2 642 649.4
vibrobox 12 328 177 578 N/A N/A 1 362 1 382.8 0.41 1 296 1 310.6 964 1 043.0 971 1 004.0 779 785.4
最小值 － － 8 8.8 0.00 5 5.0 5 5.0 5 5.0 5 5.0
最大值 － － 2 219 2 262.0 1.12 2 089 2 108.5 1 596 1 884.0 1 635 1 721.5 1 369 1 375.0
平均值 － － 430.63 441.98 0.11 383.92 386.75 298.29 332.86 296.08 310.98 248.75 250.28
标准差 － － 635.11 643.97 0.30 615.71 619.06 451.73 534.26 460.32 497.77 363.43 365.44
注: 加粗数值是对应算法找到的最优值

4.5 在 LPNMR’09 实例上的实验结果
表 2 展示了 CPLEX 求解器和其他高效的局部搜索算法在 LPNMR’09 实例上的实验结果. 表中“|V|”列表示图
G(V, E) 的顶点数, 其他行列表示的含义与表 1 相同. 在该组实例中, CPLEX 求解器仅能求得 2 个实例的可行解,
且无法证明其最优性, 而对于其他 7 个实例, CPLEX 无法在给定的时间内找到可行解. 对比 5 个启发式算法可发
现, 算法 MA、GRASP、GRASP_impLS 和 FPLS 能够在所有实例上找到相同的最小解和平均解. 然而 MWCDS
算法无法匹配其中任何一个实例的结果. 此外, 除了 MWCDS 算法, 其余 4 个算法在 LPNMR’09 实例上所得到的
“最小值”“最大值”“平均值”和“标准差”结果均相等.

4.6 在一般 UDG 实例上的实验结果
表 3 展示了 CPLEX 求解器和其他算法在一般 UDG 实例上的实验结果, 其中每列和每行的含义与表 1 中
相同. 对于该组实例, CPLEX 求解器未能找到任何一个最优解或可行解, 原因在于该组实例规模相对较大. 其
他 5 个启发式算法, 即 MWCDS、MA、GRASP、GRASP_impLS 和 FPLS, 分别在 0、22、12、27 和 41 个实例
上找到了最小解. 此外, 这些算法获得的平均解与 FPLS 算法的平均解相匹配的实例数量分别为 0、18、10
和 23.
与此同时, FPLS 算法在这组实例上得到的“平均值”和“标准差”结果均优于其他算法. 实验结果表明, 本文提