引言
小行星（Asteroids）是经典的街机游戏，玩家控制一艘飞船在太空中飞行，需要躲避并击碎不断飘来的陨石。要在这一环境中训练出智能的AI玩家，传统的手写规则或固定结构的神经网络往往难以适应复杂多变的局面。神经进化（Neuroevolution）是一类通过进化算法优化神经网络结构及权重的技术，其中NEAT（NeuroEvolution of Augmenting Topologies）算法尤为出色，它能够同时进化网络的拓扑结构和连接权重。
本文将用Java实现简化版小行星游戏，并基于NEAT算法训练能够自主游玩的AI飞船。
NEAT算法核心原理
三大核心机制
- 历史标记（Historical Markings）：每个基因连接都有唯一的创新编号（innovation number），用于跨个体对齐基因进行交叉。
- 物种形成（Speciation）：根据拓扑相似度将种群划分为多个物种，保护结构创新不被过早淘汰。
- 渐进式复杂化（Incremental Growth）：从最小结构开始，通过突变逐步增加网络复杂度，避免搜索高维空间。
兼容性距离
两个个体间的兼容性距离用于判断是否属于同一物种：
$$\delta = \frac{c_1 E}{N} + \frac{c_2 D}{N} + c_3 \cdot \overline{W}$$
其中E为不重叠连接数，D为不重叠节点数，$\overline{W}$为权重差异均值，N为较大基因组的长度，$c_1, c_2, c_3$为系数。
Java实现
import java.util.*;
/**
* 基因连接：表示神经网络中的一个连接
*/
class ConnectionGene {
int inNode; // 输入节点ID
int outNode; // 输出节点ID
double weight; // 连接权重
boolean enabled; // 是否启用
int innovation; // 创新编号
public ConnectionGene(int inNode, int outNode, double weight, boolean enabled, int innovation) {
this.inNode = inNode;
this.outNode = outNode;
this.weight = weight;
this.enabled = enabled;
this.innovation = innovation;
}
public ConnectionGene copy() {
return new ConnectionGene(inNode, outNode, weight, enabled, innovation);
}
}
/**
* 基因节点：表示神经网络中的一个节点
*/
class NodeGene {
int id;
NodeType type;
enum NodeType { INPUT, HIDDEN, OUTPUT, BIAS }
public NodeGene(int id, NodeType type) {
this.id = id;
this.type = type;
}
}
/**
* 基因组：编码一个完整的神经网络
*/
class Genome {
List<NodeGene> nodes;
List<ConnectionGene> connections;
int maxNodeId;
double fitness;
int speciesId;
public Genome() {
this.nodes = new ArrayList<>();
this.connections = new ArrayList<>();
this.maxNodeId = 0;
this.fitness = 0;
this.speciesId = -1;
}
/**
* 创建最小网络（输入直接连接输出）
*/
public static Genome createMinimal(int numInputs, int numOutputs, Random random, InnovationTracker tracker) {
Genome g = new Genome();
// 添加输入节点
for (int i = 0; i < numInputs; i++) {
g.nodes.add(new NodeGene(i, NodeGene.NodeType.INPUT));
}
// 添加偏置节点
g.nodes.add(new NodeGene(numInputs, NodeGene.NodeType.BIAS));
// 添加输出节点
for (int i = 0; i < numOutputs; i++) {
g.nodes.add(new NodeGene(numInputs + 1 + i, NodeGene.NodeType.OUTPUT));
}
g.maxNodeId = numInputs + numOutputs;
// 全连接
for (int i = 0; i <= numInputs; i++) {
for (int j = 0; j < numOutputs; j++) {
int outId = numInputs + 1 + j;
int innov = tracker.getInnovation(i, outId);
g.connections.add(new ConnectionGene(i, outId, random.nextGaussian() * 0.5, true, innov));
}
}
return g;
}
public Genome copy() {
Genome g = new Genome();
g.maxNodeId = maxNodeId;
g.fitness = fitness;
for (NodeGene n : nodes) g.nodes.add(new NodeGene(n.id, n.type));
for (ConnectionGene c : connections) g.connections.add(c.copy());
return g;
}
}
/**
* 创新编号追踪器：确保相同突变获得相同创新编号
*/
class InnovationTracker {
private final Map<String, Integer> innovationMap = new HashMap<>();
private int nextInnovation = 0;
public synchronized int getInnovation(int inNode, int outNode) {
String key = inNode + "->" + outNode;
return innovationMap.computeIfAbsent(key, k -> nextInnovation++);
}
}
/**
* 神经网络前馈计算器
*/
class NeuralNetwork {
private final Map<Integer, List<ConnectionGene>> nodeInputs = new HashMap<>();
private final Map<Integer, Double> nodeValues = new HashMap<>();
private final List<Integer> evalOrder = new ArrayList<>();
private final Set<Integer> inputNodes = new HashSet<>();
private final Set<Integer> outputNodes = new HashSet<>();
public NeuralNetwork(Genome genome) {
// 构建邻接表
for (ConnectionGene c : genome.connections) {
if (!c.enabled) continue;
nodeInputs.computeIfAbsent(c.outNode, k -> new ArrayList<>()).add(c);
}
for (NodeGene n : genome.nodes) {
if (n.type == NodeGene.NodeType.INPUT || n.type == NodeGene.NodeType.BIAS) {
inputNodes.add(n.id);
} else if (n.type == NodeGene.NodeType.OUTPUT) {
outputNodes.add(n.id);
}
}
// 拓扑排序
buildEvalOrder(genome);
}
private void buildEvalOrder(Genome genome) {
Map<Integer, Set<Integer>> dependencies = new HashMap<>();
for (NodeGene n : genome.nodes) {
dependencies.put(n.id, new HashSet<>());
}
for (ConnectionGene c : genome.connections) {
if (c.enabled) {
dependencies.get(c.outNode).add(c.inNode);
}
}
Set<Integer> ready = new HashSet<>(inputNodes);
Set<Integer> remaining = new HashSet<>();
for (NodeGene n : genome.nodes) {
if (!inputNodes.contains(n.id)) remaining.add(n.id);
}
while (!remaining.isEmpty()) {
boolean progress = false;
for (int node : new ArrayList<>(remaining)) {
if (ready.containsAll(dependencies.get(node))) {
evalOrder.add(node);
ready.add(node);
remaining.remove(node);
progress = true;
}
}
if (!progress) break; // 存在环，NEAT通常避免此情况
}
}
public double[] activate(double[] inputs) {
nodeValues.clear();
// 设置输入值
int inputIdx = 0;
for (int nodeId : inputNodes) {
if (inputIdx < inputs.length) {
nodeValues.put(nodeId, inputs[inputIdx++]);
}
}
// 按拓扑顺序计算节点值
for (int nodeId : evalOrder) {
double sum = 0;
List<ConnectionGene> conns = nodeInputs.get(nodeId);
if (conns != null) {
for (ConnectionGene c : conns) {
sum += nodeValues.getOrDefault(c.inNode, 0.0) * c.weight;
}
}
// Sigmoid激活
nodeValues.put(nodeId, 1.0 / (1.0 + Math.exp(-sum)));
}
// 收集输出
double[] outputs = new double[outputNodes.size()];
int i = 0;
for (int nodeId : outputNodes) {
outputs[i++] = nodeValues.getOrDefault(nodeId, 0.0);
}
return outputs;
}
}
/**
* 简化版小行星游戏环境
*/
class AsteroidsGame {
static final double WIDTH = 800, HEIGHT = 600;
double shipX, shipY, shipAngle, shipSpeed;
boolean alive;
int score;
int ticks;
static final int MAX_TICKS = 3000;
// 陨石状态 [x, y, vx, vy, size]
List<double[]> asteroids = new ArrayList<>();
Random random;
public AsteroidsGame(Random random) {
this.random = random;
reset();
}
public void reset() {
shipX = WIDTH / 2;
shipY = HEIGHT / 2;
shipAngle = 0;
shipSpeed = 0;
alive = true;
score = 0;
ticks = 0;
asteroids.clear();
for (int i = 0; i < 5; i++) {
spawnAsteroid();
}
}
private void spawnAsteroid() {
double x = random.nextDouble() * WIDTH;
double y = random.nextDouble() * HEIGHT;
double angle = random.nextDouble() * 2 * Math.PI;
double speed = 1 + random.nextDouble() * 2;
double size = 20 + random.nextDouble() * 30;
asteroids.add(new double[]{x, y, Math.cos(angle) * speed, Math.sin(angle) * speed, size});
}
/**
* 执行一步游戏逻辑
* @param turn 转向（-1左, 0直, 1右）
* @param thrust 是否推进
*/
public void step(int turn, boolean thrust) {
if (!alive) return;
ticks++;
// 更新飞船
shipAngle += turn * 0.1;
if (thrust) {
shipSpeed = Math.min(shipSpeed + 0.2, 5);
} else {
shipSpeed *= 0.98; // 摩擦
}
shipX += Math.cos(shipAngle) * shipSpeed;
shipY += Math.sin(shipAngle) * shipSpeed;
// 边界环绕
if (shipX < 0) shipX += WIDTH;
if (shipX > WIDTH) shipX -= WIDTH;
if (shipY < 0) shipY += HEIGHT;
if (shipY > HEIGHT) shipY -= HEIGHT;
// 更新陨石
for (double[] a : asteroids) {
a[0] += a[2];
a[1] += a[3];
if (a[0] < 0) a[0] += WIDTH;
if (a[0] > WIDTH) a[0] -= WIDTH;
if (a[1] < 0) a[1] += HEIGHT;
if (a[1] > HEIGHT) a[1] -= HEIGHT;
}
// 碰撞检测
for (double[] a : asteroids) {
double dx = shipX - a[0];
double dy = shipY - a[1];
double dist = Math.sqrt(dx * dx + dy * dy);
if (dist < a[4] + 10) {
alive = false;
return;
}
}
score += 1; // 存活奖励
// 随机生成新陨石
if (random.nextDouble() < 0.01) {
spawnAsteroid();
}
}
/**
* 获取神经网络输入（8维传感器：8个方向到最近陨石的距离）
*/
public double[] getInputs() {
double[] inputs = new double[8];
for (int i = 0; i < 8; i++) {
double sensorAngle = shipAngle + i * Math.PI / 4;
double minDist = 1000;
for (double[] a : asteroids) {
double dx = a[0] - shipX;
double dy = a[1] - shipY;
double angleToAsteroid = Math.atan2(dy, dx);
double angleDiff = Math.abs(normalizeAngle(angleToAsteroid - sensorAngle));
if (angleDiff < Math.PI / 8) {
double dist = Math.sqrt(dx * dx + dy * dy);
minDist = Math.min(minDist, dist);
}
}
inputs[i] = Math.min(minDist / 400.0, 1.0); // 归一化
}
return inputs;
}
private double normalizeAngle(double angle) {
while (angle > Math.PI) angle -= 2 * Math.PI;
while (angle < -Math.PI) angle += 2 * Math.PI;
return angle;
}
}
/**
* NEAT进化引擎
*/
class NEATEngine {
static final int POPULATION_SIZE = 100;
static final double COMPATIBILITY_THRESHOLD = 3.0;
static final double WEIGHT_MUTATION_RATE = 0.8;
static final double ADD_NODE_RATE = 0.03;
static final double ADD_CONNECTION_RATE = 0.05;
static final double CROSSOVER_RATE = 0.75;
List<Genome> population;
InnovationTracker tracker;
Random random;
int generation;
public NEATEngine(Random random) {
this.random = random;
this.tracker = new InnovationTracker();
this.population = new ArrayList<>();
this.generation = 0;
}
public void initialize() {
for (int i = 0; i < POPULATION_SIZE; i++) {
Genome g = Genome.createMinimal(8, 2, random, tracker);
population.add(g);
}
}
/**
* 评估种群适应度
*/
public void evaluate() {
for (Genome g : population) {
g.fitness = evaluateGenome(g);
}
}
private double evaluateGenome(Genome genome) {
NeuralNetwork nn = new NeuralNetwork(genome);
double totalScore = 0;
// 评估5个随机场景取平均
for (int trial = 0; trial < 5; trial++) {
AsteroidsGame game = new AsteroidsGame(new Random(random.nextInt()));
while (game.alive && game.ticks < AsteroidsGame.MAX_TICKS) {
double[] inputs = game.getInputs();
double[] outputs = nn.activate(inputs);
int turn = outputs[0] > 0.6 ? 1 : (outputs[0] < 0.4 ? -1 : 0);
boolean thrust = outputs[1] > 0.5;
game.step(turn, thrust);
}
totalScore += game.score;
}
return totalScore / 5.0;
}
/**
* 物种形成
*/
public Map<Integer, List<Genome>> speciate() {
Map<Integer, List<Genome>> species = new HashMap<>();
int nextSpeciesId = 0;
for (Genome g : population) {
boolean assigned = false;
for (Map.Entry<Integer, List<Genome>> entry : species.entrySet()) {
Genome representative = entry.getValue().get(0);
if (compatibilityDistance(g, representative) < COMPATIBILITY_THRESHOLD) {
entry.getValue().add(g);
g.speciesId = entry.getKey();
assigned = true;
break;
}
}
if (!assigned) {
List<Genome> newSpecies = new ArrayList<>();
newSpecies.add(g);
species.put(nextSpeciesId, newSpecies);
g.speciesId = nextSpeciesId;
nextSpeciesId++;
}
}
return species;
}
private double compatibilityDistance(Genome a, Genome b) {
Set<Integer> innovA = new HashSet<>();
Set<Integer> innovB = new HashSet<>();
Map<Integer, Double> weightA = new HashMap<>();
Map<Integer, Double> weightB = new HashMap<>();
for (ConnectionGene c : a.connections) {
innovA.add(c.innovation);
weightA.put(c.innovation, c.weight);
}
for (ConnectionGene c : b.connections) {
innovB.add(c.innovation);
weightB.put(c.innovation, c.weight);
}
Set<Integer> disjoint = new HashSet<>(innovA);
disjoint.addAll(innovB);
Set<Integer> common = new HashSet<>(innovA);
common.retainAll(innovB);
int excess = disjoint.size() - common.size();
int n = Math.max(a.connections.size(), b.connections.size());
if (n < 20) n = 1;
double weightDiff = 0;
for (int innov : common) {
weightDiff += Math.abs(weightA.get(innov) - weightB.get(innov));
}
double avgWeightDiff = common.isEmpty() ? 0 : weightDiff / common.size();
return 1.0 * excess / n + 0.4 * avgWeightDiff;
}
/**
* 产生下一代
*/
public void reproduce() {
Map<Integer, List<Genome>> species = speciate();
List<Genome> newPopulation = new ArrayList<>();
double totalAdjustedFitness = 0;
Map<Integer, Double> speciesFitness = new HashMap<>();
for (Map.Entry<Integer, List<Genome>> entry : species.entrySet()) {
double sf = 0;
for (Genome g : entry.getValue()) {
sf += g.fitness / entry.getValue().size(); // 共享适应度
}
speciesFitness.put(entry.getKey(), sf);
totalAdjustedFitness += sf;
}
// 精英保留
Genome best = population.stream().max(Comparator.comparingDouble(g -> g.fitness)).orElse(null);
if (best != null) newPopulation.add(best.copy());
while (newPopulation.size() < POPULATION_SIZE) {
// 选择物种
double r = random.nextDouble() * totalAdjustedFitness;
double cumsum = 0;
int selectedSpecies = -1;
for (Map.Entry<Integer, Double> entry : speciesFitness.entrySet()) {
cumsum += entry.getValue();
if (cumsum >= r) {
selectedSpecies = entry.getKey();
break;
}
}
if (selectedSpecies == -1) selectedSpecies = 0;
List<Genome> sp = species.get(selectedSpecies);
if (sp == null || sp.isEmpty()) continue;
Genome parent1 = tournamentSelect(sp, 3);
if (random.nextDouble() < CROSSOVER_RATE && sp.size() > 1) {
Genome parent2 = tournamentSelect(sp, 3);
Genome child = crossover(parent1, parent2);
mutate(child);
newPopulation.add(child);
} else {
Genome child = parent1.copy();
mutate(child);
newPopulation.add(child);
}
}
population = newPopulation;
generation++;
}
private Genome tournamentSelect(List<Genome> candidates, int tournamentSize) {
Genome best = candidates.get(random.nextInt(candidates.size()));
for (int i = 1; i < tournamentSize; i++) {
Genome challenger = candidates.get(random.nextInt(candidates.size()));
if (challenger.fitness > best.fitness) best = challenger;
}
return best;
}
private Genome crossover(Genome parent1, Genome parent2) {
Genome child = new Genome();
child.maxNodeId = Math.max(parent1.maxNodeId, parent2.maxNodeId);
// 复制所有节点
Set<Integer> nodeIds = new HashSet<>();
for (NodeGene n : parent1.nodes) nodeIds.add(n.id);
for (NodeGene n : parent2.nodes) nodeIds.add(n.id);
for (int id : nodeIds) {
// 简化：使用父节点类型（NEAT通常按fitness处理）
NodeGene.NodeType type = NodeGene.NodeType.HIDDEN;
for (NodeGene n : parent1.nodes) {
if (n.id == id) { type = n.type; break; }
}
child.nodes.add(new NodeGene(id, type));
}
// 对齐连接基因
Map<Integer, ConnectionGene> map1 = new HashMap<>();
Map<Integer, ConnectionGene> map2 = new HashMap<>();
for (ConnectionGene c : parent1.connections) map1.put(c.innovation, c);
for (ConnectionGene c : parent2.connections) map2.put(c.innovation, c);
Set<Integer> allInnovations = new HashSet<>(map1.keySet());
allInnovations.addAll(map2.keySet());
for (int innov : allInnovations) {
ConnectionGene g1 = map1.get(innov);
ConnectionGene g2 = map2.get(innov);
if (g1 != null && g2 != null) {
// 共有基因：随机继承
ConnectionGene chosen = random.nextBoolean() ? g1 : g2;
child.connections.add(chosen.copy());
} else if (g1 != null) {
// 来自更优父代的断裂基因
if (parent1.fitness >= parent2.fitness) {
child.connections.add(g1.copy());
}
} else if (g2 != null) {
if (parent2.fitness >= parent1.fitness) {
child.connections.add(g2.copy());
}
}
}
return child;
}
private void mutate(Genome genome) {
// 权重突变
for (ConnectionGene c : genome.connections) {
if (random.nextDouble() < WEIGHT_MUTATION_RATE) {
if (random.nextDouble() < 0.1) {
c.weight = random.nextGaussian() * 2; // 完全重置
} else {
c.weight += random.nextGaussian() * 0.5; // 微调
}
}
}
// 添加连接
if (random.nextDouble() < ADD_CONNECTION_RATE) {
addConnectionMutation(genome);
}
// 添加节点
if (random.nextDouble() < ADD_NODE_RATE) {
addNodeMutation(genome);
}
}
private void addConnectionMutation(Genome genome) {
List<Integer> nodeIds = new ArrayList<>();
for (NodeGene n : genome.nodes) nodeIds.add(n.id);
Collections.shuffle(nodeIds, random);
for (int i = 0; i < Math.min(20, nodeIds.size()); i++) {
for (int j = 0; j < Math.min(20, nodeIds.size()); j++) {
int inId = nodeIds.get(i);
int outId = nodeIds.get(j);
if (inId == outId) continue;
boolean exists = false;
for (ConnectionGene c : genome.connections) {
if (c.inNode == inId && c.outNode == outId) { exists = true; break; }
}
if (!exists) {
int innov = tracker.getInnovation(inId, outId);
genome.connections.add(new ConnectionGene(inId, outId,
random.nextGaussian(), true, innov));
return;
}
}
}
}
private void addNodeMutation(Genome genome) {
if (genome.connections.isEmpty()) return;
ConnectionGene chosen = genome.connections.get(random.nextInt(genome.connections.size()));
if (!chosen.enabled) return;
chosen.enabled = false;
genome.maxNodeId++;
int newNodeId = genome.maxNodeId;
genome.nodes.add(new NodeGene(newNodeId, NodeGene.NodeType.HIDDEN));
int innov1 = tracker.getInnovation(chosen.inNode, newNodeId);
genome.connections.add(new ConnectionGene(chosen.inNode, newNodeId, 1.0, true, innov1));
int innov2 = tracker.getInnovation(newNodeId, chosen.outNode);
genome.connections.add(new ConnectionGene(newNodeId, chosen.outNode, chosen.weight, true, innov2));
}
}
/**
* 主程序入口
*/
public class AsteroidsNEATDemo {
public static void main(String[] args) {
Random random = new Random(42);
NEATEngine engine = new NEATEngine(random);
engine.initialize();
System.out.println("=== NEAT训练小行星AI ===");
for (int gen = 0; gen < 50; gen++) {
engine.evaluate();
double maxFitness = engine.population.stream()
.mapToDouble(g -> g.fitness).max().orElse(0);
double avgFitness = engine.population.stream()
.mapToDouble(g -> g.fitness).average().orElse(0);
System.out.printf("Generation %d: Max=%.1f, Avg=%.1f, Species=%d%n",
gen, maxFitness, avgFitness,
engine.speciate().size());
engine.reproduce();
}
// 最终评估
engine.evaluate();
Genome champion = engine.population.stream()
.max(Comparator.comparingDouble(g -> g.fitness)).orElse(null);
System.out.printf("\n最佳个体适应度: %.1f%n", champion != null ? champion.fitness : 0);
System.out.println("网络节点数: " + champion.nodes.size());
System.out.println("网络连接数: " + champion.connections.size());
}
}
算法分析
时间复杂度
- 神经网络前馈计算：O(E)，E为启用连接数
- 单代评估：O(P × T × E)，P为种群大小，T为单局最大步数
- 物种形成：O(P² × G)，G为平均基因组大小
空间复杂度
- 种群存储：O(P × G)
NEAT的优势
相比固定拓扑的神经网络进化（如简单遗传算法优化权重），NEAT通过渐进式复杂化和物种保护机制，显著提高了在复杂任务中的收敛速度和最终性能。在小行星这类需要感知-决策闭环的任务中，NEAT能够自动发现合适的传感器连接模式。
扩展思考
- 记忆增强：引入循环连接或外部记忆，使飞船能够追踪陨石运动轨迹。
- 多目标优化：同时优化生存时间和击碎陨石数量，使用NSGA-II等多目标进化算法。
- 协进化：同时进化AI玩家和游戏难度（陨石生成策略），实现自动课程学习。
总结
NEAT算法通过历史标记、物种形成和渐进式复杂化三大核心机制，实现了神经网络结构与权重的协同进化。在小行星游戏中的应用展示了神经进化在动态环境决策中的强大能力。相比传统深度学习需要大量标注数据，NEAT仅需适应度反馈即可自主学习，是处理强化学习问题的有力替代方案。
