加菲猫欢乐跑
65.99M · 2026-03-26
我曾经使用遗传算法常用于解决旅行商问题，认为遗传算法解决问题的关键是对问题编码。看到了一篇有趣的技术博文【1】，介绍使用遗传算法（Genetic Algorithm, GA） 训练小车在模拟环境中实现自动泊车。尽管文章中对泊车问题编码的思路非常精彩，但是使用 Three.js 进行算法实现和可视化的，对后端选手不太友好。在复现的过程中，参考了博文【1】的算法思路，为了避免碰撞，优化了损失函数。本文使用python实现算法，并使用pygame库进行可视化，源码上传了git仓库（github.com/lcmchn/self…）。
首先要理解本算法设计的核心思想：
自动泊车的本质是 “小车根据环境（障碍物）调整动作（行驶、转向），最终精准停靠目标车位”。本文用进化（遗传算法）的方式“训练”小车学会这一过程，而不是手动编写规则。
然后大家在阅读本文前思考几个问题，这是本文解决泊车任务的关键：
感知（看）：小车如何获取周围环境信息？ 决策（想）：如何根据环境信息生成动作指令？ 优化（学）：如何让小车通过迭代 “学会” 最优决策逻辑？
为了解决上面三个问题，本文先对小车建模，然后利用遗传算法进化小车的“大脑”。下面分别介绍。
为了简化模型，小车的动作被抽象为两个独立维度的信号，每个信号仅 3 种状态。小车每隔一定步长（本文为100ms）接收一次动作信号，然后执行。
| -1 | 0 | +1 |
|---|---|---|
| 倒车 | 静止 | 前进 |
| -1 | 0 | +1 |
|---|---|---|
| 左转 | 直行 | 右转 |
每辆小车拥有8个距离传感器，检测与障碍物的距离，使小车拥有感知周围环境的能力。每隔一定步长（本文为100ms）传感器输出 8 个浮点数（对应 8 个传感器的距离值），作为大脑决策系统的输入。当监测范围内（4m）无障碍物，传感器数值为0；当传感器数值很小但不为0，表示障碍物就在附近。
小车的大脑决策系统实现了由“感知”到“动作”的转换：距离传感器输入， 动作信号输出。本文算法通过一个简单的线性函数+信号转换建模：
-->发动机信号
engineSignal = brainToMuscleSignal(
(e0 * sensor0) + (e1 * sensor1) + ... + (e7 * sensor7) + ebias // <- brainFunction
)
-->方向盘信号
wheelSignal = brainToMuscleSignal(
(w0 * sensor0) + (w1 * sensor1) + ... + (w7 * sensor7) + wbias // <- brainFunction
)
sensor[i]：小车周围8方位距离传感器，返回到障碍物的距离。
e[i]、ebias、w[i]、wbias：可学习的权重参数（即“基因”）。
-->sigmoid函数
将多项式输出的任意浮点数压缩到 (0,1) 区间（归一化）
-->阈值划分
(0, 0.1)→-1，(0.1, 0.9)→0，(0.9,1)→+1（通过 margin 参数控制阈值范围,-10+1就是需要的动作信号！！）
每个个体（一辆小车）的“基因”就是其线性控制函数的所有权重和偏置（e0-e7、ebias、w0-w7、wbias 共 18 个系数）：
为了得到优秀的基因（180位0/1 序列），解决自动泊车问题。本算法使用遗传算，模拟自然选择，迭代产生更优个体。下图为算法的关键步骤和流程。
| 遗传算法概念 | 泊车任务实现 |
|---|---|
| 个体（Individual） | 一个小车基因组（180位0/1 序列） |
| 种群（Population） | 一代小车的集合（默认 1000 个个体） |
| 适应度函数（Fitness Function） | 基于 “车轮到车位角的平均距离” 计算：fitness = 1 / (loss + 1)，其中 loss 是 4 个车轮到车位 4 个角的平均距离（距离越近，fitness 越高） 加入碰撞惩罚项：发生碰撞直接将适应度降至1% |
| 选择（Selection） | 加权随机选择：适应度越高的个体，被选中作为父母的概率越大；同时保留 10%“最优个体” 直接进入下一代（避免优质基因丢失） |
| 交叉（Crossover） | 均匀交叉：父母基因组的每一位以 50% 概率遗传给子女（模拟基因重组） |
| 变异（Mutation） | 随机变异：每个基因位以 4% 概率翻转（0→1 或 1→0，引入新基因多样性） |
def car_fitness_from_loss(loss: float, has_collision: bool = False, is_loop: bool = False,
is_timeout: bool = False) -> float:
"""
增强版适应度函数：
- loss越小（离车位越近），适应度越高
- 碰撞大幅惩罚适应度
"""
base_fitness = 1.0 / (loss + 1e-6)
# 惩罚项：碰撞/循环/超时直接将适应度降至1%
if has_collision:
base_fitness *= 0.01
# 额外奖励：离车位足够近（<50像素）时翻倍奖励
if loss < 50:
print()
base_fitness *= 2.0
return
初始化种群（N 辆随机小车）。
对每辆车：
根据适应度选择、交叉、变异，生成新一代种群。
重复步骤 2–3，直到某代出现能成功泊车的小车，或达到最大代数。
初始代的小车的”基因“是随机的，完全没有自动泊车的能力：
遗传算法训练50代后，小车掌握了自动泊车的能力，基本能停靠在目标车位附近：
平均适应度随着迭代呈上升趋势，说明算法正在有效筛选优质基因，种群整体的泊车能力在持续提升。
虽然本文的算法不适合直接用于真实自动驾驶（训练的小车一路上有时会撞到别的车，而且停车位也停得不准确），但为理解机器学习、优化算法和机器人控制提供了起点。下面是针对本文算法的几点反思：
dev.to/trekhleb/se…
