本文概述
- 爬山算法是一种局部搜索算法，可在海拔/值不断增加的方向上连续移动以找到山峰或对该问题的最佳解决方案。当它达到一个峰值，没有邻居有更高的值时，它将终止。
- 爬山算法是一种用于优化数学问题的技术。爬山算法的一个被广泛讨论的例子是旅行推销员问题，其中我们需要最小化推销员的行进距离。
- 它也被称为贪婪本地搜索，因为它只查找其良好的直接邻居状态，而没有超出此范围。
- 爬山算法的节点具有状态和值两个部分。
- 当有良好的启发式功能时，通常会使用“爬山”。
- 在此算法中，我们不需要维护和处理搜索树或图形，因为它仅保留一个当前状态。
爬山的特点
以下是爬坡算法的一些主要功能：
- 生成和测试变量：爬山是“生成和测试”方法的变量。生成和测试方法会产生反馈，有助于确定在搜索空间中向哪个方向移动。
- 贪婪方法：爬山算法搜索会朝着优化成本的方向发展。
- 不回溯：不回溯搜索空间，因为它不记得以前的状态。
爬山的状态空间图
状态空间景观是爬山算法的图形表示，它显示了算法的各种状态与目标函数/成本之间的关系图。
在Y轴上，我们采用的函数可以是目标函数或成本函数，而在x轴上则是状态空间。如果Y轴上的函数是成本，则搜索的目标是找到全局最小值和局部最小值。如果Y轴的函数是“目标函数”，则搜索的目标是找到全局最大值和局部最大值。
爬山状态空间图
局部最大值：局部最大值是一个比其邻居状态更好的状态，但还有另一个状态高于其邻居状态。
全局最大值：全局最大值是状态空间景观的最佳状态。它具有最高的目标函数值。
当前状态：这是景观图中当前存在代理的状态。
平坦的局部最大值：这是景观中的平坦空间，当前状态的所有相邻状态都具有相同的值。
肩膀：这是一个高原地区，有上坡的边缘。
爬山算法的类型
- 简单的爬坡：
- 最陡的爬坡：
- 随机爬山：
1.简单的爬坡：
简单的爬山是实现爬山算法的最简单方法。它一次只评估邻居节点状态，然后选择第一个优化当前成本的状态并将其设置为当前状态。它仅检查它的一个后继状态，如果发现比当前状态更好，则将其他状态保持在同一状态。该算法具有以下特点：
- 耗时少
- 最佳解决方案较少，无法保证解决方案
简单爬坡算法：
- 步骤1：评估初始状态，如果是目标状态，则返回成功并停止。
- 步骤2：循环直到找到解决方案或没有新的运算符可应用。
- 步骤3：选择一个运算符并将其应用于当前状态。
- 步骤4：检查新状态：如果是目标状态，则返回成功并退出。否则，如果它比当前状态更好，则将新状态分配为当前状态。如果不是比当前状态更好，则返回步骤2。
- 步骤5：退出。
2.最陡峭的登山：
最陡峭上升算法是简单爬山算法的一种变体。该算法检查当前状态的所有相邻节点，并选择一个最接近目标状态的邻居节点。该算法在搜索多个邻居时会消耗更多时间
最陡峭爬坡算法：
- 步骤1：评估初始状态，如果是目标状态，则返回成功并停止，否则将当前状态设为初始状态。
- 步骤2：循环直到找到解决方案或当前状态不变。假定SUCC为一个状态，以使当前状态的任何后继者都比它更好。对于适用于当前状态的每个运算符：应用新运算符并生成一个新状态。评估新状态。如果是目标状态，则将其返回并退出，否则将其与SUCC进行比较。如果它优于SUCC，则将新状态设置为SUCC。如果SUCC优于当前状态，则将当前状态设置为SUCC。
- 步骤5：退出。
3.随机爬山：
随机爬山不会在移动之前检查所有邻居。而是，该搜索算法随机选择一个邻居节点，并决定是将其选择为当前状态还是检查另一状态。
爬山算法中的问题
1.局部最大值：局部最大值是景观中的一个峰值状态，它比其相邻状态中的每个状态都好，但是也存在另一个状态，该状态高于局部最大值。
解决方案：回溯技术可以作为状态空间景观中局部最大值的解决方案。创建有希望的路径的列表，以便算法可以回溯搜索空间并探索其他路径。
2.高原：高原是搜索空间的平坦区域，当前状态的所有相邻状态都包含相同的值，因为该算法无法找到任何最佳移动方向。在高原地区爬山搜索可能会丢失。
解决方案：高原的解决方案是在搜索时采取大步或很少步来解决问题。随机选择一个远离当前状态的状态，因此该算法有可能找到非平稳区域。
3.山脊：山脊是局部最大值的一种特殊形式。它的面积比周围的区域高，但它本身具有坡度，无法一口气到达。
解决方案：通过使用双向搜索或通过不同方向移动，我们可以改善此问题。
模拟退火：
爬山算法永远不会向较低值移动，因为它可能会卡在局部最大值上，因此它保证是不完整的。如果算法通过移动后继者来应用随机游走，则它可能会完成但效率不高。模拟退火是同时产生效率和完整性的算法。
在机械术语中，退火是将金属或玻璃硬化至高温然后逐渐冷却的过程，因此这可使金属达到低能晶体状态。在模拟退火中使用相同的过程，在该过程中，算法选择随机移动，而不是选择最佳移动。如果随机移动改善了状态，则它遵循相同的路径。否则，该算法将遵循概率小于1的路径，或者它会下坡并选择另一条路径。
