基于Python与遗传算法的迷宫求解实战指南

实现目标与环境准备

本文旨在通过Python脚本演示如何利用遗传算法自动推导并输出迷宫的最优通行路线。相比传统递归回溯，遗传算法擅长处理大规模离散搜索空间，能够通过模拟生物进化机制逐步逼近全局最优解。

环境仅需标准Python 3运行库及可视化组件。执行 pip install matplotlib 安装绘图依赖后即可直接运行以下示例。

构建迷宫矩阵与路径编码机制

寻路的第一步是将物理结构数字化。采用二维列表表示地图区域是主流做法：

• 0：代表可通行的安全路径
• 1：代表不可逾越的障碍墙壁
• S / E：分别标记起始位置与目标出口

# 迷宫网格定义
# 0=路径, 1=墙壁, S=起点, E=终点
maze = [
    [1, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 0, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 1],
    [1, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 0, 1],
    [1, 'S', 0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1, 1, 1]
]

# 明确记录起止点索引，便于后续计算
start_pos = (5, 1)
end_pos = (2, 5)

在遗传算法中，每条候选路线被编码为移动方向指令序列。约定字符映射规则如下：

D向下 | U向上 | L向左 | R向右

例如 "DDRRUULDL" 即代表一条包含九个位移指令的完整路径染色体。种群将由大量此类随机生成的字符串组成。

编写适应度函数与遗传进化操作

算法需要一套评分标准来判断哪条路线更有价值。适应度函数的核心在于模拟个体移动轨迹，实时校验越界、撞墙状态，并奖励接近终点的行为。

第1步：路径扫描与得分计算

入口为方向序列与当前网格地图。遍历指令修正坐标，若触碰墙壁或越界则立即终止并返回零分；若抵达终点返回高分；若未到达则按曼哈顿距离赋予阶梯分数，引导种群向出口聚集。

def evaluate_fitness(path, grid, start, end):
    x, y = start
    max_steps = len(path)
    
    # 执行全部指令
    for move in path:
        dx, dy = {'D':(1,0), 'U':(-1,0), 'R':(0,1), 'L':(0,-1)}.get(move, (0,0))
        x, y = x + dx, y + dy
        
        # 越界检查
        if not (0 <= x < len(grid) and 0 <= y < len(grid[0])):
            return 0
            
        tile = grid[x][y]
        
        # 撞墙检查
        if isinstance(tile, int) and tile == 1:
            return 0
            
        # 成功抵达终点
        if tile == 'E':
            return max_steps * 10 + 100
            
    # 未到达终点：根据距离计算鼓励分数
    distance = abs(x - end[0]) + abs(y - end[1])
    return max_steps - distance

第2步：精英筛选与基因重组

选择采用锦标赛法，从种群中随机抽取若干个体对比得分，优胜者进入交配池。

交叉采用单点交换：截取父代A的前半段与父代B的后半段拼接，生成具备双亲特征的新染色体。

import random

def evolve_selection(pool):
    # 锦标赛选择示例
    cand1, cand2 = random.sample(pool, 2)
    return cand1 if evaluate_fitness(cand1, maze, start_pos, end_pos) > evaluate_fitness(cand2, maze, start_pos, end_pos) else cand2

def crossover(gene_a, gene_b):
    # 单点交叉
    split = random.randint(1, len(gene_a)-1)
    child = gene_a[:split] + gene_b[split:]
    return child

第3步：引入随机扰动维持多样性

变异防止算法陷入局部最优。设定较低概率，以等概率将某个位置的指令替换为其他三个方向之一。

def mutate_gene(individual):
    moves = ['D', 'U', 'L', 'R']
    mutated = list(individual)
    for i in range(len(mutated)):
        if random.random() < 0.02:  # 2% 变异率
            mutated[i] = random.choice(moves)
    return "".join(mutated)

执行多代迭代与成功判定标准

将上述组件串联为主循环。系统会不断刷新种群，并监控当代最高分个体。当得分突破阈值（通常>100）或达到最大代数上限时触发结束。

def run_genetic_solver(pop_size=100, max_gen=200):
    # 1. 初始化：随机生成方向序列
    genes = [''.join(random.choices(['D','U','L','R'], k=70)) 
             for _ in range(pop_size)]
    
    best_gene = ""
    best_score = -1
    
    # 2. 迭代进化
    for gen in range(max_gen):
        scores = [evaluate_fitness(g, maze, start_pos, end_pos) for g in genes]
        current_best_idx = scores.index(max(scores))
        
        if scores[current_best_idx] > best_score:
            best_score = scores[current_best_idx]
            best_gene = genes[current_best_idx]
            
        # 达标提前退出
        if best_score >= 200:
            print(f"[{gen+1}代] 找到通路！最终得分: {best_score}")
            break
            
        # 重组新种群
        mating_pool = sorted(zip(scores, genes), reverse=True)
        new_genes = []
        for _ in range(pop_size):
            p1 = evolve_selection([g for _, g in mating_pool[:10]])
            p2 = evolve_selection([g for _, g in mating_pool[:10]])
            child = crossover(p1, p2)
            child = mutate_gene(child)
            new_genes.append(child)
        genes = new_genes
        
    return best_gene

可视化展示与常见排错建议

获得最优路径后，可通过图形界面确认走向是否符合预期。调用matplotlib绘制背景栅格并用色块覆盖有效坐标即可。

import matplotlib.pyplot as plt

def render_path(grid, optimal_route, start):
    fig, ax = plt.subplots()
    ax.set_xlim(0, len(grid[0])); ax.set_ylim(0, len(grid))
    ax.invert_yaxis()  # 适配矩阵坐标系
    
    # 渲染墙壁
    for r, row in enumerate(grid):
        for c, val in enumerate(row):
            if val == 1:
                ax.add_patch(plt.Rectangle((c, r), 1, 1, facecolor='black'))
                
    # 渲染追踪轨迹
    cx, cy = start
    ax.plot([cy], [cx], 'o', color='blue')
    for m in optimal_route:
        dx, dy = {'D':(1,0), 'U':(-1,0), 'R':(0,1), 'L':(0,-1)}.get(m, (0,0))
        nx, ny = cx+dx, cy+dy
        ax.plot([cy, ny], [cx, nx], linewidth=3, color='green')
        cx, cy = nx, ny
        
    plt.show()

在实际跑通脚本时，若发现曲线始终无法收敛：
① 检查网格尺寸与genes初始化长度是否匹配，指令数量不足会导致无法跨越长距离；
② 适当提高max_gen上限至500以上，复杂地形需要更多迭代次数释放算力；
③ 调整变异率在0.03~0.1之间浮动，过低易早熟，过高则退化为纯随机游走。

总结

遗传算法通过将抽象的方向指令转化为可进化的基因片段，结合精准的坐标校验与距离导向评分，能够高效挖掘迷宫中的隐藏通道。该架构不仅适用于方格寻路，其底层的选择与重组思想同样广泛应用于物流调度、路由配置等工程领域。以上就是Python利用遗传算法探索迷宫出路实例深究的详细内容，更多关于Python启发式搜索与路径优化的资料请关注本站其它相关文章！