人工智能中的爬山算法

在人工智能中，爬山算法是一种用于优化数学问题的算法。它不断增加其值直到达到最佳解决方案。

什么是爬山算法？

爬山算法可以定义为一种局部搜索算法，它是启发式搜索算法的一种形式。它不断从当前状态或初始状态向上移动，直到达到最佳解决方案或达到峰值。让我们用一个通用示例来更好地理解。

假设X先生正在爬山。X先生会一直爬山直到到达山顶。X先生现在在A点，所以X先生的当前位置是A。后来他在B点，这是一个比A点更好的位置。所以X先生的当前位置现在指向B。这个过程一直持续到他到达山顶C点。因此，在我们的算法中，初始当前状态是A，如果得到比A更好的状态B，算法会将当前状态从A更改为B，这将一直持续到达到最佳解决方案或最佳点。最初，起点被称为山的底部，它是一个非最优状态。它不断尝试攀爬或迭代，直到达到峰值或某个预设条件。改进当前状态的过程可以称为攀爬。这就是它被称为爬山算法的原因。

爬山算法可以被认为是一种内存高效的解决大型计算问题的方法。爬山方法的最佳示例是旅行商问题。爬山方法可能不是找到最优解决方案的方法，但它很擅长计算局部最小值/最大值。

状态空间图

上面是状态和目标函数的图形表示。如果y轴表示目标函数，则我们可以建立全局/局部最大值。如果y轴用于表示成本函数，我们可以建立局部/全局最小值。x轴用于表示状态空间。

• 局部最大值/最小值：它是一种比邻近状态更好的状态。但它不是存在的最佳可能状态。它之所以更好，是因为目标函数/成本函数的值高于其邻居。
• 全局最大值/最小值：它是最佳可能状态。此处目标函数/成本函数的值最高。
• 肩部：一个向上延伸边缘的平坦区域。
• 平坦局部最大值：一个平坦区域，其中邻近解决方案具有相同的值。

爬山算法的特点

以下是爬山算法的关键特点：

1. 贪婪方法：算法总是朝着优化成本的方向移动。这使得算法能够建立局部最小值/最大值。
2. 无回溯：它一直向前移动。它作用于当前状态并查看后续状态。从不回头看以前的状态。
3. 反馈机制：生成-测试算法的一种变体。它有助于决定下一步行动。是向上爬还是向下走。
4. 增量变化：通过增量变化，算法改进当前状态。

爬山算法的工作原理

它是遗传算法最简单的实现。与更传统的遗传算法相比，它的迭代速度更快，但不如后者彻底。
爬山算法的工作原理非常简单。让我们简单描述一下它的工作方式。

1. 从一个空解开始。这将被视为“最初的最佳解决方案”。
2. 评估当前解决方案。
3. 随机变异解决方案。
4. 评估新解决方案，如果发现它是最佳解决方案，则用它替换之前的解决方案。转到步骤2并重复2和3。

爬山算法的类型

以下是爬山算法的类型：

1. 简单爬山算法 

它是爬山方法最简单的形式，其中评估邻近解决方案。如果邻近状态的值大于当前状态，则算法会将此邻近状态设置为当前状态。它一次只检查一个后继状态。该算法的特点如下：

• 耗时较少
• 最优解较少或解决方案次优
• 不保证解决方案。
• 需要较少的计算能力。

简单爬山算法的算法。

步骤1：创建 CURRENT 节点、NEIGHBOR 节点和 GOAL 节点。

步骤2：评估 CURRENT 节点，如果它是 GOAL 节点，则停止并返回成功。

步骤3：否则将 NEIGHBOR 节点设置为 CURRENT 节点并继续前进。

步骤4：循环直到 CURRENT 节点 = GOAL 节点或没有操作符可应用。

步骤5：退出。

2. 最陡峭上升爬山算法

它是简单爬山算法的一种变体。在这里，算法将检查当前状态的所有邻近节点，并选择值最接近目标状态的节点。由于它搜索所有邻近节点，因此时间消耗高，功耗也高。

