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

仿真资料吧

2025年10月25日 17:58

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

本地搜索算法在人工智能中很重要，因为它们可以快速找到好的答案，尤其是当找到完美的解决方案需要太长时间或太多的努力时。它们对于检查每个可能的选项不切实际的大问题或复杂问题很有用。

它只关注当前的解决方案和与之直接相关的解决方案，而不是到处寻找。
非常适合现实世界的任务，如谜题、时间表或路线查找。

局部搜索算法的工作原理

第 1 步：选择一个起点：从一个可能的解决方案开始，该解决方案通常是随机的，但有时基于规则。

第 2 步：寻找邻居：

邻居是我们可以通过对当前解决方案进行小而简单的更改来获得的类似解决方案。
例如，在拼图中，交换两块会创建一个邻居。

第 3 步：比较：环顾四周，看看是否有更好的邻居。

第 4 步：移动：如果存在更好的邻居，请移动到它，使其成为我们新的“当前”解决方案。

步骤5：重复： 按照相同的步骤从新点继续搜索。

第 6 步：停止：当没有一个邻居更好或经过足够的尝试时。

本地搜索算法的类型

让我们看看几种类型的本地搜索算法：

1. 爬山搜索算法

爬山搜索算法是一种简单的局部搜索算法，它迭代地朝着更好的解决方案发展。它通常用于优化问题，其目标是找到由目标函数表示的景观的峰值。

过程：

开始：从初始解决方案开始。
评估：评估相邻解决方案。
移动：如果目标函数值改进了当前解，则转换为具有最高目标函数值的相邻函数值。
重复：继续此过程，直到不存在更好的相邻解决方案。

优点：

易于实施。
在小或平滑的搜索空间中效果很好。

缺点：

可能会陷入局部最优。
对搜索空间的探索有限。

import random


def f(x):
    return - (x - 3)**2 + 5


def hill_climb():
    current_x = random.uniform(0, 6)
    step_size = 0.1
    max_iterations = 100
    for i in range(max_iterations):
        neighbors = [current_x + step_size, current_x - step_size]
        neighbors = [x for x in neighbors if 0 <= x <= 6]
        neighbor_scores = [f(x) for x in neighbors]
        best_neighbor_idx = neighbor_scores.index(max(neighbor_scores))
        best_neighbor = neighbors[best_neighbor_idx]
        if f(best_neighbor) > f(current_x):
            current_x = best_neighbor
        else:
            break
    return current_x, f(current_x)


result_x, result_value = hill_climb()
print(f"Found maximum at x = {result_x:.2f}, value = {result_value:.2f}")

输出：在 x = 3.02 处找到最大值，值 = 5.00

2. 模拟退火

模拟退火的灵感来自冶金中的退火过程，其中材料被加热，然后逐渐冷却以去除缺陷。它允许偶尔移动到更差的解决方案以逃避局部最优值，并且这种移动的可能性会随着时间的推移而降低。

过程：

开始：从初始溶液和初始温度开始。
移动：以一定概率过渡到相邻的解决方案。
冷却计划：根据预定义的时间表逐渐降低温度。
概率函数：接受更差的解，其概率随着温度的降低而降低。

优点：

由于概率接受更差的解决方案，可以逃避局部最优。
灵活探索解决方案空间。

缺点：

需要仔细调整温度和冷却计划等参数。
由于重复评估，计算成本高昂。

import math
import random


def f(x):
    return - (x - 3)**2 + 5


def get_neighbor(x, step_size=0.1):
    return x + random.uniform(-step_size, step_size)


def simulated_annealing():
    current_x = random.uniform(0, 6)
    best_x = current_x
    best_eval = f(current_x)
    temp = 10
    max_iterations = 1000
    for i in range(max_iterations):
        t = temp / float(i + 1)
        candidate = get_neighbor(current_x)
        candidate = max(0, min(6, candidate))
        candidate_eval = f(candidate)
        if candidate_eval > best_eval or random.random() < math.exp((candidate_eval - best_eval) / t):
            current_x = candidate
            best_eval = candidate_eval
            best_x = current_x
    return best_x, f(best_x)


result_x, result_value = simulated_annealing()
print(f"Best found x = {result_x:.2f}, value = {result_value:.2f}")

输出：最佳发现 x = 3.02，值 = 5.00

3. 遗传算法

