引导式局部搜索（GLS）

名称

引导式局部搜索（Guided Local Search, GLS）

分类

查看分类思维导图

引导式局部搜索是一种元启发式优化技术，它在局部搜索方法的基础上进行扩展，以跳出局部最优并提升解的质量。该方法与其他基于局部搜索的元启发式方法密切相关，例如迭代局部搜索（Iterated Local Search）和变邻域搜索（Variable Neighborhood Search）。

• 优化
  • 元启发式
    • 局部搜索方法
      • 引导式局部搜索

策略

引导式局部搜索通过引导搜索过程朝向解空间中更有前景的区域，从而提升局部搜索算法的性能。其实现方式是在原始目标函数中加入惩罚项，以鼓励算法探索新解，并对与近期访问到的局部最优解相关的特征施加惩罚。

GLS 的核心思想在于识别那些可能频繁出现在局部最优解中的解特征，并对这些特征进行惩罚，从而有效改变搜索景观，使搜索倾向于探索新的区域。惩罚值会根据搜索历史动态调整，使算法能够适应问题结构，并避免重复访问已探索区域。

特征识别

GLS 依赖于“解特征”这一概念。解特征是用于描述和区分解的问题相关属性或结构特征，通常由具体问题领域决定，并能够刻画解结构中的关键方面。

惩罚计算

每个解特征都对应一个惩罚项，用以反映该特征对目标函数的影响。初始时，各特征的惩罚值均设为零；在搜索过程中，惩罚值会根据这些特征在已访问解中的出现频率及其影响程度动态更新。

增广目标函数

GLS 通过在原始目标函数中加入与解特征相关的加权惩罚项之和，构造增广目标函数。该增广目标函数引导局部搜索同时最小化原始目标值与惩罚值，从而鼓励算法探索新的区域并跳出局部最优。

过程

1. 使用构造型启发式方法或随机初始化生成初始解 s。
2. 将所有解特征的初始惩罚值设为零。
3. 对当前解 s 执行局部搜索，得到一个局部最优解 s*。
4. 当终止条件未满足时：
   1. 识别局部最优解 s* 中所包含的解特征。
   2. 根据这些特征的出现频率及影响程度更新其惩罚值。
   3. 通过加入惩罚项的加权和来修改目标函数。
   4. 使用增广目标函数，以当前解 s* 为基础继续执行局部搜索。
   5. 若找到新的局部最优解，则将 s* 更新为该新解。
   6. 若满足终止条件，则返回当前找到的最优解。

数据结构

• 解（Solution）：表示问题的一个候选解，通常编码为向量，或根据具体问题领域采用更复杂的数据结构。
• 特征（Feature）：表示解的某种问题相关属性或结构特征，用于引导搜索过程。
• 惩罚（Penalty）：表示与每个解特征相关联的惩罚值，并在搜索过程中动态更新。

参数

• lambda：权重因子，用于控制增广目标函数中原始目标函数与惩罚项之间的平衡。
• alpha：缩放因子，用于控制根据解特征的出现频率和影响程度更新惩罚值的速度。
• 最大迭代次数（max_iterations）：GLS 算法允许执行的最大迭代次数。

注意事项

优点

• 与基础局部搜索方法相比，引导式局部搜索能够更有效地跳出局部最优并探索解空间中有前景的区域，从而提升解的质量。
• 惩罚项的动态调整使 GLS 能够适应问题结构，并避免重复访问已经探索过的区域，从而提高搜索效率。
• GLS 是一种具有较强灵活性的框架，只要能够定义合适的解特征，就可以应用于多种优化问题。

缺点

• GLS 的性能在很大程度上依赖于解特征的合理定义，而特征定义通常具有较强的问题依赖性，可能需要领域知识或反复实验才能确定。
• GLS 的效果还取决于原始目标函数与惩罚项之间的平衡，该平衡由 lambda 参数控制。该参数的调优可能较为困难，通常需要反复试验。
• 相较于基础局部搜索方法，GLS 在特征识别和惩罚更新过程中引入了额外的计算开销。

启发式建议

特征定义

• 定义能够刻画问题结构关键方面、并能区分优劣解的解特征。
• 优先考虑那些可能出现在局部最优解中、并能够引导搜索走向未探索区域的特征。
• 可尝试不同的特征集合，并评估其对搜索性能的影响。

参数调优

• 可从较小的 lambda 值开始，例如 0.1；若搜索过程容易陷入局部最优，可逐步增大该参数。
• 调整 alpha 以控制惩罚值更新速度。较大的 alpha 会导致更快的惩罚更新，并带来更强的探索倾向。
• 应根据问题规模和可用计算资源设置 max_iterations，既要保证搜索有足够迭代次数收敛，又要避免运行时间过长。

局部搜索集成

• 在 GLS 中应选用高效且有效的局部搜索算法作为底层搜索方法。
• 应结合具体问题设计合适的邻域结构和移动算子，以有效探索搜索空间。
• 可尝试不同的局部搜索技术（例如爬山算法、模拟退火），以找到最适合当前问题的实现方式。

混合化

• 可考虑将 GLS 与其他元启发式方法或问题特定启发式方法相结合，以进一步提升性能。
• 可以探索混合式方法，结合不同技术的优势，例如利用 GLS 引导基于种群的元启发式算法，或在特征定义和惩罚更新过程中融入领域知识。

终止准则

• 应根据问题需求和可用资源设定合适的终止条件。
• 可采用的准则包括最大迭代次数、最大函数评估次数，或达到目标解质量阈值。
• 可实现提前停止机制，即当若干次迭代后未观察到显著改进时，提前终止搜索。