最陡峭上升爬山算法的算法

步骤1：创建 CURRENT 节点、NEIGHBOR 节点和 GOAL 节点。

步骤2：评估 CURRENT 节点，如果它是 GOAL 节点，则停止并返回成功。

步骤3：否则设置一个状态(X)，其中当前状态的后继值高于它。

步骤4：使用新操作符并生成新解决方案。

步骤5：将此新解决方案与 GOAL 节点进行比较。如果是，则退出程序；否则与状态(X)进行比较。

步骤6：如果新状态高于状态(X)，则将其设置为X。

步骤7：继续循环。重复步骤4和5。

步骤8：退出。

3. 随机爬山算法

在这里，算法从不关注所有邻近节点。它随机选择一个邻近节点来检查它是否比当前节点更好。随机选择邻近节点是根据一些预定义的标准进行的。

随机爬山算法的算法

步骤1：创建 CURRENT 节点、NEIGHBOR 节点和 GOAL 节点。

步骤2：评估 CURRENT 节点，如果它是 GOAL 节点，则停止并返回成功。

步骤3：否则随机选择一个 NEIGHBOR 节点并评估 NEIGHBOR。

以概率 选择 NEIGHBOR。

步骤4：如果 NEIGHBOR = GOAL 返回成功并退出。否则设置 CURRENT 节点=NEIGHBOR 并继续循环。重复步骤2、3、4。

步骤5：退出。

4. 随机重启爬山算法

这里采用了一种尝试和再尝试的策略。在此，节点被迭代搜索，然后在每一步选择最佳节点。这将一直持续到找到目标。该过程的成功取决于山的形状。如果只有几个高原、局部最大值和山脊，就很容易到达目的地。它也被称为霰弹枪爬山算法。一个成功概率为p的算法运行n次，或者找到一个解，将以概率 解决。

爬山算法的问题

爬山算法在三个主要区域无法达到最优解。

1. 局部最大值

   在局部最大值点，算法的贪婪接近特性将导致终止，因为邻近状态的值低于当前状态。但这并不是最佳解决方案，存在一个全局最大值。

    

   

   解决方案：可以使用回溯技术来克服局部最大值问题。访问过的状态被列出，如果搜索到达一个不需要的状态，它可以回溯并探索一条新路径。

2. 山脊

   山脊上的点总是看起来像一个山峰。从山脊上的一个点出发的所有可能移动都是向下的。因此，算法将从这样的状态终止。

   

   解决方案：同时向多个方向移动。

3. 高原

   在高原上，所有邻居的值都相同。因此很难选择最佳方向。

   

   解决方案：大幅跳跃以到达非高原空间。

模拟退火

众所周知，爬山算法从不进行向下移动或向较低值的移动。并且它是不完整的，因为它会停留在局部最大值。如果算法进行随机游走，那么它可能是完整的，但效率不高。

模拟退火是一种解决方案或一种允许向下移动以逃离局部最大值的算法。.

退火可以定义为将金属加热到高温然后逐渐冷却的过程，这样金属将机械地达到低能量晶体状态。模拟退火中使用了类似的过程。在这里，算法选择一个随机移动而不是最佳移动。如果选择的随机移动改进了状态，则遵循相同的路径。否则，它将以小于1的概率遵循路径，或者它将向下移动并选择另一条路径。

人工智能中爬山算法的优势。

• 适用于路由相关问题，如旅行商问题、作业调度、芯片设计和投资组合管理。
• 在有限的计算能力下，它可用于解决优化问题。
• 比其他搜索算法更高效。

爬山算法的应用

以下领域可以使用爬山算法。

市场营销

它可用于生成良好的营销计划。该技术广泛用于解决旅行商问题。它可以有效地建立局部最小值。

机器人技术

它可用于增强机器人中不同组件和系统的协调。

作业调度

在作业调度中，系统资源分配给不同的任务，并且作业从一个节点迁移到另一个节点。爬山算法可用于建立正确的路由。