遗传算法：位串的适者生存

自然如何解决复杂问题，以及我们如何把它转化为代码。一篇用 Java 讲解的实用入门。

经过数十亿年，自然演化出了一套极为高效的优化过程：进化。遗传算法（GA）把这一原理迁移到计算机科学中，用来解决那些经典算法束手无策的问题。

基本原理

设想你要为一个问题寻找最佳解，但解空间极其庞大。逐一尝试所有可能性需要耗费数年时间。遗传算法采用了另一种思路：它模拟进化。

一个具体的例子

我们的目标：找到一个所有位都为 1 的二进制串。听起来很简单？确实如此。但这个简单的例子展示了所有概念，而这些概念在更复杂的问题中同样适用。

个体：一个包含 5 个位的数组，用 0 或 1 随机初始化。

适应度：1 的个数。最大值为 5，此时我们就得到了完美解。

Java 中的实现

个体

每个个体代表一个可能的解：

public class Individual {
    private int[] genes = new int[5];
    private int fitness = 0;

    // Random initialization
    public Individual() {
        Random rn = new Random();
        for (int i = 0; i < genes.length; i++) {
            genes[i] = rn.nextInt(2); // 0 or 1
        }
    }

    // Fitness = number of ones
    public void calcFitness() {
        fitness = 0;
        for (int gene : genes) {
            if (gene == 1) fitness++;
        }
    }
}

种群

一个种群管理多个个体：

public class Population {
    private Individual[] individuals = new Individual[10];
    private int fittest = 0; // Best fitness of the population

    public Individual getFittest() {
        int maxFit = Integer.MIN_VALUE;
        Individual fittestIndividual = null;

        for (Individual ind : individuals) {
            if (ind.getFitness() > maxFit) {
                maxFit = ind.getFitness();
                fittestIndividual = ind;
            }
        }
        return fittestIndividual;
    }

    public Individual getSecondFittest() {
        // Similar, but second best
        ...
    }
}

选择

选出两个最优个体作为父代。选择方法有很多，比如锦标赛选择或轮盘赌选择。这里我们采用精英选择：简单而有效。

public void selection() {
    fittest = population.getFittest();
    secondFittest = population.getSecondFittest();
}

交叉

核心机制：在一个随机位置，交换两个父代的基因。交叉点之前的基因会在两个父代之间互换。

public void crossover() {
    Random rn = new Random();
    int crossOverPoint = rn.nextInt(fittest.genes.length);

    for (int i = 0; i < crossOverPoint; i++) {
        int temp = fittest.genes[i];
        fittest.genes[i] = secondFittest.genes[i];
        secondFittest.genes[i] = temp;
    }
}

变异

变异防止算法陷入局部最优。随机翻转一个位。

public void mutation() {
    Random rn = new Random();

    // 10% probability of mutation
    if (rn.nextDouble() < 0.1) {
        int mutationPoint = rn.nextInt(fittest.genes.length);

        // Flip bit: 0 → 1 or 1 → 0
        fittest.genes[mutationPoint] = 1 - fittest.genes[mutationPoint];
    }
}

算法

把一切组合起来：不断迭代，直到找到完美解。

public static void main(String[] args) {
    GeneticAlgorithm ga = new GeneticAlgorithm();

    // 1. Initialize population
    ga.population.initializePopulation(10);
    ga.population.calculateFitness();

    int generation = 0;

    // 2. Evolution loop
    while (ga.population.fittest < 5) {
        generation++;

        // Selection
        ga.selection();

        // Crossover
        ga.crossover();

        // Mutation
        ga.mutation();

        // Replace weakest individual
        ga.addFittestOffspring();

        // Recalculate
        ga.population.calculateFitness();

        System.out.println("Generation: " + generation +
            " Fitness: " + ga.population.fittest);
    }

    System.out.println("Solution found in generation " + generation);
}

典型输出

Generation: 1  Fitness: 3
Generation: 2  Fitness: 3
Generation: 3  Fitness: 4
Generation: 4  Fitness: 4
Generation: 5  Fitness: 5
Solution found in generation 5
Genes: [1, 1, 1, 1, 1]

仅用 5 代、10 个个体，算法就找到了完美解。对于更复杂的问题会耗时更久，但原理完全相同。

真实世界的应用场景

这个简单的例子可以推广到复杂问题上：

关键心得

“遗传算法并不保证得到最优解，但它们往往能在可接受的时间内找到一个非常好的解。”

1. 编码至关重要

你如何把问题表示为基因，决定了成败。二进制编码很简单，但排列、浮点数或复杂结构往往更合适。

2. 在探索与利用之间取得平衡

变异过多 = 搜索混乱无序。变异过少 = 过早收敛。合适的变异率因具体问题而异。

3. 适应度函数是关键

糟糕的适应度函数会导致糟糕的解。请在打磨一个精确的评估函数上投入时间。

4. 保持多样性

当所有个体都变得相似时，进化就会停滞。像拥挤（crowding）或小生境（niching）这样的技术会有所帮助。

结论

对于解空间大到无法穷举搜索的优化问题，遗传算法是一件强大的工具。它的实现出人意料地简单：种群、适应度、选择、交叉、变异。真正的艺术在于恰当的编码和合适的适应度函数。

它的妙处在于：你无需理解最优解到底长什么样。你只需要能够评估一个解有多好。剩下的交给进化去完成。

所用技术：

对优化算法或 AI 驱动的解决方案感兴趣？联系我，我期待与你交流。