带随机重启的随机爬山算法（SHCR）

名称

带随机重启的随机爬山算法（Stochastic Hill Climbing With Random-Restarts, SHCR）

分类

查看分类思维导图

带随机重启的随机爬山算法是一种局部搜索元启发式算法，隶属于更广义的随机优化领域。它与其他爬山类算法密切相关，例如简单爬山算法（Simple Hill Climbing）和随机爬山算法（Stochastic Hill Climbing）。

• 人工智能
  • 计算智能
    • 随机优化
      • 元启发式
        • 局部搜索算法
          • 爬山算法
            • 带随机重启的随机爬山算法

策略

带随机重启的随机爬山算法是一种局部搜索算法，其目标是在搜索空间中通过迭代改进候选解来寻找全局最优解。算法从一个随机初始解开始，通过对当前解施加随机扰动来尝试找到更优解；如果新解能够改进目标函数值，则接受该新解。

随机搜索

与在每次迭代中都确定性选择最优邻域解的简单爬山算法不同，随机爬山算法在搜索过程中引入了随机性。这种随机性使算法有机会跳出局部最优，从而提高找到全局最优解的可能性。

随机重启

为进一步提升算法寻找全局最优解的能力，带随机重启的随机爬山算法会从多个不同的初始解出发重复执行搜索。当算法到达局部最优，或达到最大迭代次数后，它会从一个新随机生成的解重新开始搜索。该过程会重复进行，直到达到预设的重启次数，或找到一个令人满意的解为止。

过程

数据结构

1. current_solution：当前候选解。
2. best_solution：迄今为止找到的最优解。
3. objective_function：用于评估解质量的目标函数。

参数

1. max_iterations：每次爬山搜索允许执行的最大迭代次数。
2. num_restarts：执行随机重启的次数。
3. step_size：施加于当前解的扰动幅度。

算法步骤

1. 将 best_solution 初始化为 None。
2. 重复执行 num_restarts 次：
   1. 随机生成一个初始解，并将其赋值给 current_solution。
   2. 重复执行 max_iterations 次：
      1. 对 current_solution 施加幅度为 step_size 的随机扰动，得到一个新解。
      2. 计算该新解的目标函数值。
      3. 如果新解优于 current_solution，则将 current_solution 更新为该新解。
      4. 如果 current_solution 优于 best_solution，则将 best_solution 更新为 current_solution。
   3. 如果找到了一个令人满意的解，则终止算法。
3. 返回 best_solution。

注意事项

优点

• 简单且易于实现。
• 由于在搜索过程中引入了随机性，因此能够跳出局部最优。
• 多次随机重启提高了找到全局最优解的可能性。

缺点

• 算法性能在很大程度上依赖于参数选择，例如 step_size 和 max_iterations。
• 对于复杂问题，可能需要大量目标函数评估，计算代价较高。
• 搜索过程的随机性可能导致不同运行之间结果不稳定。

启发式建议

参数选择

• 应根据可用计算资源和问题复杂度选择 max_iterations。较大的取值能够提高找到更优解的概率，但也会增加计算成本。
• 应将 num_restarts 设置为能够平衡探索与开发的数值。更多的重启次数会提高找到全局最优解的可能性，但也会增加整体运行时间。
• 应根据搜索空间的特性调整 step_size。较大的 step_size 有利于更广泛的探索，但可能跳过优良解；较小的 step_size 有利于精细搜索，但可能导致收敛较慢。

问题相关考虑

• 应定义能够准确反映给定问题中解质量的目标函数。
• 应结合搜索空间的结构设计合适的扰动机制，以有效探索解空间。
• 在条件允许时，可引入领域知识来引导搜索过程，并提高生成解的质量。

终止准则

• 除最大迭代次数外，还可考虑实现其他终止准则，例如：
  • 达到预定义的目标函数值。
  • 检测到收敛，即目标函数值的改进低于某个阈值。
  • 为算法执行设置时间上限。

混合化

• 可考虑将带随机重启的随机爬山算法与其他优化技术结合，例如其他局部搜索算法或演化算法，以进一步提升其性能。
• 可融入问题特定启发式信息或领域知识，以引导搜索过程并生成更高质量的解。