人工智能中的局部搜索算法

引言

计算机推理中的局部搜索计算是一组优化算法，通过对初始解决方案进行小的迭代改进来寻找问题的最佳解决方案。这些算法用于解决优化问题，在这些问题中，找到精确解要么困难，要么计算成本高昂。爬山法、模拟退火、禁忌搜索和遗传算法是不同类型的局部搜索算法的几个例子。这些算法中的每一种的工作方式略有不同，但它们都遵循相同的基本方法：迭代地创建新解决方案并将它们与当前解决方案进行比较，以确定它们是否更优。

计算机推理中的局部搜索算法是人工智能领域的一项关键工具，并经常用于解决优化问题。局部搜索算法的应用包括调度、路由和资源分配。它们对于搜索空间非常大的问题特别有用，并且可以用于解决离散和连续优化问题。

局部搜索

节点以不同的方式系统地扩展，通过有指导的和无指导的搜索

• 将不同的路径存储在内存中，并
• 选择最合适的路径，

因此，需要一个解状态来引导目标节点。然而，在这些“经典搜索算法”之外，还有一些“局部搜索算法”，它们在某种程度上只考虑到达目标节点所需的解状态，而忽略了路径成本。与这些路径不同，局部搜索算法通过遍历单个当前节点并通常遵循该节点的邻居来完成其任务。

为了解决复杂的优化问题，局部搜索算法通常与其他优化方法（如约束满足或线性规划）结合使用。由于它们可以快速收敛到接近最优解的解，即使它们找不到精确的最优解，它们对于搜索空间非常大的问题也特别有帮助。

局部搜索算法是如何工作的？

局部搜索算法适用于完美优化问题。任何能提供解决方案的节点都可以被称为完美优化问题。然而，目标函数的目的是在所有这些状态中识别出最好的状态。不幸的是，纯粹的优化问题在从当前状态转向目标状态方面无法产生好的解决方案。

局部搜索算法的一个关键优势在于它们可以非常高效，特别是与详尽搜索或动态规划等其他优化技术相比。这是因为局部搜索算法只需要探索整个搜索空间的一小部分，这可以节省大量的时间和计算资源。

然而，局部搜索算法的一个最大限制是它们可能会陷入局部最优解，这些解比它们的所有邻居都好得多，但并非整体上最佳的可能解。为了克服这个限制，许多局部搜索算法使用不同的技术，如随机化、记忆或多个起始点，以帮助它们逃离局部最优解并找到更好的解决方案。

操作局部搜索算法

局部搜索算法是一类优化算法，通过对问题解决方案进行小的、局部的更改来迭代地改进它。以下是局部搜索算法的常见步骤：

• 初始化：算法以问题的初始解决方案开始。该解决方案可以随机生成或使用启发式方法生成。
• 评估：使用目标函数评估初始解决方案的质量。目标函数根据问题的约束和要求衡量解决方案的好坏。
• 局部搜索：算法通过对当前解决方案进行小的修改来生成邻近解决方案。这些修改可以是随机的，也可以由启发式方法指导。
• 确定：使用目标函数评估局部解决方案，并选择最佳解决方案作为新的当前解决方案。
• 停止：当满足停止条件时，算法停止。此条件可以是最大迭代次数、目标函数的有限值或时间限制。

局部搜索算法通常用于计算上不切实际或不可能找到精确解的情况。旅行商问题、背包问题和图着色问题是这些问题的许多例子。

局部搜索算法

局部搜索算法是人工智能中的一类优化算法，它通过搜索其邻近解决方案来迭代地改进给定解决方案。局部搜索算法的主要规则是，从第一个解决方案开始，然后移动到一个更好、更高、更强的、改进的、更好的解决方案，直到找不到更好的解决方案。有几种类型的局部搜索算法，其中一些列在下面。

爬山法

爬山法是人工智能中一种用于优化和人工智能问题的局部搜索算法。它是一种启发式搜索算法，从初始解决方案开始，通过一次一个小的修改来迭代地改进它，并选择能够最大程度改进解决方案的最佳修改。“爬山法”一词指的是爬山以到达顶峰（最优解）的类比。该算法通过朝着目标函数增加值迈出渐进的步伐（或“爬升”）来工作，直到达到局部最大值，此时无法再获得收益。爬山算法的基本步骤如下：

• 从初始解决方案开始。
• 评估目标函数以确定解决方案的质量。
• 通过对当前解决方案进行小的修改来创建一组候选解决方案。
• 评估每个候选解决方案的目标函数。
• 选择最能改进目标函数的候选解决方案。
• 重复步骤 3-5，直到无法进行进一步改进。

爬山法的简单性和有效性是其主要优势之一，因为它不需要创建和维护搜索树。然而，其主要缺点是它可能会陷入局部最优解，在这些局部最优解中，如果不先进行非改进性移动就无法进一步改进。为了解决这个问题，已经提出了爬山算法的多种变体，包括模拟退火和禁忌搜索。

