第2章 爬山法：从局部最优到全局探索

爬山法，说白了就是「往高处走」。你站在一个山坡上，闭着眼睛，只靠脚底的感觉——哪边高就往哪边迈一步。这就是爬山法的核心思想：每一步都朝着当前能看到的、让目标函数值提升的方向移动。

我刚开始接触优化算法时，觉得这玩意儿也太简单了吧？但后来发现，很多实际问题还真就靠它解决。当然，它也有明显的短板，咱们慢慢聊。

2.1 基本原理

爬山法属于局部搜索算法。它不关心全局长什么样，只盯着当前解的邻居空间。每次迭代，它从当前解的邻居中挑一个「更好」的，然后跳过去。

关键假设：目标函数是单峰的，或者至少局部是单峰的。如果函数像心电图一样剧烈震荡，爬山法基本就废了。

你想想看，这像不像一个近视眼找山顶？只能看到脚下几米的范围，哪高往哪走。如果遇到一个小山包，它就会停在那，以为到了顶峰。

2.2 算法流程

爬山法的流程非常直观，我一般把它拆成5步：

1. 初始化：随机生成一个初始解 x₀，或者根据经验指定一个起点。
2. 生成邻居：在当前解 x 的邻域内，生成一组候选解 N(x)。
3. 评估选择：计算每个候选解的目标函数值 f(x')，选出最优的那个 x*。
4. 判断移动：如果 f(x*) > f(x)，就移动到 x*；否则停止，返回当前解。
5. 迭代：重复步骤2-4，直到满足终止条件（达到最大迭代次数或无法改进）。

代码实现也很简单，我贴一个最基础的版本：

def hill_climbing(f, x0, neighbor_func, max_iter=1000):
    x = x0
    for i in range(max_iter):
        neighbors = neighbor_func(x)
        x_best = max(neighbors, key=lambda x: f(x))
        if f(x_best) <= f(x):
            break  # 无法改进，停止
        x = x_best
    return x, f(x)

嗯，这里要注意：neighbor_func 怎么设计，直接决定了算法能不能找到好解。我见过太多人随便写个邻居生成函数，结果算法跑半天还在原地打转。

2.3 优缺点分析

爬山法的优缺点非常鲜明，我整理了一个表格，方便你对比：

维度	优点	缺点
实现难度	代码量少，逻辑简单，10行就能跑起来	邻居生成策略需要手工调，依赖经验
计算效率	每步只评估邻居，计算量小，收敛快	容易陷入局部最优，无法跳出
适用场景	目标函数平滑、单峰或近似单峰	多峰、离散、噪声大的问题基本无效
可解释性	每一步都有明确的物理意义	无法解释为什么停在某个局部点

2.4 改进策略：随机重启爬山法

既然标准爬山法容易卡在局部最优，那最简单的改进思路就是——多爬几次。这就是随机重启爬山法（Random Restart Hill Climbing）。

核心逻辑：

• 从多个随机初始点开始，分别执行标准爬山法
• 记录每次运行得到的最优解
• 在所有运行结果中，取最好的那个作为最终解

代码也很直接：

def random_restart_hill_climbing(f, neighbor_func, num_restarts=10, max_iter=1000):
    best_x, best_val = None, -float('inf')
    for _ in range(num_restarts):
        x0 = random_initial_solution()
        x, val = hill_climbing(f, x0, neighbor_func, max_iter)
        if val > best_val:
            best_x, best_val = x, val
    return best_x, best_val

我个人习惯把重启次数设为 10-20 次。太少的话，覆盖不到全局；太多的话，计算成本就上去了。你想想看，这其实是在用「时间换概率」——每次重启都是一次独立的探索，总有一次能撞到全局最优附近。

2.5 知识结构图

下面这张图展示了爬山法的完整知识体系，从基本原理到改进策略：

2.6 避坑指南

最后，我总结几个实际项目中容易踩的坑：

• 邻居生成太密或太疏：太密会导致每步计算量爆炸，太疏又容易错过好解。我一般建议邻居数量控制在 10-50 之间，具体看问题维度。
• 初始点选择太随意：随机重启虽然能缓解，但如果初始点全扎堆在一个区域，重启再多也没用。建议用拉丁超立方采样或 Sobol 序列来生成初始点。
• 终止条件太宽松：只靠「无法改进」来终止，很容易提前收敛。我习惯加一个最大迭代次数兜底，比如 500 或 1000 步。
• 忽略了目标函数的尺度：如果函数值范围很大，相邻解的差异可能被数值精度吃掉。建议做归一化或使用相对比较。