最优化之遗传算法：以迷宫寻路为例

想象我们正在运行一个程序，目标是找到从迷宫入口到出口的最短路径。

我们来按照遗传算法的计算流程，一步步地、系统地解释所有核心概念，并用“迷宫寻路”这个例子贯穿始终。

---

第0步：明确问题 (Problem Definition)

• 问题 (Problem)： 在给定的迷宫地图上，找到一条从起点到终点的最短且有效（不撞墙）的路径。
• 目标： 最小化路径长度（步数）。

---

第一步：初始化种群 (Initialization)

• 个体 (Individual)：
  • 定义： 遗传算法中代表一个潜在解决方案的基本单元。
  • 在迷宫中的体现： 一个个体就是一条具体的行走路径。它不是一个抽象概念，而是一个具体的、可执行的方案。
  • 比喻： 一个“探索者”或一个“寻路机器人”，它脑子里记着一套行走指令。
• 编码 (Encoding)：
  • 定义： 将“个体”（即路径）转换成计算机能够存储和操作的数据形式的过程。
  • 在迷宫中的体现： 我们选择基于动作的编码。
    • 定义动作：0=前进, 1=左转, 2=右转。
    • 一条路径（如：前进→右转→前进→前进→左转→前进）被编码为一个整数数组：[0, 2, 0, 0, 1, 0]。
  • 重要性： 编码是连接现实问题和算法计算的桥梁。算法操作的不是“路径图”，而是这些编码后的数组。
• 种群 (Population)：
  • 定义： 在算法开始时或每一代中，所有“个体”的集合。
  • 在迷宫中的体现： 我们随机生成100个不同的路径指令数组，例如：
    • 个体1: [1, 0, 2, 1, 0, 0]
    • 个体2: [0, 0, 0, 2, 2, 1]
    • …
    • 个体100: [2, 1, 0, 0, 0, 2]
  • 目的： 提供一个多样化的“解”的初始集合，避免一开始就陷入局部最优。

计算流程： 随机生成 N 个 个体 -> 每个个体进行 编码 -> 组成 初始种群

---

第二步：评估个体（计算适应度）(Evaluation / Fitness Calculation)

• 适应度 (Fitness)：
  • 定义： 衡量一个个体（即一个潜在解）优劣程度的数值。值越高，表示该解越“好”或越“适应”环境。
  • 在迷宫中的体现： 我们需要设计一个适应度函数 (Fitness Function)。
    • 函数逻辑：
      1. 解码： 读取个体的编码数组（如 [0, 2, 0, 0, 1, 0]）。
      2. 模拟行走： 从起点开始，按照数组指令一步步在迷宫地图上模拟行走。
      3. 计算得分：
         • 如果没有到达终点：适应度 = 一个很小的数（如 1），或基于离终点的直线距离给分。
         • 如果到达了终点：适应度 = 1 / (实际步数) 或 M - 实际步数（M是一个大数）。步数越少，适应度越高！
         • 惩罚： 如果行走过程中撞墙，可以额外扣分或直接判定无效。
    • 例子：
      • 个体A ([0,2,0,0,1,0])：走了50步到终点，适应度 = 1/50 = 0.02
      • 个体B ([0,0,0,0,0,0])：一直往前走，撞墙了，适应度 = 0.001
• “探索者”比喻： 让每个“探索者”都去试走一遍它记住的路线，然后根据它走得好不好（是否到终点、走了几步）给它打分。

计算流程： 对种群中每个 个体 -> 使用 适应度函数 计算其 适应度值 -> 得到每个个体的 适应度分数

---

第三步：选择“父母” (Selection)

• 选择 (Selection)：
  • 定义： 根据个体的适应度值，从当前种群中挑选出一部分个体作为“父母”，用于产生下一代。适应度越高，被选中的概率越大。
  • 原理： 模拟“优胜劣汰，适者生存”的自然法则。
  • 常用方法：
    • 轮盘赌选择 (Roulette Wheel Selection)： 想象一个大转盘，每个个体占的扇形面积与其适应度成正比。转盘转起来，指针停在哪块区域，就选中哪个个体。适应度高的个体“盘子”大，更容易被选中。
    • 锦标赛选择 (Tournament Selection)： 随机挑选几个个体（比如3个）进行“比赛”，适应度最高的那个获胜并被选中。重复此过程。
  • 在迷宫中的体现： 适应度为 0.02 的个体A被选中的机会远大于适应度为 0.001 的个体B。

计算流程： 根据 适应度分数 -> 使用 选择算法 -> 选出 M 对 “父母” 个体

---

第四步：“生宝宝”（交叉）(Crossover)

