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

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

表 5 反馈机制有效性验证实验结果

APLS FPLS
实例 |V| |E|
Best Avg Best Avg
ba_1k_30k 1 000 30 039 21 21.0 21 21.0
ba_1k_6k 1 000 5 964 80 80.0 79 79.9
c-fat200-1 200 1 534 18 18.0 18 18.0
DD_g140 560 2 710 118 118.9 118 118.7
DD_g142 288 1 290 64 64.0 64 64.0
DD_g143 414 2 088 83 84.7 83 83.9
DD_g144 288 1 514 56 56.5 56 56.1
DD_g145 404 2 320 71 71.1 70 70.8
DD_g146 327 1 506 69 69.9 69 69.8
delaunay_n11 2 048 6 127 333 337.1 333 335.4
delaunay_n12 4 096 12 264 683 687.2 681 683.3
delaunay_n13 8 192 24 547 1 376 1 381.8 1 369 1 375.0
DSJC500-5 500 125 248 5 5.0 5 5.0
er_graph_1k_6k 1 000 6 000 107 108.9 108 109.4
socfb-Haverford76 1 446 59 589 58 58.5 58 58.5
str_0 363 2 454 55 55.2 55 55.0
str_200 363 3 068 47 47.0 47 47.0
str_400 363 3 157 46 46.0 46 46.0
str_600 363 3 279 41 41.0 41 41.0
SW-1000-6-0d3-trial3 1 000 3 000 166 168.1 168 168.6
SW-100-6-0d3-trial3 100 300 16 16.0 16 16.0
t3dl_a 20 360 265 113 1 052 1 057.3 1 044 1 049.4
tube1 21 498 459 277 644 648.5 642 649.4
vibrobox 12 328 177 578 780 786.1 779 785.4
最小值 5 5.0 5 5.0
最大值 1 376 1 381.8 1 369 1 375.0
平均值 249.54 251.16 248.75 250.28
标准差 365.31 367.21 363.43 365.44
注: 加粗数值是对应算法找到的最优值

5.1.2 扰动策略的有效性
为了验证扰动策略的有效性, 对 APLS 算法进行了改写, 得到了算法 ALS. ALS 算法与 APLS 算法的区别在
于 ALS 算法中没有使用扰动策略, 仅使用了基于年龄属性、双层格局检测策略及禁忌策略的避免循环搜索方法.
具体来说, APLS 在求解的过程中, 算法会记录每一次求得的最小解, 若本次得到的解比之前的解好, 那将没有改
善解的迭代步数初始化为 1, 若本次所得到解没有比之前的解好, 那将没有改善解的迭代步数加 1. 当没有改善解
的迭代步数达到了 50 时, 该算法采用了移出顶点规则 1 来翻转一些顶点, 从而扩大搜索空间. 而 ALS 在求解过程
中, 可能会一直陷入局部最优的情况, 导致算法停滞并难以跳出. 通过对比 APLS 和 ALS 算法的求解效果, 可以评
估扰动策略对算法性能的影响.
ALS 和 APLS 算法的实验结果如表 6 所示. 在此表中, 每列和每行的含义与表 2 中的含义相同. 从表 6 中可以
看出, 除“DD_g145”和“tube1”实例外, APLS 在其余 22 个实例上都能找到更小的解或已知的最小解. 而在平均解方
面, 除“DD_g140”“DD_g144”“DD_g145”和“tube1”实例外, APLS 在其余 20 个实例上都能找到更小的平均解或已
知的最小平均解. 因此可以得出结论, 通过引入扰动策略, 当算法在迭代过程中陷入局部最优状态, 无法进一步提
升解的质量时, 该策略能够有效地打破当前的搜索空间限制, 扩大搜索范围, 帮助算法探索更多的解空间, 使算法
的全局搜索能力得以增强, 进而可能发现更优解. 在应用扰动策略的 APLS 算法与不使用扰动策略的对比算法