局部束搜索

一种名为局部束搜索的启发式搜索算法被应用于优化和人工智能问题。它是标准爬山算法的一个变体，其中当前状态是 k 个解决方案的初始集合（或“束”），而不是单个解决方案。

该算法在每个周期内从当前状态创建一组候选解决方案，评估这些解决方案，并选择最好的 k 个作为新的当前状态。

局部束搜索算法的基本步骤如下：

• 从 k 个随机生成的解决方案开始。
• 评估每个解决方案的目标函数。
• 通过对当前状态进行小的修改来创建一组候选解决方案。
• 评估每个候选解决方案的目标函数。
• 选择最好的 k 个候选解决方案作为新的当前状态。
• 重复步骤 3-5，直到满足停止条件。

局部束搜索与传统的爬山法相比，能够同时探索多个搜索路径，从而增加了找到全局最优解的可能性。尽管如此，它仍然可能会陷入局部最优解，尤其是在搜索空间巨大或复杂的情况下。

为了解决这个问题，已经提出了局部束搜索算法的多种变体，包括随机束搜索和带重启动的束搜索。通过这些变体，搜索过程被赋予了随机或重复重启动，这有助于算法逃离局部最优解并探索搜索空间的新区域。

模拟退火

模拟退火是一种用于优化和人工智能问题的启发式搜索算法。通过允许算法偶尔接受不改进的移动，这种爬山算法的变体可以避免陷入局部最优解的问题。

算法从初始解决方案开始，通过对初始解决方案进行小的修改来迭代地生成新解决方案。算法在每个周期后评估新解决方案的目标函数，并根据旧解决方案和新解决方案的目标函数值之间的差异以及温度参数，使用概率函数决定接受还是拒绝它。

模拟退火算法的基本步骤如下：

1. 从初始解决方案开始。
2. 将初始温度设置为一个较高的值。
3. 重复以下步骤，直到满足停止条件：
   
   • 通过对当前解决方案进行小的调整来创建一个新解决方案。
   • 评估新解决方案的目标函数。
   • 如果新解决方案改进了目标函数，则接受它作为新的当前解决方案。
   • 如果新解决方案没有改进目标函数，则以取决于当前解决方案和新解决方案的目标函数值之间的差异以及当前温度的概率来接受它。
   • 根据冷却计划降低温度。
4. 返回当前解决方案作为最终解决方案。

模拟退火算法最重要的规则是通过调整温度参数来控制搜索过程中的随机性程度。高温通过增加算法接受非改进性移动的倾向来鼓励算法探索搜索空间的新区域。随着温度的降低，算法变得更加具体，并专注于改进解决方案。

模拟退火已被成功应用于广泛的优化问题，例如旅行商问题和车间调度问题。然而，为了获得良好的性能，它需要仔细调整温度和冷却计划参数。

Travelling Salesman Problem

旅行商问题 (TSP) 是组合优化问题的一个著名例子，其目标是在起始城市和给定城市集合之间确定最快的路线。由于这是一个 NP-hard 问题，目前还没有已知的算法可以在多项式时间内解决它。

由于其能够有效地搜索大型解决方案空间，人工智能中的局部搜索算法通常用于解决 TSP。TSP 的局部搜索算法通过从初始解决方案开始，然后通过一次一个小的修改来逐步改进它，直到不再可能进行修改。

2-opt 局部搜索算法是一种流行的 TSP 局部搜索算法，它以最小化总距离的方式连接剩余的节点。它涉及从当前解决方案中移除两条边，并用两条不同的边替换它们。该算法一直进行，直到不再有改进的空间。

Lin-Kernighan 算法是另一个流行的 TSP 局部搜索算法，它涉及一系列 2-opt 移动，这些移动由基于边交换和节点合并的一组启发式方法指导。尽管该算法比 2-opt 更复杂，但它可以产生更优的结果。

2-opt 和 Lin-Kernighan 算法都是在一次处理单个解决方案的局部搜索算法。然而，为了提高找到全局最优解的可能性，已经提出了这些算法的各种变体，例如禁忌搜索和模拟退火。这些算法引入了额外的机制来逃离局部最优解并探索搜索空间的新区域。

结论

局部搜索算法通过进行小的修改来迭代地改进单个解决方案。它们广泛用于组合优化问题，以从大量可能的解决方案中找到最佳解决方案。局部搜索算法通常简单且高效，并且可以处理大型解决方案空间。然而，它们容易陷入局部最优解，此时解决方案不是全局最优解。

为了克服这个限制，已经提出了局部搜索算法的各种变体，例如禁忌搜索、模拟退火和遗传算法。这些变体引入了额外的机制来探索搜索空间和逃离局部最优解，但代价是增加了复杂性和计算资源。局部搜索算法是解决广泛优化问题的重要工具，并且仍然是人工智能和运筹学中的一个活跃研究领域。