• 交叉 (Crossover) / 杂交 (Recombination)：
  • 定义： 将两个被选中的“父母”个体的部分编码进行交换，从而生成一个或多个新的“子代”个体。这是产生新解的主要方式。
  • 原理： 模拟生物的有性生殖，让优秀的“基因”（即路径中的好片段）有机会组合在一起。
  • 常用方法：
    • 单点交叉 (Single-Point Crossover)：
      1. 随机选择一个交叉点（例如，在长度为6的数组中选位置3）。
      2. 将两个父代的编码在该点“剪断”。
      3. 子代1 = 父代A的前半段 + 父代B的后半段
      4. 子代2 = 父代B的前半段 + 父代A的后半段
  • 在迷宫中的体现：
    • 父代A: [0, 2, 0 | 0, 1, 0] (适应度高，前半段可能很聪明)
    • 父代B: [1, 1, 1 | 2, 2, 2] (适应度高，后半段可能很高效)
    • 子代: [0, 2, 0 | 2, 2, 2] (可能结合了A的聪明开头和B的高效结尾！)
• 交叉概率 (Crossover Probability, Pc)： 不是每一对父母都会交叉。通常设置一个概率（如 Pc=0.8），表示父母配对后发生交叉的可能性。

计算流程： 对每对选中的 “父母” -> 以 概率 Pc 决定是否交叉 -> 如果交叉，随机选 交叉点 -> 执行 交叉操作 -> 生成 子代个体

---

第五步：引入“变异” (Mutation)

• 变异 (Mutation)：
  • 定义： 以很小的概率，随机改变一个子代个体编码中的某个（或某些）基因（即数组中的某个元素）。
  • 原理： 模拟生物的基因突变。它能增加种群的多样性，帮助算法跳出“局部最优解”（比如所有个体都卡在某个次优路径上），探索新的可能性。
  • 在迷宫中的体现：
    • 子代: [0, 2, 0, 2, 2, 2]
    • 变异：以很小的概率（如 Pm=0.01），随机选中第4个位置，将其从 2 (右转) 变为 1 (左转)。
    • 变异后: [0, 2, 0, 1, 2, 2]
    • 这个微小改变可能让“探索者”避开一个死胡同，发现一条新路！
• 变异概率 (Mutation Probability, Pm)： 非常小（通常0.1%到1%），避免破坏已经找到的好解。

计算流程： 对每个生成的 子代个体 -> 遍历其编码的每个位置 -> 以 概率 Pm 决定是否变异 -> 如果变异，随机改变该位置的值 -> 得到最终的 子代

---

第六步：生成新一代种群 (Replacement)

• 新种群 (New Population)：
  • 定义： 由上一步产生的所有“子代”个体组成的集合，它将完全取代或部分取代旧的种群，成为算法的下一代。
  • 在迷宫中的体现： 我们通过选择、交叉、变异，生成了100个新的子代个体（路径）。这100个新个体就构成了第2代种群。
  • 策略： 最常见的是“代际更新”，即完全用子代替换父代。有时会保留少数精英个体（适应度最高的几个）。

计算流程： 收集所有经过 变异 的 子代 -> 组成 新种群

---

第七步：循环与终止 (Iteration & Termination)

• 循环： 将新种群作为当前种群，回到第二步（评估适应度），开始新的一轮进化。
• 终止条件 (Termination Condition)： 什么时候停止？
  • 达到最大代数： 比如进化了1000代。
  • 找到满意解： 比如某个个体的适应度达到了预设的高分（找到了很短的路径）。
  • 适应度不再提升： 连续很多代，种群的最好适应度都没有明显改善（可能已经收敛）。
• 输出： 当满足终止条件时，算法停止。输出当前种群中适应度最高的个体，它就是我们找到的最优或近似最优的路径。

计算流程： 检查 终止条件 -> 如果不满足，回到 第二步 -> 如果满足，输出 最佳个体

---

总结：概念层级与流程图

概念	定义	在迷宫寻路中的具体体现
问题 (Problem)	需要解决的任务	找到迷宫的最短有效路径
解决方案 (Solution)	问题的最优或满意答案	一条从起点到终点的最短路径
个体 (Individual)	代表一个潜在解决方案的基本单元	一条具体的行走路径（如：前进→右转→前进…）
编码 (Encoding)	将“个体”转换为计算机可操作的数据形式	将路径转换为动作指令数组，如 [0, 2, 0, 0, 1, 0]
种群 (Population)	所有个体的集合	100个不同的路径指令数组组成的列表
适应度 (Fitness)	衡量个体优劣的数值	根据路径是否到终点、步数长短计算出的分数（步数越少，分数越高）
适应度函数 (Function)	计算适应度的具体规则	读取编码数组 -> 模拟行走 -> 计算得分（1/步数 或 M-步数）
选择 (Selection)	根据适应度挑选“父母”	用轮盘赌或锦标赛法，让高分路径有更大机会被选中
交叉 (Crossover)	交换父母部分编码，生成子代	父代A [0,2,0|0,1,0] + 父代B [1,1,1|2,2,2] -> 子代 [0,2,0|2,2,2]
变异 (Mutation)	以小概率随机改变子代编码中的某个值	[0,2,0,2,2,2] -> (变异第4位) -> [0,2,0,1,2,2]
新种群 (New Pop.)	由子代组成的下一代种群	100个新生成的路径数组
终止条件	算法停止的依据	达到1000代，或找到适应度>0.05的路径，或连续50代无提升

计算流程：
初始化种群 → 评估适应度 → 选择 → 交叉 → 变异 → 生成新种群 → 检查终止？ → (否)→ 回到“评估适应度” / (是)→ 输出最佳个体