遗传算法（GA）的灵感来自自然选择和进化过程。他们使用一系列解决方案，并随着时间的推移使用选择、交叉和突变等遗传算子进化它们。

过程：

初始化：从随机解的总体开始。
评估：评估每个解决方案的适用性。
选择：根据他们的适应性选择最佳的繁殖解决方案。
交叉：组合成对的解决方案以产生新的后代。
突变：对后代进行随机更改以保持多样性。
替换：通过选择要保留的解决方案来形成新的种群。

优点：

可以探索广阔的解决方案空间，找到高质量的解决方案。
适用于搜索空间大的复杂问题。

缺点：

由于需要评估许多解决方案，计算成本很高。
需要调整各种参数，如种群规模和突变率。

import random


def f(x):
    return - (x - 3)**2 + 5


def genetic_algorithm():
    population = [random.uniform(0, 6) for _ in range(20)]
    max_generations = 50
    for _ in range(max_generations):
        scores = [f(x) for x in population]
        best = population[scores.index(max(scores))]
        new_population = [best]  # keep best
        while len(new_population) < len(population):
            parents = random.sample(population, 2)
            child = (parents[0] + parents[1]) / 2
            # mutation: small random step
            if random.random() < 0.3:
                child += random.uniform(-0.2, 0.2)
                child = max(0, min(6, child))
            new_population.append(child)
        population = new_population
    scores = [f(x) for x in population]
    best = population[scores.index(max(scores))]
    return best, f(best)


result_x, result_value = genetic_algorithm()
print(f"Best found x = {result_x:.2f}, value = {result_value:.2f}")

输出：最佳发现 x = 3.00，值 = 5.00

4. 禁忌搜索

通过使用称为禁忌列表的内存结构来增强本地搜索，以避免重新访问以前探索过的解决方案。这有助于防止循环回到局部最佳状态，并鼓励探索新区域。

过程：

开始：从初始解决方案开始并初始化禁忌列表。
移动：在考虑禁忌列表的同时过渡到相邻的解决方案。
更新：将当前解决方案添加到禁忌列表中，并可能删除较旧的条目。
愿望标准：允许导致更好解决方案的举动，即使它们在禁忌列表中。

优点：

减少陷入局部最优的机会。
有效探索大型和复杂的搜索空间。

缺点：

需要仔细管理禁忌清单和愿望标准。
计算复杂性可能很高。

import random


def f(x):
    return - (x - 3)**2 + 5


def tabu_search():
    current_x = random.uniform(0, 6)
    tabu_list = []
    tabu_size = 5
    step_size = 0.1
    max_iterations = 100
    best_x = current_x
    best_eval = f(current_x)
    for _ in range(max_iterations):
        neighbors = [current_x + step_size, current_x - step_size]
        neighbors = [x for x in neighbors if 0 <=
                     x <= 6 and x not in tabu_list]
        if not neighbors:
            break
        neighbor_scores = [f(x) for x in neighbors]
        best_neighbor_idx = neighbor_scores.index(max(neighbor_scores))
        best_neighbor = neighbors[best_neighbor_idx]
        if f(best_neighbor) > best_eval:
            best_x, best_eval = best_neighbor, f(best_neighbor)
        tabu_list.append(current_x)
        if len(tabu_list) > tabu_size:
            tabu_list.pop(0)
        current_x = best_neighbor
    return best_x, f(best_x)


result_x, result_value = tabu_search()
print(f"Best found x = {result_x:.2f}, value = {result_value:.2f}")

输出：最佳发现 x = 3.02，值 = 5.00

本地搜索算法的比较

特征/方面	爬山	模拟退火	遗传算法	禁忌搜索
灵感	爬山	冶金退火	自然选择和进化	基于内存的搜索
搜索空间	当地	广泛（具有受控随机性）	非常广泛（基于人群）	内存宽广
转向更糟糕的解决方案	不	是（概率）	是（通过突变/交叉）	罕见（有抽吸）
避免局部最佳	不	是的	是的	是的
内存使用情况	低	中等	高	中到高
需要调整参数	极小	高（温度、冷却）	高（人口、突变率）	中号（禁忌大小、规则）
速度	快	温和	较慢（种群进化）	温和
复杂性	简单	温和	高	温和
最佳用例	小/简单的问题	许多局部最优的问题	复杂的优化问题	骑自行车容易出现的问题