每日算法 — 使用java实现Flappy Bird：遗传算法进化神经网络与自适应跳越策略

Flappy Bird 是一款风靡全球的休闲小游戏，玩家通过点击屏幕控制小鸟飞越不断出现的管道间隙。游戏规则看似简单，但要让 AI 自主学会飞行策略却涉及神经进化算法的核心思想。本文将用 Java 实现一个完整的 Flappy Bird AI 训练系统，基于遗传算法（Genetic Algorithm）进化神经网络权重，使小鸟能够在多代迭代中自适应地掌握跳越时机。

一、问题分析与算法设计

1.1 游戏状态建模

小鸟的决策需要感知当前环境状态。我们提取以下关键输入特征作为神经网络的输入层：

• 小鸟与上方管道的垂直距离
• 小鸟与下方管道的垂直距离
• 小鸟与前方管道的水平距离
• 小鸟当前的垂直速度

这四个特征足以描述小鸟当前面临的决策场景。

1.2 神经网络结构

采用简单的前馈神经网络（Feedforward Neural Network）：

• 输入层：4 个神经元（对应上述 4 个特征）
• 隐藏层：6 个神经元，使用 Sigmoid 激活函数
• 输出层：1 个神经元，输出跳跃概率

当输出值大于 0.5 时，小鸟执行跳跃动作。

1.3 遗传算法流程

遗传算法通过模拟自然选择过程来优化神经网络权重，核心步骤包括：

1. 种群初始化：随机生成 N 个个体的神经网络权重
2. 适应度评估：每个个体控制小鸟飞行，存活时间越长、穿过管道越多，适应度越高
3. 选择操作：根据适应度采用轮盘赌选择父代
4. 交叉操作：以一定概率交换两个父代的神经网络权重
5. 变异操作：以一定概率对权重添加随机扰动
6. 迭代进化：重复评估-选择-交叉-变异，直到收敛

二、Java 实现

2.1 神经网络类

import java.util.Random;

/**
 * 前馈神经网络：4输入 -> 6隐藏 -> 1输出
 * 使用Sigmoid激活函数
 */
public class NeuralNetwork {
    private static final Random RAND = new Random();

    // 网络拓扑参数
    private final int inputSize = 4;
    private final int hiddenSize = 6;
    private final int outputSize = 1;

    // 权重矩阵
    private double[][] weightsIH; // 输入到隐藏层 [hiddenSize][inputSize]
    private double[][] weightsHO; // 隐藏到输出层 [outputSize][hiddenSize]
    private double[] biasH;       // 隐藏层偏置
    private double[] biasO;       // 输出层偏置

    public NeuralNetwork() {
        weightsIH = new double[hiddenSize][inputSize];
        weightsHO = new double[outputSize][hiddenSize];
        biasH = new double[hiddenSize];
        biasO = new double[outputSize];
        randomizeWeights();
    }

    /**
     * 从权重数组构造网络（用于遗传算法的基因编码）
     */
    public NeuralNetwork(double[] genes) {
        this();
        int idx = 0;
        for (int i = 0; i < hiddenSize; i++) {
            for (int j = 0; j < inputSize; j++) {
                weightsIH[i][j] = genes[idx++];
            }
            biasH[i] = genes[idx++];
        }
        for (int i = 0; i < outputSize; i++) {
            for (int j = 0; j < hiddenSize; j++) {
                weightsHO[i][j] = genes[idx++];
            }
            biasO[i] = genes[idx++];
        }
    }

    /**
     * 随机初始化所有权重，使用Xavier初始化策略
     */
    private void randomizeWeights() {
        double limitIH = Math.sqrt(6.0 / (inputSize + hiddenSize));
        double limitHO = Math.sqrt(6.0 / (hiddenSize + outputSize));

        for (int i = 0; i < hiddenSize; i++) {
            for (int j = 0; j < inputSize; j++) {
                weightsIH[i][j] = (RAND.nextDouble() * 2 - 1) * limitIH;
            }
            biasH[i] = (RAND.nextDouble() * 2 - 1) * limitIH;
        }
        for (int i = 0; i < outputSize; i++) {
            for (int j = 0; j < hiddenSize; j++) {
                weightsHO[i][j] = (RAND.nextDouble() * 2 - 1) * limitHO;
            }
            biasO[i] = (RAND.nextDouble() * 2 - 1) * limitHO;
        }
    }

