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

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

的探索能力. 通过这种方法, 算法得以在已知的解空间附近进行探索, 而不是简单地陷入重复无效的局部搜索循环
中. 这有助于发现新的搜索路径并跳出现有的搜索局限. 扰动的动态性体现在扰动强度的设定上, 它可以根据当前
搜索状态的特征动态地调整, 以更好地平衡探索和利用. 扰动强度是扰动策略中一个重要的参数, 它对扰动效果产
生极大影响. 如果扰动强度过大, 将导致算法重新启动; 而如果扰动强度过小, 则无法跳出局部最优值, 或很容易陷
入循环. 为了适应不同规模的实例, 本文设置扰动的顶点数量为 0.01 × n (n 为顶点数). 大量实验证明, 这样的扰动
强度能够适应不同情况, 既不过于剧烈也不过于微弱, 确保了在不完全放弃已取得进展的同时, 也能够探索新的解
空间. 因此, 当当前候选解陷入局部最优时, 会随机翻转 0.01 × n 个顶点, 以跳出局部最优, 通过这种随机翻转一定
比例的顶点来扰动候选解, 使得算法能够在更大范围内重新评估和优化解结构, 从而避免了循环现象, 增加了跳出
局部最优的可能性. 这种策略增强了算法的全局搜索能力, 并且确保即使对于 NP 难问题也能得到较高质量的近
似解. 此外, 如果当前找到的最小解在 50 次循环内未能提升解的质量, 则会进行一次扰动.

3.4 反馈机制
本文提出的算法框架分为两个主要阶段: 构建初始解阶段和局部搜索阶段. 在构建初始解阶段, 希望选择加入
候选解的顶点具有很高的概率出现在最优解中, 以获得更好的初始解质量, 从而提高最终优化结果的质量. 为了实
现这一目标, 本文提出了一种反馈机制. 该机制通过利用上一轮迭代过程中的信息来指导本轮的搜索过程, 即将这
些历史学习成果应用于下一轮的顶点选择. 这种机制确保了算法能够利用过去的经验, 尤其是那些在多次被验证
为有效顶点的加入候选解中的顶点, 从而提高算法从一个较优初始解开始进行局部搜索的能力. 具体来说, 反馈机
制主要体现在对顶点选择策略的影响上.
在局部搜索阶段, 本文将通过一些策略来选择要添加到当前解中的顶点. 如果一个顶点多次被加入当前候选
解中, 那么它出现在最优解中的概率也会更大, 这种反馈机制使得算法在新一轮搜索开始时就能基于历史经验做
出更加明智的选择. 为了衡量顶点加入候选解的频率, 本文提出了一个表示频率的变量 add_frequency. 每当一个
顶点被添加到候选解中一次, 该顶点的 add_frequency 的值就增加 1.
随后, 将每个顶点的频率信息在算法重新启动后的构建初始解阶段进行反馈. 在这个阶段, 在面对多个 Dscore
值相同的顶点选择时, 优先考虑 add_frequency 值高的顶点, 这是一种基于历史成功经验的智能决策. 它减少了随
机性, 使得算法的顶点选择更为明智, 这在算法的初期尤为重要, 因为高质量的初始解能有效引导后续的搜索方
向. 并且通过反馈机制, 算法能够避免重复探索那些在过往迭代中已经证明不太可能有效或低效的顶点, 这大大降
低了搜索空间, 缩短了达到较优解所需的时间, 提升了算法效率. 同时, 该机制使得算法能够根据问题的具体实例
动态调整搜索路径, 对于不同的图结构, 频繁出现在解中的顶点可能指示了特定的结构特征, 算法通过学习这些特
征动态优化搜索策略, 更加聚焦于关键顶点的选择, 避免了盲目探索. 需要注意的是, 每次反馈频率信息后, add_frequency
值会被重置为 0, 这确保了每轮迭代都能基于最新的反馈信息作出决策, 避免了过时信息的干扰, 保持算法的灵活
性和适应性.

3.5 顶点选择方法
本文提出的算法一共包括两个阶段: 一个是构建初始解阶段, 一个是局部搜索阶段. 在构建初始解阶段中, 需
要挑选顶点加入解中, 那么选择哪些顶点就变成极其重要, 因为初始解影响最终找到的最优解的质量.
在局部搜索阶段, 算法会不停地交换当前候选解内的顶点与当前候选解以外的顶点, 以优化初始解. 因此, 在
此阶段选择一些合适的顶点进行交换就变得尤为重要, 因为这可以尽可能避免算法陷入局部最优, 从而整体提高
算法的性能. 因此, 算法结合了 Dscore, Nscore 以及上述所提到的所有策略, 提出了以下几个顶点的选择规则.
添加顶点规则 1: 选择一个 Dscore 值最大且 ConfChange 值为 1 的顶点, 如果有多个顶点具有相同的最大的
Dscore 值, 则随机选择一个 add_frequency 值最大的顶点.
添加顶点规则 2: 选择一个 Dscore 值最大且 ConfChange 值为 1 的顶点, 如果有多个顶点具有相同的最大的
Dscore 值, 则从中随机选择一个顶点.
添加顶点规则 3: 选择一个 Dscore 值最大且 ConfChange 值为 1 的顶点, 如果有多个顶点具有相同的最大的