改进爬山算法之一：随机化爬山法（Stochastic Hill Climbing，SHC）
随机化爬山法（Stochastic Hill Climbing），也被称为随机爬山法，是一种基于搜索算法的优化方法，是爬山算法的一个变种，它通过引入随机性来减少算法陷入局部最优解的风险，并增加搜索解空间的能力。这种方法特别适合于解决那些具有多个局部最优解的优化问题。
一、算法思想
爬山算法在选择下一步时是采用贪心策略，即在邻域空间中寻找最优解作为下一步，容易陷入局部最优解。随机化爬山法是对爬山算法的改进，其主要思想是在上山移动中随机选择下一步，选择的概率随着上山移动的陡峭程度而变化。这意味着，在搜索过程中，算法会以一定的概率接受比当前解更差的解，从而增加了跳出局部最优解的机会。如下图中的虚线，在邻域搜索空间N(x)中，随机选择一个方向作为下一步。
图1 随机爬山法演示图
二、算法步骤
1. 初始化：随机选择一个初始解作为搜索起点。
2. 评估：计算当前解的适应度值，即目标函数的值。
3. 迭代：
（1）在每次迭代中，随机生成一个或多个邻域解。
（2）比较邻域解与当前解的适应度值。
（3）根据一定的概率选择接受邻域解作为新的当前解。这个概率可能与邻域解与当前解的适应度值差异有关，也可能是一个固定的概率。
图2 邻域搜索空间N(x)中随机选择
（4）如果邻域解的适应度值更好，则通常接受该邻域解作为新的当前解。如果邻域解的适应度值较差，则根据一定的概率决定是否接受。
4. 终止：当达到预设的迭代次数或找到满足要求的最优解时，停止迭代。
三、算法数学表达
（1）初始化解：设初始解为，通常是在解空间内随机选择的。
（2）邻域解生成：对于当前解，生成一个或多个邻域解
。邻域解的生成方式取决于问题的具体性质和搜索空间的结构。
（3）适应度评估：计算当前解和邻域解
的适应度值，分别记为
和
。
（4）接受概率：定义一个接受概率，用于决定是否接受邻域解作为新的当前解。这个概率可能与邻域解与当前解的适应度值差异有关，也可能是一个固定的概率。
一种常见的接受概率公式是：