    /**
     * 前向传播：根据输入特征计算输出
     * @param inputs 4维特征向量 [birdY-gapTop, birdY-gapBottom, distance, velocity]
     * @return 输出层激活值，大于0.5建议跳跃
     */
    public double feedForward(double[] inputs) {
        // 隐藏层计算
        double[] hidden = new double[hiddenSize];
        for (int i = 0; i < hiddenSize; i++) {
            double sum = biasH[i];
            for (int j = 0; j < inputSize; j++) {
                sum += inputs[j] * weightsIH[i][j];
            }
            hidden[i] = sigmoid(sum);
        }

        // 输出层计算
        double output = biasO[0];
        for (int j = 0; j < hiddenSize; j++) {
            output += hidden[j] * weightsHO[0][j];
        }
        return sigmoid(output);
    }

    private double sigmoid(double x) {
        return 1.0 / (1.0 + Math.exp(-x));
    }

    /**
     * 将网络权重编码为一维基因数组
     */
    public double[] toGenes() {
        int geneLength = hiddenSize * (inputSize + 1) + outputSize * (hiddenSize + 1);
        double[] genes = new double[geneLength];
        int idx = 0;
        for (int i = 0; i < hiddenSize; i++) {
            System.arraycopy(weightsIH[i], 0, genes, idx, inputSize);
            idx += inputSize;
            genes[idx++] = biasH[i];
        }
        for (int i = 0; i < outputSize; i++) {
            System.arraycopy(weightsHO[i], 0, genes, idx, hiddenSize);
            idx += hiddenSize;
            genes[idx++] = biasO[i];
        }
        return genes;
    }

    /**
     * 基因长度：用于遗传算法初始化
     */
    public static int getGeneLength() {
        return 6 * (4 + 1) + 1 * (6 + 1); // 37
    }
}

2.2 游戏环境与适应度评估

/**
 * Flappy Bird 游戏模拟器
 * 简化物理模型，用于快速评估神经网络表现
 */
public class GameEnvironment {
    // 游戏参数
    private static final double GRAVITY = 0.5;
    private static final double JUMP_STRENGTH = -6.0;
    private static final int PIPE_WIDTH = 60;
    private static final int PIPE_GAP = 120;
    private static final int PIPE_SPEED = 3;
    private static final int SCREEN_WIDTH = 400;
    private static final int SCREEN_HEIGHT = 600;
    private static final int BIRD_RADIUS = 15;

    // 状态变量
    private double birdY, birdVelocity;
    private double pipeX, pipeGapY;
    private int score;
    private boolean alive;
    private Random rand;

    public GameEnvironment() {
        rand = new Random();
        reset();
    }

    /**
     * 重置游戏状态
     */
    public void reset() {
        birdY = SCREEN_HEIGHT / 2.0;
        birdVelocity = 0;
        pipeX = SCREEN_WIDTH;
        pipeGapY = 150 + rand.nextInt(SCREEN_HEIGHT - 300);
        score = 0;
        alive = true;
    }

    /**
     * 执行一帧游戏逻辑
     * @param jump 是否跳跃
     */
    public void step(boolean jump) {
        if (!alive) return;

        // 更新小鸟物理状态
        if (jump) {
            birdVelocity = JUMP_STRENGTH;
        }
        birdVelocity += GRAVITY;
        birdY += birdVelocity;

        // 更新管道位置
        pipeX -= PIPE_SPEED;
        if (pipeX < -PIPE_WIDTH) {
            pipeX = SCREEN_WIDTH;
            pipeGapY = 150 + rand.nextInt(SCREEN_HEIGHT - 300);
            score++;
        }

        // 碰撞检测
        if (birdY < BIRD_RADIUS || birdY > SCREEN_HEIGHT - BIRD_RADIUS) {
            alive = false;
        }
        // 检测是否撞击管道
        if (pipeX < 80 && pipeX + PIPE_WIDTH > 50) {
            if (birdY - BIRD_RADIUS < pipeGapY - PIPE_GAP / 2.0 ||
                birdY + BIRD_RADIUS > pipeGapY + PIPE_GAP / 2.0) {
                alive = false;
            }
        }
    }

