随机爬山算法（SHC）

名称

随机爬山算法（Stochastic Hill Climbing, SHC），也称为随机山登算法（Random Hill Climbing）或随机上升法（Stochastic Ascent）。

分类

查看分类思维导图

随机爬山算法是一种局部搜索算法，属于随机优化领域，而随机优化是计算智能的一个子领域。它与其他爬山类算法密切相关，例如简单爬山算法（Simple Hill Climbing）和带随机重启的爬山算法（Random-restart Hill Climbing）。

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

策略

探索

随机爬山算法通过迭代生成并评估当前解的随机邻域解来探索搜索空间。算法从一个初始解开始，然后从当前解的邻域中随机选择一个邻居解。邻域通常由一组可能的移动或扰动定义，这些移动或扰动可作用于当前解以生成新解。

开发

若根据预定义目标函数判断，随机选取的邻居解优于当前解，则算法移动到该邻居解，并从该位置继续搜索。通过不断移动到更优邻居，算法能够利用搜索空间的局部结构，逐步爬升至局部最优。

终止

随机爬山算法持续执行探索与开发过程，直到满足终止条件。常见终止条件包括达到最大迭代次数、找到满足最低质量阈值的解，或在指定次数的连续迭代中未观察到进一步改进。

过程

1. 初始化：
   1. 生成一个初始解
   2. 计算初始解的目标函数值
   3. 将当前解设为该初始解
2. 重复执行，直到满足终止条件：
   1. 生成当前解的一个随机邻居解
   2. 计算该邻居解的目标函数值
   3. 若邻居解优于当前解：
      1. 将当前解更新为该邻居解
3. 返回当前解作为找到的最优解

数据结构

• 解（Solution）：表示搜索空间中的一个候选解
• 目标函数（Objective Function）：用于评估解质量或适应度的函数

参数

• 最大迭代次数（Maximum Iterations）：算法终止前允许执行的最大迭代次数
• 最低质量阈值（Minimum Quality Threshold）：决定可接受解最低质量要求的阈值
• 非改进次数上限（Non-improvement Limit）：在终止前允许连续未改进的最大迭代次数

注意事项

优点

• 简单性：随机爬山算法易于理解和实现，适合作为问题领域初步探索时的算法选择。
• 避免局部最优：通过随机选择邻居，随机爬山算法有可能跳出局部最优并探索搜索空间中的不同区域。
• 低内存需求：随机爬山算法仅需存储当前解和迄今找到的最优解，因此内存开销较低。

缺点

• 探索不完全：随机爬山算法可能陷入局部最优，无法遍历整个搜索空间，从而可能错失全局最优解。
• 缺乏保证：随机爬山算法无法保证找到全局最优解，甚至无法保证找到高质量的局部最优解。
• 对初始解敏感：随机爬山算法最终得到的解质量可能在很大程度上受初始解影响。

启发式建议

邻域定义

• 应选择能够对当前解产生有意义且多样化扰动的邻域定义方式。
• 需要同时考虑邻域规模以及生成和评估邻居解的计算成本。

终止条件

• 应根据可用计算资源以及解质量与运行时间之间的权衡来设置最大迭代次数。
• 应结合具体问题领域和期望解质量，确定合适的最低质量阈值。
• 可根据搜索空间景观特征以及陷入局部最优的可能性，调整非改进次数上限。

目标函数设计

• 应设计能够准确反映问题目标属性与约束条件的目标函数。
• 应确保目标函数具有较高的计算效率，因为在搜索过程中会被频繁调用。

初始解生成

• 可尝试不同的初始解生成策略，例如随机初始化、启发式构造或结合领域知识的方法。
• 可从不同初始解出发多次运行随机爬山算法，以探索搜索空间中的不同区域。