Page 246 - 《软件学报》2025年第8期
P. 246

李睿智 等: 局部搜索算法求解最小弱连通支配集问题                                                       3669


                 出的算法在效果上更为出色, 并且随着问题规模的增加, 所提出算法在求解能力上的优势变得更加明显.

                 4.7   在  NDR  实例上的实验结果
                    表  4  展示了  CPLEX  求解器和其他算法在      NDR  实例上的实验结果, 其中每列和每行的含义与表               2  相同. 对于
                 该组实例, 精确求解器       CPLEX  在  24  个实例上无法获得任何最优解或可行解. 对于启发式算法来说, MWCDS                  算
                 法所得到的最小解和平均解不及其他              4  个对比算法. 在实例“c-fat200-1”“DSJC500-5”“SW-100-6-0-d3-trial3”和
                 “ba_1k_30k”上, GRASP、GRASP_impLS  和  FPLS  算法可以找到相同的最小解, MA       算法能在其中的       3  个实例上
                 找到最小解. 在其他      20  个实例上, FPLS  算法能够找到优于其他对比算法的最小解. 在平均解方面, FPLS                算法也明
                 显优于   MWCDS、MA、GRASP     和  GRASP_impLS  算法.
                    最后, FPLS  算法在这组实例上求得的“最大值”“平均值”和“标准差”结果均较优. 总体来说, 本文提出的算法
                 在该组实例上具有较好的效果. 同时, 随着原始图中顶点数量的增加, 本文提出的算法改进效果越好, 尤其是在
                 “delaunay_n11”“delaunay_n12”“delaunay_n13”“t3dl_a”“tube1”和“vibrobox”这  6  个实例上.
                    综合这   4  组实例的结果, 本文提出的算法在与其他算法的比较中表现出色. 不仅在小图实例中找到了已知的
                 最小解, 而且在大图实例中找到了更小的解. 因此, 本文提出的算法对于求解最小弱连通支配集问题具有很好的
                 效果.

                 5   讨 论

                 5.1   消融实验
                    为了解决局部搜索过程中的循环问题, 本文提出了基于年龄属性、双层格局检测策略和禁忌策略的避免循环
                 方法. 为使当前解能够有效地跳出局部最优, 本文提出了扰动策略. 为了利用上一次迭代的搜索信息来指导搜索,
                 使得算法能从一个较优的初始解开始进行搜索, 本文提出了反馈机制. 基于以上策略提出了高效的局部搜索算法
                 求解最小弱连通支配集问题. 本节将对避免循环搜索方法、扰动策略和反馈机制的有效性进行验证. 本节选择规
                 模分布较广的     NDR  基准测试实例进行测试. 对比算法在不同随机种子下运行                  10  次, 内循环和外循环迭代次数均
                 设为  1 000  次, 并将求解每个实例的截止时间设置为          300 s.

                 5.1.1    反馈机制的有效性
                    为了验证反馈机制的有效性, 本文对            FPLS  算法进行了改写, 得到了算法       APLS. APLS  算法与  FPLS  算法的区
                 别在于   APLS  算法中没有使用反馈机制, 仅使用了基于年龄属性、双层格局检测策略及禁忌策略的避免循环搜索
                 方法和扰动策略. APLS     在构建初始解时, 不会考虑上一轮在局部搜索过程中顶点的反馈信息, 因此在本轮构建初
                 始解时容易错过大概率在最优解中的顶点, 而               FPLS  在选择顶点时则考虑了此信息. 具体来说, APLS           首先随机选
                 择一个   Dscore 值最大的顶点加到解中, 接着从当前解的二层邻居内随机选择一个                    Dscore 值最大的顶点加到解中,
                 若当前解的    2  层邻居内有锁定顶点, 优先将锁定顶点加到解中, 而              FPLS  首先随机选择一个      Dscore 值最大的顶点
                 加到解中, 接着从当前解的        2  层邻居内选择一个      Dscore 最大的顶点加到解中, 若有多个顶点满足相同条件, 优先
                 选择  add_frequency 值较大的顶点, 若仍有多个顶点满足该条件时才会选择随机添加一个满足该条件的顶点, 若当
                 前解的   2  层邻居内有锁定顶点, 优先将锁定顶点加到解中. 通过对比                FPLS  和  APLS  算法的求解效果, 可以评估反
                 馈机制对算法性能的影响.
                    APLS  和  FPLS  算法的实验结果如表     5  所示. 在此表中, 每列和每行的含义与表         2  中的含义相同. 结果表明, 除
                 “er_graph_1k_6k”“SW-1000-6-0d3-trial3”实例外, FPLS  在其余  22  个实例上都能找到更小的解或已知的最小解. 在
                 平均解方面, 除“er_graph_1k_6k”“SW-1000-6-0d3-trial3”和“tube1”实例外, FPLS  在其余  21  个实例上能找到更小的
                 平均解或已知的最小平均解. 因此可以得出结论, 反馈机制是算法设计中的一项关键优化策略, 它通过历史信息的
                 累积和应用, 为算法提供了智能决策的基础, 减少了搜索成本, 加速了收敛过程, 增强了算法对不同实例的适应性.
                 在最小弱连通支配集问题的求解中, 反馈机制展现了其在提升算法性能、效率和解质量方面的巨大潜力, 是算法
                 创新和优化的重要方向.
   241   242   243   244   245   246   247   248   249   250   251