路径规划之启发式算法之二十四：爬山算法（Hill Climbing Algorithm，HCA）
爬山算法（Hill Climbing Algorithm）是一种启发式的基于局部最优解的搜索算法，用于在给定的搜索空间中寻找全局最优解或足够好的解。它属于局部搜索算法，通常用于解决优化问题，包括连续和离散问题。
一、定义与原理
爬山算法模拟了爬山的过程，从某个随机起始点开始，不断向更高的点（即更好的解）移动，直到达到一个局部最高点（即局部最优解）。它基于贪心策略，每次迭代都选择当前状态下相邻解中最好的一个。
图1 爬山算法演示图
二、算法流程
（1）初始化：选择一个随机解作为起始点，并计算其适应度（即目标函数值）。
（2）选择相邻解：随机或按照一定的规则选择一个相邻的解进行移动。
（3）计算适应度：计算相邻解的适应度。
（4）比较与更新：如果相邻解的适应度优于当前解，则接受相邻解作为当前解，并继续搜索；否则，保持当前解不变，并尝试其他相邻解。
（5）终止条件：当满足某个终止条件时（如达到最大迭代次数、解的质量在一定次数内没有明显改善等），停止搜索并返回当前解作为结果。
三、算法数学公式
爬山算法的数学公式通常与具体的目标函数相关，假设我们希望最大化目标函数
，那么爬山算法可以表示为以下步骤：
（1）初始化：选择一个初始解，计算其目标函数值
。
（2）邻域搜索：生成当前解的邻域解集合
。邻域解可以通过对当前解进行微小的修改得到，例如，在连续空间中，邻域解可以是当前解加上或减去一个小的步长（x+step、x-step，可以是上下左右4个方向）。
图2 搜索邻域
（3）选择更优解：从邻域解集合中选择一个使目标函数值最大的解
，即：
（4）更新当前解：如果比
更优（即更大），则将
作为新的当前解；否则，停止搜索或尝试其他策略。
（5）重复：重复步骤2到4，直到达到终止条件（如达到最大迭代次数或找不到更优的邻域解）。
在具体实现中，数学公式可能涉及更多的细节，如步长的选择、邻域解生成的策略等。这些细节会影响算法的性能和结果。
算法流程图如下：
图3 爬山算法流程图