变邻域搜索（VNS）

名称

变邻域搜索（Variable Neighborhood Search, VNS）

分类

查看分类思维导图

变邻域搜索是一种元启发式优化算法，其通过在搜索过程中系统性地改变邻域结构来跳出局部最优，并探索解空间中的不同区域。它与其他基于局部搜索的元启发式方法密切相关，例如模拟退火（Simulated Annealing）和禁忌搜索（Tabu Search）。

• 优化
  • 元启发式
    • 基于局部搜索的元启发式
      • 变邻域搜索

策略

变邻域搜索的核心思想是在搜索过程中系统性地改变邻域结构。这使得算法能够跳出局部最优，并探索解空间中的不同区域。其搜索过程在两个主要阶段之间交替进行：扰动阶段与局部搜索阶段。

扰动阶段

在扰动阶段，算法通过对当前解进行随机扰动来生成一个新解。该扰动基于一组预先定义的邻域结构进行，这些邻域通常按照规模或复杂度递增的顺序排列。扰动阶段有助于算法跳出局部最优，并探索解空间中的新区域。

局部搜索阶段

在扰动阶段之后，算法以扰动后的解为起点执行局部搜索。局部搜索旨在当前邻域中寻找更优解。若找到改进解，则从该新解继续搜索；否则，算法转向预定义集合中的下一个邻域结构。

搜索过程在扰动阶段与局部搜索阶段之间不断迭代，直到满足停止准则，例如达到最大迭代次数或时间上限。

过程

1. 初始化算法：
   1. 定义邻域结构集合 N_k, k = 1, …, k_max，并按规模或复杂度递增排序。
   2. 选择一个初始解 x。
   3. 设置当前最优解 x_best = x。
2. 重复执行，直到满足停止准则：
   1. 令 k = 1。
   2. 重复执行，直到 k = k_max：
      1. 扰动阶段：利用邻域结构 N_k 对 x 进行随机扰动，生成新解 x'。
      2. 局部搜索阶段：以 x' 为起点应用局部搜索方法，得到新解 x''。
      3. 若 x'' 优于 x_best，则更新 x_best = x''，并令 x = x''。
      4. 若 x'' 优于 x，则令 x = x'' 且 k = 1；否则，令 k = k + 1。
3. 返回找到的最优解 x_best。

数据结构

• 邻域结构集合 N_k, k = 1, …, k_max：一组预先定义的邻域结构，并按规模或复杂度递增排序。
• 当前解 x：搜索过程中当前正在探索的解。
• 最优解 x_best：搜索过程中迄今为止找到的最优解。

参数

• k_max：搜索过程中使用的最大邻域结构数量。
• 停止准则：用于决定搜索过程何时终止的条件，例如最大迭代次数或时间上限。

注意事项

优点

• 能够通过系统性改变邻域结构跳出局部最优。
• 邻域结构集合的定义具有较高灵活性，因此算法可适配不同问题领域。
• 相对易于实现，并且可以方便地与其他局部搜索技术或元启发式方法结合。

缺点

• 算法性能依赖于邻域结构的选择及其应用顺序。
• 为定义有效的邻域结构，可能需要一定的问题相关知识。
• 对于大规模问题实例或复杂邻域结构，搜索过程的计算代价可能较高。

启发式建议

邻域结构定义

• 应使用一组具有多样性的邻域结构，以有效探索解空间中的不同区域。
• 可按规模或复杂度递增对邻域结构进行排序，使算法能够逐步加强搜索。
• 在定义邻域结构时，可结合问题特定知识，以确保其适用于给定问题。

探索与开发的平衡

• 可根据问题规模与复杂度调整邻域结构数量 k_max。较大的 k_max 有助于更充分地探索，但也可能增加计算时间。
• 应控制局部搜索阶段的搜索强度，以平衡探索与开发。更强的局部搜索可能提升解质量，但也可能削弱算法跳出局部最优的能力。

随机化机制

• 应在扰动阶段引入随机性，以保证扰动的多样性并避免循环行为。
• 可考虑采用自适应或自适应演化机制，根据搜索进展动态调整扰动强度。

混合化

• 可将变邻域搜索与其他元启发式方法或局部搜索技术结合，以提升其性能。
• 可融入问题特定启发式规则或领域知识，以引导搜索过程并提升解质量。

终止准则

• 可综合使用多种终止准则，例如最大迭代次数、时间上限或停滞检测机制，以在解质量与计算时间之间取得平衡。
• 可考虑基于当前最优解改进速率实现提前停止机制，以避免在搜索不太可能继续取得改进时进行不必要的计算。