迭代局部搜索（ILS）

名称

迭代局部搜索（Iterated Local Search, ILS）

分类

查看分类思维导图

迭代局部搜索是一种元启发式优化算法，通过结合局部搜索与扰动步骤来跳出局部最优。它与其他元启发式方法密切相关，例如变邻域搜索（Variable Neighborhood Search, VNS）和贪婪随机自适应搜索（Greedy Randomized Adaptive Search Procedure, GRASP）。

• 优化
  • 元启发式
    • 随机优化
      • 迭代局部搜索（ILS）

策略

迭代局部搜索是一种简单而高效的优化策略，通过在强化搜索与多样化搜索两个阶段之间交替进行来实现优化。强化阶段通过对当前解执行局部搜索，不断改进解，直至达到局部最优。当局部搜索无法继续提升解质量时，便触发多样化阶段，即对当前解施加扰动算子，以跳出局部最优并探索搜索空间中的新区域。

扰动步骤是 ILS 的关键组成部分。扰动既要足够强，以使当前解能够摆脱局部最优；又不能过强，以免破坏当前解中已有的优良特征。施加扰动后，再次对修改后的解执行局部搜索。如此循环往复，直到满足终止准则，例如达到最大迭代次数或时间上限。

ILS 在整个搜索过程中维护迄今为止找到的最优解，并在算法结束时将其作为最终输出。算法的有效性主要取决于局部搜索过程和扰动算子的设计，而这两者都可以根据具体问题进行针对性调整。

过程

数据结构：

• 当前解（current_solution）：当前正在搜索的解。
• 最优解（best_solution）：迄今为止找到的最优解。

参数：

• 最大迭代次数（max_iterations）：允许执行的最大迭代次数。
• 扰动强度（perturbation_strength）：施加于当前解的扰动强度。

步骤：

1. 初始化：
   1. 生成一个初始解，并将其赋值给 current_solution。
   2. 对 current_solution 执行局部搜索，直到达到局部最优。
   3. 将 best_solution 设为 current_solution。
   4. 将 iteration_count 设为 0。
2. 当 iteration_count 小于 max_iterations 时：
   1. 根据 perturbation_strength 对 current_solution 应用扰动算子。
   2. 对扰动后的解执行局部搜索，直到达到局部最优。
   3. 若新的局部最优解优于 best_solution，则更新 best_solution。
   4. 若满足接受准则（例如始终接受，或以某一概率接受），则将 current_solution 更新为新的局部最优解。
   5. 将 iteration_count 增加 1。
3. 返回 best_solution 作为最终输出。

注意事项

优点：

• 简单性：ILS 易于实现，仅需要少量核心组件，即局部搜索过程和扰动算子。
• 灵活性：通过选取合适的局部搜索与扰动策略，ILS 可以适配多种优化问题。
• 高效性：通过结合强化搜索与多样化搜索，ILS 能够有效探索搜索空间并找到高质量解。

缺点：

• 参数敏感性：ILS 的性能可能对参数选择较为敏感，例如扰动强度和接受准则。
• 对局部搜索的依赖性：ILS 的效果在很大程度上依赖于底层局部搜索过程的质量。
• 缺乏问题特定知识：ILS 本身并不天然融入问题特定知识，因此在某些问题上，相较于专用算法，其性能可能受到限制。

启发式建议

扰动强度：

• 可从较小的扰动强度开始；当搜索陷入局部最优时，再逐步增大扰动强度。
• 应根据问题规模和复杂度调整扰动强度。
• 可尝试不同的扰动算子，例如随机移动、交换操作或重新启动。

局部搜索过程：

• 应选择适合具体问题的局部搜索方法，例如爬山法、模拟退火或禁忌搜索。
• 需要综合考虑局部搜索质量与其计算开销之间的权衡。
• 可通过实现高效的数据结构和增量评估技术来加速局部搜索过程。

接受准则：

• 始终接受新的局部最优解会使搜索更具探索性，但也可能导致收敛速度变慢。
• 仅当新的局部最优解优于当前解时才接受，会使搜索更偏向开发，但也更容易陷入局部最优。
• 可考虑采用概率型接受准则，例如模拟退火中的 Metropolis 准则，以平衡探索与开发。

终止准则：

• 可设置最大迭代次数或时间上限，以控制算法总体运行时间。
• 可实现基于搜索进展的提前停止机制，例如当连续若干次迭代未观察到改进时停止搜索。
• 还可考虑问题特定的终止准则，例如达到目标解质量，或满足某些约束条件。

混合化：

• 可将 ILS 与其他元启发式方法或问题特定启发式方法结合，以提升性能。
• 可在扰动步骤或局部搜索过程中融入领域知识或问题特定算子。
• 可将 ILS 用作更大优化框架中的一个组成部分，例如模因算法（Memetic Algorithm）或混合进化算法（Hybrid Evolutionary Algorithm）。