人工智能中的爬山算法

• 爬山算法是一种局部搜索算法，它在增加海拔/值的方向上不断移动，以找到山峰或问题的最佳解决方案。当它达到没有邻居具有更高值的峰值时，它终止。

• 爬山算法是一种用于优化数学问题的技术。爬山算法的一个广泛讨论的例子是旅行商问题，在这个问题中我们需要最小化推销员走过的距离。

• 它也被称为贪婪的本地搜索，因为它只查看其良好的直接邻居状态，而不会超出该状态。

• 爬山算法的一个节点有状态和值两个组成部分。

• Hill Climbing 主要在有好的启发式方法可用时使用。

• 在这个算法中，我们不需要维护和处理搜索树或图，因为它只保持一个当前状态。

爬山的特点：

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

• 生成和测试变体：爬山是生成和测试方法的变体。Generate and Test 方法产生的反馈有助于决定在搜索空间中移动的方向。

• 贪心方法：爬山算法搜索朝着优化成本的方向移动。

• 无回溯：它不回溯搜索空间，因为它不记得之前的状态。

爬山的状态空间图：

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

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

状态空间景观中的不同区域：

局部最大值：局部最大值是一种比它的邻居状态更好的状态，但还有另一个状态比它更高。

全局最大值：全局最大值是状态空间景观的最佳可能状态。它具有最高的目标函数值。

当前状态：它是景观图中当前存在代理的状态。

平坦局部最大值：它是景观中的平坦空间，其中当前状态的所有相邻状态都具有相同的值。

肩部：这是一个有上坡边缘的高原地区。

爬山算法的类型：

• 简单的爬山：

• 最陡峭的爬坡：

• 随机爬山：

1. 简单爬山：

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

• 耗时少

• 次优解且不保证解

简单爬山算法：

• 步骤1：评估初始状态，如果是目标状态则返回成功和停止。

• 第 2 步：循环直到找到解决方案或没有可用的新运算符为止。

• 第 3 步：选择一个运算符并将其应用于当前状态。

• 第 4 步：检查新状态：

1. 如果是目标状态，则返回成功并退出。

2. 否则，如果它比当前状态更好，则将新状态分配为当前状态。

3. 否则如果不比当前状态好，则返回步骤2。

• 第五步：退出。

2. Steepest-Ascent 爬山：

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

Steepest-Ascent 爬山算法：

• 步骤1：评估初始状态，如果是目标状态则返回成功并停止，否则将当前状态作为初始状态。

• 第 2 步：循环直到找到解决方案或当前状态不变。

1. 应用新运算符并生成新状态。

2. 评估新状态。

3. 如果是目标状态，则返回并退出，否则将其与 SUCC 进行比较。

4. 如果它比 SUCC 好，则将新状态设置为 SUCC。

5. 如果 SUCC 优于当前状态，则将当前状态设置为 SUCC。

1. 让 SUCC 成为一个状态，使得当前状态的任何后继者都比它更好。

2. 对于适用于当前状态的每个运算符：

• 第五步：退出。

3.随机爬山：

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

爬山算法的问题：

1. 局部最大值：局部最大值是景观中比其每个相邻状态都更好的峰值状态，但也存在另一种高于局部最大值的状态。

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

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

解决方法：高原的解决方法是边搜索边走大步或小步，解决问题。随机选择一个远离当前状态的状态，这样算法就有可能找到非高原区域。

3. 脊：脊是局部极大值的一种特殊形式。它有一个高于周围区域的区域，但它本身有一个斜坡，并且不能一步到位。

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

模拟退火：

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

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