    /**
     * 获取神经网络输入特征（已归一化）
     */
    public double[] getInputs() {
        double[] inputs = new double[4];
        inputs[0] = (pipeGapY - PIPE_GAP / 2.0 - birdY) / SCREEN_HEIGHT; // 到上管道距离
        inputs[1] = (birdY - (pipeGapY + PIPE_GAP / 2.0)) / SCREEN_HEIGHT; // 到下管道距离
        inputs[2] = pipeX / SCREEN_WIDTH; // 水平距离
        inputs[3] = birdVelocity / 10.0;  // 垂直速度
        return inputs;
    }

    /**
     * 使用神经网络控制小鸟，运行完整一局并返回适应度
     */
    public double evaluateFitness(NeuralNetwork nn) {
        reset();
        int frames = 0;
        final int MAX_FRAMES = 10000; // 防止无限飞行

        while (alive && frames < MAX_FRAMES) {
            double[] inputs = getInputs();
            double output = nn.feedForward(inputs);
            step(output > 0.5);
            frames++;
        }

        // 适应度 = 穿过的管道数 * 100 + 存活帧数（鼓励飞得更远）
        return score * 100.0 + frames;
    }

    public boolean isAlive() { return alive; }
    public int getScore() { return score; }
}

2.3 遗传算法引擎

import java.util.Arrays;
import java.util.Comparator;

/**
 * 遗传算法引擎：管理种群进化过程
 */
public class GeneticEngine {
    private static final Random RAND = new Random();

    private final int populationSize;
    private final double mutationRate;
    private final double crossoverRate;
    private final int eliteCount;
    private final int geneLength;

    private Individual[] population;
    private GameEnvironment[] envs;

    /**
     * 个体封装：基因与适应度
     */
    static class Individual {
        double[] genes;
        double fitness;
        NeuralNetwork network;

        Individual(int geneLength) {
            genes = new double[geneLength];
            for (int i = 0; i < geneLength; i++) {
                genes[i] = RAND.nextDouble() * 2 - 1;
            }
            network = new NeuralNetwork(genes);
        }

        Individual(double[] genes) {
            this.genes = genes.clone();
            this.network = new NeuralNetwork(genes);
        }
    }

    public GeneticEngine(int popSize, double mutRate, double crossRate, int elite) {
        this.populationSize = popSize;
        this.mutationRate = mutRate;
        this.crossoverRate = crossRate;
        this.eliteCount = elite;
        this.geneLength = NeuralNetwork.getGeneLength();

        population = new Individual[popSize];
        envs = new GameEnvironment[popSize];

        for (int i = 0; i < popSize; i++) {
            population[i] = new Individual(geneLength);
            envs[i] = new GameEnvironment();
        }
    }

    /**
     * 评估种群中所有个体的适应度
     */
    public void evaluatePopulation() {
        for (int i = 0; i < populationSize; i++) {
            population[i].fitness = envs[i].evaluateFitness(population[i].network);
        }
        // 按适应度降序排序
        Arrays.sort(population, Comparator.comparingDouble((Individual ind) -> ind.fitness).reversed());
    }

    /**
     * 轮盘赌选择：按适应度比例选择父代
     */
    private Individual rouletteSelect() {
        double totalFitness = 0;
        for (Individual ind : population) {
            totalFitness += ind.fitness;
        }
        double pick = RAND.nextDouble() * totalFitness;
        double current = 0;
        for (Individual ind : population) {
            current += ind.fitness;
            if (current >= pick) {
                return ind;
            }
        }
        return population[populationSize - 1];
    }

    /**
     * 单点交叉：交换两个父代的基因片段
     */
    private Individual[] crossover(Individual p1, Individual p2) {
        if (RAND.nextDouble() > crossoverRate) {
            return new Individual[]{new Individual(p1.genes), new Individual(p2.genes)};
        }
        int point = RAND.nextInt(geneLength);
        double[] child1 = new double[geneLength];
        double[] child2 = new double[geneLength];

        System.arraycopy(p1.genes, 0, child1, 0, point);
        System.arraycopy(p2.genes, point, child1, point, geneLength - point);
        System.arraycopy(p2.genes, 0, child2, 0, point);
        System.arraycopy(p1.genes, point, child2, point, geneLength - point);

        return new Individual[]{new Individual(child1), new Individual(child2)};
    }

    /**
     * 高斯变异：对基因添加小幅随机扰动
     */
    private void mutate(Individual ind) {
        for (int i = 0; i < geneLength; i++) {
            if (RAND.nextDouble() < mutationRate) {
                ind.genes[i] += RAND.nextGaussian() * 0.3;
                // 限制权重范围
                ind.genes[i] = Math.max(-3, Math.min(3, ind.genes[i]));
            }
        }
        ind.network = new NeuralNetwork(ind.genes);
    }

