遗传算法求解迷宫
遗传算法（Genetic Algorithm，GA）是模仿自然选择与遗传机制的一种搜索启发式算法。下面用它来解一个随机迷宫：种群里的每个个体是一串移动指令（上/下/左/右），适应度是个体在迷宫中"走到底"后离终点的距离——离得越近，越有资格繁衍后代，经过一代代的选择、交叉与变异，种群逐渐学会穿越迷宫。
算法细节
由 DeepSeek-V4-Flash 实现。
编码：移动序列
每个个体是一条固定长度的指令串，指令为四个方向之一：
指令集 0=上 1=下 2=左 3=右
个体 3 3 0 2 3 1 0 0 1 2 ... （长度 ~8×迷宫边长）把个体放进迷宫执行：从起点出发按指令依次移动，撞墙或越界的指令被忽略、原地不动。这样基因里"多余的"指令不会破坏路径，只会暂时浪费一格，算法可以容忍冗余基因的存在。
适应度
到达终点 ? 1e6 - 已走步数 // 巨大加成，且偏好更短路径
: 已走步数 * 0.1 + 1000 * (1 - 距终点曼哈顿距离 / 最大距离)- 没到达前，离终点的距离主导适应度，推动路径朝终点延伸；
- 已走的步数作次要奖励，让能走得更远的个体在"同距离"下胜出；
- 一旦到达终点，适应度跃升到
量级，之后选择压力转为 路径更短更好——所以你会在求解后看到路径还在一点点缩短。
选择、交叉与变异
| 算子 | 做法 |
|---|---|
| 选择 | 锦标赛选择（tournament）：随机抽 3 个个体，取适应度最高者作为父本，重复两次得到父母 |
| 交叉 | 单点交叉：随机选一个切点，把父亲切点后的指令段与母亲的后半段拼接，得到"父前半 + 母后半"的子代 |
| 变异 | 逐基因变异：每个方向指令以变异率（默认 6%）随机改成一个新方向 |
| 精英保留 | 当前最优个体原封不动进入下一代，保证适应度不倒退 |
| 多样性 | 每代有 2% 概率注入一个全新随机个体，防止过早收敛 |
evolve()：一代是如何产生的
evolve 是算法的核心，接收上一代（pop）、上一代每个个体的适应度（fits）与配置，产出一模一样大小的下一代：
export function evolve(pop, fits, cfg, rand = Math.random): number[][] {
const next: number[][] = []
const { chromLen: L, crossoverRate: pc, mutationRate: pm } = cfg
// 1. 精英保留：当前最优个体原封不动进入下一代
let bi = 0
for (let i = 0; i < fits.length; i++) if (fits[i] > fits[bi]) bi = i
next.push([...pop[bi]])
// 2. 循环补满下一代
while (next.length < pop.length) {
// 3. 随机注入新个体，防止过早收敛
if (rand() < 0.02) { next.push(randomChromosome(L, rand)); continue }
// 4. 选亲本：两次锦标赛各抽 3 个候选，取其中适应度最高者
const child = [...pop[tournament(fits, 3, rand)]] // 父本（复制）
const mate = pop[tournament(fits, 3, rand)] // 母本（只读）
// 5. 单点交叉：按概率 0.7，把父本切点后的段换成母本的
if (rand() < pc) {
const pt = (rand() * L) | 0
for (let i = pt; i < L; i++) child[i] = mate[i]
}
// 6. 逐基因变异：每位指令以概率 pm 随机改成新方向
for (let i = 0; i < L; i++) {
if (rand() < pm) child[i] = (rand() * 4) | 0
}
next.push(child)
}
return next
}逐步解读：
① 精英保留 —— 找到适应度最高的个体，直接复制一份放进下一代。三点值得注意：
- 它保证"迄今为止最好的路径"不会被交叉/变异破坏，代际最优适应度单调不减；
- 若没有它，好不容易进化出来的好个体可能刚出现就被下一代弄丢了，前功尽弃；
② 循环条件 —— while (next.length < pop.length) 保证下一代与上一代人口数完全一致；
③ 随机注入 —— 2% 概率塞入一个全新的随机染色体并跳过交叉/变异。这是对抗早熟收敛的保险：当种群被交叉压到大家几乎一样时，近亲杂交产不出新花样，只能靠外来基因打破僵局。
④ 选亲本（锦标赛选择） —— tournament 随机抽 3 个候选、返回其中适应度最高者的下标：
function tournament(fits, k, rand) {
let best = 0, bestFit = -Infinity
for (let i = 0; i < k; i++) {
const j = (rand() * fits.length) | 0
if (fits[j] > bestFit) { bestFit = fits[j]; best = j }
}
return best
}它让强个体有很高的概率成为父母、弱个体偶尔也能胜出——k 就是取舍的旋钮：k=1 等于随机抽（无选择压力），k 越大越"择优"。这里 k=3 兼顾利用与探索。父本用 [...] 复制（因为之后要改），母本只读不复制。
⑤ 单点交叉 —— 按概率 0.7（crossoverRate），随机选一个切点 pt，把父本的后半段用母本的同位段覆盖，得到"父前半 + 母后半"的子代。交叉是 GA 的组合引擎：两条路径里各自的好片段（比如一段漂亮的转向序列）可能被拼接成更完整的走廊。剩下 30% 的概率跳过交叉，子代直接是父本的克隆，交给变异去扰动。
⑥ 逐基因变异 —— 对 L 位指令逐位以概率 mutationRate（默认 6%）随机改成 0~3 之一。变异是探索的头号来源：哪怕父母都没试过的某个拐弯，子代也能靠它撞出来；同时大多数子代只是父母路径的轻微扰动——探索发生在已知好解的邻近区域。
关键细节
- 迷宫保证可解：随机抛墙后用 BFS 校验起点到终点是否连通，不连通就重新生成。
- 撞墙即忽略 是这类"指令串"编码的经典处理：它把可行解空间变得非常宽容，配合同距离下按步数排序，种群很容易从"只顾往前冲"演化出"会拐弯"的路径。
- 适应度曲线用对数纵轴绘制，因为到达终点后适应度从千级跳到百万级，线性坐标会压得前面看不出变化。
一个有趣的观察：把变异率拉到 20% 并缩小种群，你会看到种群像一群"醉酒的人"在迷宫里乱撞，难以收敛；而变异率过低时，种群又容易在某个局部路径上固化，找不到更近的捷径。平衡探索与利用，正是遗传算法的核心课题。