爬山(Hill Climbing)算法是一种局部搜索算法，它在增加高度/值的方向上连续移动，以找到山峰或最佳解决问题的方法。它在达到峰值时终止，其中没有邻居具有更高的值。
爬山算法是一种用于优化数学问题的技术。其中一个广泛讨论的爬山算法的例子是旅行商问题，其中我们需要最小化推销员的行进距离。
它也称为贪婪的本地搜索，因为它只关注其良好的直接邻居状态而不是超越它。爬山算法的节点有两个组成部分，即状态和值。
Hill Climbing主要用于有良好启发式的时候。在此算法中，不需要维护和处理搜索树或图形，因为它只保留单个当前状态。

爬山算法的特点

以下是爬山算法的一些主要特征：

• 生成和测试变体：Hill Climbing是Generate和Test方法的变体。生成和测试方法产生反馈，有助于确定在搜索空间中移动的方向。
• 贪婪的方法：爬山算法搜索朝着优化成本的方向发展。
• 没有回溯：它不会回溯搜索空间，因为它不记得以前的状态。

爬山的国家空间图

状态空间景观是爬山算法的图形表示，其示出了算法的各种状态和目标函数/成本之间的图。

在Y轴上，我们采用了可以是目标函数或成本函数的函数，以及x轴上的状态空间。如果Y轴上的函数是成本，那么搜索的目标是找到全局最小值和局部最小值。如果Y轴的函数是目标函数，那么搜索的目标是找到全局最大值和局部最大值。

状态的不同区域

局部最大值：局部最大值是一个比其邻居状态更好的状态，但也有另一个高于它的状态。
全局最大值：全局最大值是状态空间最佳状态。它具有最高的目标函数值。
当前状态：它是当前存在代理的横向图中的状态。
平局局部最大值：它是景观中的平坦空间，其中当前状态的所有邻居状态具有相同的值。
肩部：这是一个具有上坡边缘的高原地区。

爬山类型算法：

• 简单爬山
• Steepest-Ascent爬山
• 随机爬山

1 简单爬山

简单的爬山是实现爬山算法的最简单方法。它一次只评估邻居节点状态，并选择第一个优化当前成本并将其设置为当前状态的状态。它只检查它的一个后继状态，如果它发现优于当前状态，则移动其他状态。该算法具有以下特征：

• 减少耗时
• 不太保证不太理想的解决方案和解决方案

简易爬山算法：

• 步骤1：评估初始状态，如果是目标状态，则返回成功并停止。
• 步骤1：循环直到找到解决方案或没有新的运算符可供应用。
• 步骤3：选择并将运算符应用于当前状态。

• 步骤4：检查新状态：

  • 如果是目标状态，则返回成功并退出。
  • 否则，如果它优于当前状态，则将新状态指定为当前状态。
  • 否则如果不比当前状态好，则返回步骤2。
• 步骤5：退出

Steepest-Ascent爬坡：

最陡峭的Ascent算法是简单爬山算法的变体。该算法检查当前状态的所有相邻节点，并选择最接近目标状态的一个邻居节点。该算法在搜索多个邻居时会消耗更多时间

最速爬坡爬山算法：

• 步骤1：评估初始状态，如果是目标状态，则返回成功并停止，否则将当前状态作为初始状态。
• 步骤2：循环直到找到解决方案或当前状态不变。
  • 让SUCC成为一个状态，使得当前状态的任何继承者都会比它更好。
  • 对于适用于当前状态的每个运算符：
    • 应用new运算符并生成新状态。
    • 评估新的状态。
    • 如果是目标状态，则返回并退出，否则将其与SUCC进行比较。
    • 如果它优于SUCC，则将新状态设置为SUCC。
    • 如果SUCC优于当前状态，则将当前状态设置为SUCC。
• 步骤3：退出

随机爬山：

随机爬山在移动之前不会检查其所有邻居。相反，该搜索算法随机选择一个邻居节点并决定是将其选择为当前状态还是检查另一个状态。

爬山算法存在的问题

1. 局部最大值：局部最大值是景观中的峰值状态，其优于每个相邻状态，但是还存在另一个高于局部最大值的状态。

解决方案：回溯技术可以解决状态空间景观中的局部最大值。创建有前途的路径列表，以便算法可以回溯搜索空间并探索其他路径。

2.高原：高原是搜索空间的平坦区域，其中当前状态的所有邻居状态包含相同的值，因为该算法没有找到任何最佳移动方向。在高原地区可能会失去爬山搜索。

解决方案：高原的解决方案是在搜索时采取大步骤或非常小的步骤来解决问题。随机选择远离当前状态的状态，因此算法可能找到非平稳区域。

3.山脊：山脊是局部最大值的特殊形式。它的面积高于周围区域，但本身有一个斜坡，一次搬不到。

解决方案：通过使用双向搜索或向不同方向移动，可以改善此问题。

模拟退火

爬山算法从不会向较低的值移动，因此可以保持不完整，因为它可能会卡在局部最大值上。如果算法应用随机游走，通过移动后继，那么它可能完成但效率不高。模拟退火是一种既能提高效率又能实现完整性的算法。

在机械术语中，退火是将金属或玻璃硬化至高温然后逐渐冷却的过程，因此这允许金属达到低能晶态。在模拟退火中使用相同的过程，其中算法选择随机移动，而不是选择最佳移动。如果随机移动改善了状态，则它遵循相同的路径。否则，算法遵循概率小于1的路径或者下坡移动并选择另一条路径。