第3章 局部搜索算法基础：爬山法、梯度下降法与Nelder-Mead单纯形法

局部搜索，说白了就是在一个小范围内找最优解。你想想看，全局优化太难了，很多时候我们只需要一个「足够好」的解，而且得快速找到它。这一章我带你看看三种最经典的局部搜索方法：爬山法、梯度下降法和Nelder-Mead单纯形法。

这三种方法各有各的脾气。我在项目中遇到过不少坑，比如梯度下降法在非凸函数上容易陷入鞍点，爬山法对初始点极其敏感。嗯，咱们一个一个来拆解。

3.1 爬山法（Hill Climbing）

爬山法是最直观的局部搜索方法。它的思路很简单：从当前点出发，往「更高」的方向走一步，直到走不动为止。

算法流程

1. 随机选择一个初始解 x₀
2. 检查当前解的邻域，找到目标函数值最大的邻居
3. 如果该邻居优于当前解，则移动过去；否则停止
4. 重复步骤2-3直到收敛

我刚开始做优化时，觉得爬山法太简单了，甚至有点看不起它。直到有一次做参数调优，面对一个光滑的单峰函数，爬山法居然比遗传算法快了两个数量级。从那以后我再也不敢小看它了。

变种与改进

变种名称	核心策略	适用场景
最陡爬山法	检查所有邻居，选最优	小规模、离散问题
随机爬山法	随机选一个邻居，如果更好就移动	大规模问题，节省计算量
首优爬山法	找到第一个更好的邻居就移动	实时性要求高的场景
模拟退火	以一定概率接受差解	多峰函数，跳出局部最优

3.2 梯度下降法（Gradient Descent）

梯度下降法，说白了就是沿着「最陡的下坡路」走。它利用目标函数的梯度信息来指导搜索方向。

我个人习惯把梯度下降法想象成「盲人下山」：你站在山上，用脚探一探哪个方向最陡，就往那个方向迈一步。每一步都让你离谷底更近一点。

数学原理

对于目标函数 f(x)，梯度下降的更新公式为：

x_{k+1} = x_k - α ∇f(x_k)

其中 α 是学习率（步长），∇f(x_k) 是梯度向量。

学习率的选择

学习率是个让人头疼的参数。我建议你这样调：

• 学习率太大：震荡发散，永远不收敛
• 学习率太小：收敛极慢，像蜗牛爬
• 自适应学习率：比如 Adam、RMSProp，省心很多

梯度下降的三种模式

模式	每次更新使用的数据量	特点
批量梯度下降	全部数据	准确但慢，适合小数据集
随机梯度下降	1个样本	快但震荡，适合大数据
小批量梯度下降	batch_size个样本	折中方案，最常用

3.3 Nelder-Mead单纯形法

Nelder-Mead单纯形法，也叫「下山单纯形法」。它不需要梯度信息，只靠函数值来搜索。这在很多工程问题中特别实用——因为很多时候你根本算不出梯度。

我记得有一次做化工流程优化，目标函数是通过仿真器计算的，根本没法求导。当时我试了梯度下降法，直接报错。后来换成 Nelder-Mead，虽然收敛慢了点，但至少能跑出结果来。

核心思想

在 n 维空间中，维护一个由 n+1 个点组成的单纯形（比如二维空间中的三角形）。通过反射、扩张、收缩、压缩四种操作，让单纯形「滚」向最优解。

四种操作

1. 反射：将最差点沿其他点的质心方向反射
2. 扩张：如果反射点更好，继续沿同一方向走远一点
3. 收缩：如果反射点不好，向质心方向收缩
4. 压缩：如果收缩也不行，所有点向最好点压缩

3.4 三种方法对比

特性	爬山法	梯度下降法	Nelder-Mead
是否需要梯度	否	是	否
收敛速度	中等	快（梯度准确时）	慢
对初始点敏感度	高	高	中等
适用问题类型	离散、组合优化	连续、可微优化	连续、不可微优化
实现难度	低	中等	中等

3.5 知识体系总览

下面这张图把三种方法的核心逻辑串起来了。你仔细看看，它们本质上都是在「局部」做文章，只是手段不同。

3.6 实践建议

说了这么多理论，最后给你几条实在的建议：

• 先试简单的：如果问题规模小，爬山法就够了。别一上来就上复杂算法。
• 梯度可用就用梯度：梯度下降法收敛快，前提是你算得准。
• 算不出梯度用Nelder-Mead：黑箱优化场景，它是最稳妥的选择之一。
• 别忘了随机重启：无论用哪种方法，多跑几次，从不同起点开始，能有效避免局部最优。