人工智能中的爬山算法

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

它是一种用于优化数学问题的技术。爬山算法的一个广为讨论的例子是旅行商问题，其中我们需要最小化旅行商的旅行距离。

它也被称为贪婪局部搜索，因为它只关注其良好的直接邻居状态，而不是更远的状态。爬山算法的一个节点有两个组成部分，即状态和值。爬山算法主要在有良好启发式时使用。在此算法中，我们不需要维护和处理搜索树或图，因为它只保留一个当前状态。

爬山算法的优点

爬山算法的优点如下。

• 论文的第一部分基于希尔图，可以轻松地将事物组合在一起，非常适合复杂的优化问题。爬山算法是爬山者的首次发明。
• 与树搜索方法相比，它为当前问题状态及其周围的解决方案使用的RAM少得多，树搜索方法将需要检查整个树。因此，这减少了要使用的总内存资源。空间很重要；解决方案应占据一个方便的区域，以尽可能少地消耗内存。
• 当谈到加速爬山时，大多数情况下它会立即带来局部最大值的闭合。如果快速获得快速解决方案的激励胜过获得全局最大值，那么这就是途径。

爬山算法的缺点

• 关于爬山，似乎有些解决方案无法找到最佳点并停留在局部峰值，特别是在需要通过许多目标函数在复杂环境中进行优化的地方。
• 它也很肤浅，因为它只寻找周围的解决方案，而不会更进一步。它可能基于局部最优解而走错了路，因此 Godbole 需要首先远离当前位置。
• 最终结果很可能在很大程度上取决于初始设置和状态，这是最敏感的因素。这意味着在这种情况下，时间是人们动态发展技能的球体周长，决定了他们的成功。

爬山算法的特点

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

• 生成和测试变体：爬山算法是生成和测试方法的一种变体。生成和测试方法会产生反馈，有助于决定在搜索空间中移动的方向。
• 贪婪方法：爬山算法搜索朝着优化成本的方向移动。
• 无回溯：它不会回溯搜索空间，因为它不记住以前的状态。
• 确定性：爬山是一种确定性优化算法，这意味着在相同的初始条件和相同的问题下，它将始终产生相同的结果。其操作没有随机性或不确定性。
• 局部邻域：爬山是一种在当前解决方案周围小范围内操作的技术。它通过进行小的、渐进的变化来探索与当前状态密切相关的解决方案。这种方法使其能够找到比当前解决方案更好的解决方案，尽管它可能不是全局最优解。

爬山算法的状态空间图

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

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

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

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

爬山算法的类型

• 简单爬山算法
• 最陡峭上升爬山算法
• 随机爬山算法

1. 简单爬山算法

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

• 耗时更少
• 解决方案次优，且不保证找到最优解

简单爬山算法的算法

• 步骤 1：评估初始状态。如果它是目标状态，则返回成功并停止。
• 步骤 2：循环直到找到解决方案或没有新的操作符可应用。
• 步骤 3：选择并对当前状态应用一个操作符。
• 步骤 4：检查新状态
  1. 如果它是目标状态，则返回成功并退出。
  2. 否则，如果它比当前状态更好，则将新状态分配为当前状态。
  3. 否则，如果它不比当前状态好，则返回步骤 2。
• 步骤 5

2. 最陡峭上升爬山算法

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

最陡峭上升爬山算法

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

• 步骤 5

3. 随机爬山算法

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

混合方法

尽管爬山算法是一种非常高效且有用的局部搜索技术，但它存在一些缺点，包括高原、山脊和局部最大值陷阱。为了克服这些限制并产生更好的优化解决方案，专家和从业者通常采用混合方法，将爬山算法与其他算法结合起来，以解决其缺点。

1. 爬山算法与模拟退火结合

模拟退火技术将受控随机性引入搜索过程。模拟退火根据随机概率函数拒绝适应度较差的状态；爬山算法只拒绝那些提高适应度（在本例中，值更高）的状态。如果爬山算法通过接受小幅下降的值而达到局部峰值，模拟退火可以通过此来突破局部峰值，并允许搜索探索解决方案空间的其他区域。

2. 爬山与遗传算法

变异、交叉和选择是遗传算法（GA）使用的三种技术。爬山是遗传算法中的一种局部优化器。在通过交叉和变异创建新解之后，可以使用爬山算法迭代或“改进”该解以进行增强。遗传算法共同提供了更好的解质量和更快的收敛时间；爬山局部搜索可以协同工作。

3. 模因算法中的爬山

模因算法是进化算法的复杂混合体，它将其他类型的个体学习或局部搜索与爬山等局部精炼方法相结合。在进入下一代之前，模因算法中的每个候选解都要经过爬山算法的局部改进。由于这种方法是平衡的，因此搜索过程更智能：遗传算法允许探索（通过随机搜索变异和交叉），而爬山算法提供利用（通过局部搜索）。

爬山算法中的问题

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

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

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

解决方案：解决平原的方案是在搜索时采取大步或非常小的步，以解决问题。随机选择一个远离当前状态的状态，这样算法就有可能找到非平原区域。

3. 山脊：山脊是局部最大值的一种特殊形式。它有一个高于其周围区域的区域，但它有坡度，并且不能通过一次移动到达。

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

模拟退火

一个从不向较低值移动的爬山算法不能保证是完整的，因为它可能会陷入局部最大值。如果算法通过移动后继节点执行随机游走，那么它可能完成但效率不高。模拟退火是一种既能提高效率又能保证完整性的算法。

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

爬山算法的应用

爬山技术已广泛应用于人工智能和优化领域。它通过系统地测试选项并选择最合适的一个，通过耦合研究活动系统地解决这些问题。一些应用如下：

一些应用如下

1. 机器学习

机器学习模型的微调通常是进行超参数优化，为模型提供关于如何学习和行为的指导。另一个服务于相同目的的练习是爬山训练。逐步调整超参数并根据各自达到的本质进行评估是爬山方法的核心。

2. 机器人技术

在机器人技术中，爬山技术对于在物理环境中漫游的人工代理非常有用，其路径在到达目的地之前会进行调整。

3. 网络设计

该工具可用于电信行业和计算机网络中网络形式、过程和拓扑的改进。这种方法消除了冗余，从而通过研究和调整网络配置来提高网络的效率。它促进了更好的协作、效率和各种通信系统的可靠性。

4. 游戏玩法

尽管爬山算法可以通过开发有助于获得最高分数的策略在游戏 AI 中达到最佳效果。

5. 自然语言处理

该软件有助于调整算法，使软件能够高效地处理手头的任务，例如文本摘要、语言翻译和语音识别。这些能力使其成为许多应用的重要工具。

实施

现在我们将尝试借助爬山算法来最大化函数：f (x) = -x² + 5

代码