    /**
     * 进化一代：选择 -> 交叉 -> 变异
     */
    public void evolve() {
        Individual[] newPop = new Individual[populationSize];

        // 保留精英个体直接进入下一代
        for (int i = 0; i < eliteCount; i++) {
            newPop[i] = new Individual(population[i].genes);
        }

        // 生成新个体填充剩余位置
        int idx = eliteCount;
        while (idx < populationSize) {
            Individual p1 = rouletteSelect();
            Individual p2 = rouletteSelect();
            Individual[] children = crossover(p1, p2);

            for (Individual child : children) {
                if (idx >= populationSize) break;
                mutate(child);
                newPop[idx++] = child;
            }
        }

        population = newPop;
    }

    public Individual getBest() {
        return population[0];
    }

    public double getAverageFitness() {
        double sum = 0;
        for (Individual ind : population) {
            sum += ind.fitness;
        }
        return sum / populationSize;
    }
}

2.4 主程序与训练入口

/**
 * Flappy Bird AI 训练主程序
 */
public class FlappyBirdAI {
    public static void main(String[] args) {
        final int POPULATION_SIZE = 100;
        final int GENERATIONS = 200;
        final double MUTATION_RATE = 0.05;
        final double CROSSOVER_RATE = 0.7;
        final int ELITE_COUNT = 5;

        GeneticEngine engine = new GeneticEngine(
            POPULATION_SIZE, MUTATION_RATE, CROSSOVER_RATE, ELITE_COUNT
        );

        System.out.println("=== Flappy Bird 遗传算法训练开始 ===");
        System.out.println("种群大小: " + POPULATION_SIZE);
        System.out.println("进化代数: " + GENERATIONS);
        System.out.println();

        for (int gen = 1; gen <= GENERATIONS; gen++) {
            engine.evaluatePopulation();
            GeneticEngine.Individual best = engine.getBest();

            if (gen % 10 == 0 || gen == 1) {
                System.out.printf("第 %3d 代 | 最优适应度: %.1f | 平均适应度: %.1f | 最优得分: %d%n",
                    gen, best.fitness, engine.getAverageFitness(),
                    new GameEnvironment().evaluateFitness(best.network) / 100);
            }

            // 如果已经能稳定穿过50个管道，提前终止
            if (best.fitness > 5000) {
                System.out.println("\n>>> 训练收敛，提前终止！");
                break;
            }

            engine.evolve();
        }

        // 最终评估
        engine.evaluatePopulation();
        GeneticEngine.Individual champion = engine.getBest();
        System.out.println("\n=== 训练完成 ===");
        System.out.println("冠军适应度: " + champion.fitness);

        // 打印冠军网络的权重（可用于持久化保存）
        System.out.println("冠军基因编码:");
        double[] genes = champion.network.toGenes();
        for (int i = 0; i < Math.min(genes.length, 10); i++) {
            System.out.printf("  gene[%d] = %.4f%n", i, genes[i]);
        }
        System.out.println("  ... (共 " + genes.length + " 个基因)");
    }
}

三、算法复杂度分析

其中 P 为种群规模，典型值 50~200。整体训练时间主要取决于每局游戏模拟的帧数，对于简单场景可在数秒内完成收敛。

四、关键优化技巧

1. Xavier 权重初始化：避免初始权重过大导致 Sigmoid 饱和，加速早期进化
2. 精英保留策略：每代保留最优个体不变异，防止优秀基因丢失
3. 高斯变异：相比均匀变异，高斯扰动能更精细地搜索局部最优
4. 适应度函数设计：同时考虑得分和存活帧数，避免局部最优（如悬停在安全区域不前进）
5. 权重截断：将权重限制在 [-3, 3] 范围内，防止数值溢出

五、总结

本文通过 Java 实现了一套完整的 Flappy Bird AI 训练系统，核心在于将神经网络控制策略编码为基因序列，通过遗传算法的选择、交叉和变异操作在多代迭代中不断优化。整个系统不依赖梯度反向传播，完全基于进化策略搜索最优权重，对于非可导或奖励稀疏的问题尤为适用。读者可以在此基础上尝试调整网络拓扑（如增加隐藏层）、改变选择策略（如锦标赛选择）或引入共进化机制，进一步探索神经进化算法的潜力。