核心概述
基于邻域改进的局部搜索方法，在不使用导数的前提下反复移动到更优邻居直至无改进，用于黑箱或组合优化并可配重启/扰动增强全局性。
原文引述
Description: Local search that iteratively moves to an improving neighbor until no improvement exists. Works without derivatives; supports first/best-improvement, stochastic variants, restarts, and perturbations. Time: Proportional to (iterations × neighborhood size); problem-dependent Status: tested ——摘自本节点现有英文注释
展开阐述
-
定义与背景
- 爬山算法（Hill Climbing）以邻域结构驱动的局部优化；常作为启发式框架处理连续/离散目标。
-
接口/字段与输入输出语义（据仓库约定）
- hillClimb(x0, neigh, f, budget, strategy) → x_best
- x0 初始解；neigh(x) 生成/采样邻域；f(x) 目标（统一最小化）；budget 为评估/迭代上限；strategy ∈ {best_improvement, first_improvement, stochastic}。
- randomRestartHC(restarts, …)：多次重启取最好。
- withPerturbation(kick_strength)：停滞时对解施加扰动后继续。
- 输出：返回当前搜索到的局部最优解 x_best 及其目标值（按实现可选）。
- hillClimb(x0, neigh, f, budget, strategy) → x_best
-
核心流程与关键要点
- 初始化 x ← x0，评估 f(x)。
- 构造邻域 N(x)：枚举或随机采样若干 y∈N(x)。
- 策略选择：
- best-improvement：取 argmin f(y)；若改善则接受，否则停止。
- first-improvement：顺序扫描遇更优即接受，减少评估。
- stochastic：按概率接受（纯爬山通常仅接受改进）。
- 达到预算或无改进则结束；可重启或扰动后继续。
-
数值稳定性/精度与边界
- 平台与局部最优：适度随机化与扰动有助跳出平台。
- 邻域大小与采样：评估昂贵时优先采样而非枚举。
- 约束处理：连续域用投影/惩罚守约；步长可自适应缩小以细化搜索。
-
复杂度与常见变体
- 复杂度 ~ O(T·|N|·C_eval)；first-improvement 常较省评估。
- 变体：随机重启、多邻域（VNS）、禁忌（Tabu）、与模拟退火（SA，邻近技术）。
-
与相邻技术的取舍
- 与 101-数值算法-黄金分割搜索：后者假设单峰并在一维连续域更高效；爬山更通用但易陷局部。
- 与 104-数值算法-数值积分、105-数值算法-自适应积分：当目标为积分误差驱动的参数调节时，爬山可作为外层调参手段。