每日算法 — 使用java实现遗传算法：生物进化驱动的函数优化与路径规划

引言：从自然选择到算法设计

1859年，达尔文发表《物种起源》，提出自然选择理论——生物种群通过遗传、变异和选择，逐步演化出适应环境的优秀个体。这一思想不仅改变了生物学，也启发了计算机科学家：能否将进化机制抽象为算法，用来自动求解复杂的优化问题？

遗传算法（Genetic Algorithm, GA） 正是这一设想的产物。作为一种经典的进化计算方法，GA通过模拟种群的繁衍过程，在巨大的解空间中进行高效搜索。它不依赖问题的梯度信息，对非凸、多峰值、离散型问题都有出色的适应能力。

本文将用 Java 从零实现一个完整的遗传算法框架，并应用于两个经典场景：函数优化（寻找复杂函数的全局最大值）和 TSP路径规划（求解旅行商最短路径）。你将看到选择、交叉、变异三大算子如何协同工作，以及参数调优对收敛速度的影响。

核心概念与算法框架

生物隐喻与算法映射

遗传算法的魅力在于它用一套简洁的抽象，模拟了生物进化的全过程：

标准遗传算法流程

遗传算法的核心迭代流程如下：

1. 初始化：随机生成 N 个个体构成初始种群
2. 评估：计算每个个体的适应度值
3. 选择：根据适应度选择优秀个体进入下一代
4. 交叉：以概率 Pc 对选中个体进行基因重组
5. 变异：以概率 Pm 对个体基因进行随机扰动
6. 终止判断：若达到最大代数或收敛条件，输出最优解；否则返回步骤2

Java 完整实现

1. 核心框架：染色体与种群

首先定义染色体的抽象接口和种群管理类：

import java.util.*;
import java.util.function.Function;

/**
 * 染色体接口：定义遗传算法个体的基本操作
 * @param <T> 染色体的具体类型（如二进制串、排列等）
 */
interface Chromosome<T extends Chromosome<T>> extends Comparable<T> {
    /**
     * 计算适应度值（越高越优）
     */
    double fitness();

    /**
     * 交叉操作：与另一个个体进行基因重组
     * @param other 另一个父代个体
     * @return 重组后的新个体（通常返回两个中的一个）
     */
    T crossover(T other);

    /**
     * 变异操作：对当前个体进行随机扰动
     */
    void mutate();

    /**
     * 创建当前个体的深拷贝
     */
    T copy();
}

/**
 * 遗传算法引擎
 * 支持多种选择策略（轮盘赌、锦标赛）和精英保留机制
 */
class GeneticAlgorithm<T extends Chromosome<T>> {
    private final List<T> population;          // 当前种群
    private final int populationSize;          // 种群规模
    private final double crossoverRate;        // 交叉概率
    private final double mutationRate;         // 变异概率
    private final int elitismCount;            // 精英保留数量
    private final Random random;
    private final Function<Random, T> factory; // 个体生成工厂

    private T bestIndividual;                  // 历史最优个体
    private double bestFitness;                // 历史最优适应度
    private int generation;                    // 当前代数

    public GeneticAlgorithm(int populationSize, double crossoverRate,
                            double mutationRate, int elitismCount,
                            Function<Random, T> factory, Random random) {
        this.populationSize = populationSize;
        this.crossoverRate = crossoverRate;
        this.mutationRate = mutationRate;
        this.elitismCount = elitismCount;
        this.factory = factory;
        this.random = random;
        this.population = new ArrayList<>(populationSize);
        this.bestFitness = Double.NEGATIVE_INFINITY;
        this.generation = 0;
    }

    /**
     * 初始化种群：随机生成指定数量的个体
     */
    public void initialize() {
        population.clear();
        for (int i = 0; i < populationSize; i++) {
            population.add(factory.apply(random));
        }
        evaluate();
    }

    /**
     * 评估种群：计算所有个体的适应度，并更新历史最优
     */
    private void evaluate() {
        for (T individual : population) {
            double fit = individual.fitness();
            if (fit > bestFitness) {
                bestFitness = fit;
                bestIndividual = individual.copy();
            }
        }
    }

    /**
     * 轮盘赌选择：适应度越高的个体被选中的概率越大
     * 为避免负适应度问题，先进行平移处理
     */
    private T rouletteWheelSelection() {
        double minFit = population.stream().mapToDouble(Chromosome::fitness).min().orElse(0);
        double offset = minFit < 0 ? -minFit + 1e-6 : 0;
        double total = population.stream().mapToDouble(ind -> ind.fitness() + offset).sum();
        double point = random.nextDouble() * total;
        double cumulative = 0;
        for (T ind : population) {
            cumulative += ind.fitness() + offset;
            if (cumulative >= point) {
                return ind.copy();
            }
        }
        return population.get(population.size() - 1).copy();
    }

    /**
     * 锦标赛选择：随机抽取k个个体，返回最优者
     *  tournamentSize 越大，选择压力越强
     */
    private T tournamentSelection(int tournamentSize) {
        T best = null;
        double bestFit = Double.NEGATIVE_INFINITY;
        for (int i = 0; i < tournamentSize; i++) {
            T candidate = population.get(random.nextInt(population.size()));
            double fit = candidate.fitness();
            if (fit > bestFit) {
                bestFit = fit;
                best = candidate;
            }
        }
        return best != null ? best.copy() : population.get(0).copy();
    }

    /**
     * 进化一代：选择 -> 交叉 -> 变异 -> 精英保留
     */
    public void evolve() {
        // 按适应度降序排序，便于精英保留
        population.sort(Comparator.reverseOrder());

        List<T> newPopulation = new ArrayList<>(populationSize);

        // 精英保留：直接将最优秀的个体复制到下一代
        for (int i = 0; i < elitismCount && i < population.size(); i++) {
            newPopulation.add(population.get(i).copy());
        }

        // 生成剩余个体
        while (newPopulation.size() < populationSize) {
            // 选择两个父代（使用锦标赛选择，选择压力适中）
            T parent1 = tournamentSelection(3);
            T parent2 = tournamentSelection(3);

            // 交叉
            T offspring;
            if (random.nextDouble() < crossoverRate) {
                offspring = parent1.crossover(parent2);
            } else {
                offspring = parent1.copy();
            }

            // 变异
            if (random.nextDouble() < mutationRate) {
                offspring.mutate();
            }

            newPopulation.add(offspring);
        }

        population.clear();
        population.addAll(newPopulation);
        generation++;
        evaluate();
    }

    public T getBestIndividual() { return bestIndividual; }
    public double getBestFitness() { return bestFitness; }
    public int getGeneration() { return generation; }
    public List<T> getPopulation() { return population; }
}

2. 应用一：函数优化（实数编码）

第一个场景是用遗传算法寻找复杂函数的全局最大值。这里使用实数编码，每个基因直接对应一个浮点数变量。

/**
 * 实数编码染色体：用于连续函数优化
 * 每个基因是一个double值，对应函数的一个输入变量
 */
class RealChromosome implements Chromosome<RealChromosome> {
    private final double[] genes;     // 基因数组（实数向量）
    private final double[] minBounds; // 各维度下限
    private final double[] maxBounds; // 各维度上限
    private final Function<double[], Double> fitnessFunc; // 适应度函数
    private double fitnessCache = Double.NaN;
    private final Random random;

    public RealChromosome(double[] genes, double[] minBounds, double[] maxBounds,
                          Function<double[], Double> fitnessFunc, Random random) {
        this.genes = genes.clone();
        this.minBounds = minBounds;
        this.maxBounds = maxBounds;
        this.fitnessFunc = fitnessFunc;
        this.random = random;
    }

    @Override
    public double fitness() {
        if (Double.isNaN(fitnessCache)) {
            fitnessCache = fitnessFunc.apply(genes);
        }
        return fitnessCache;
    }

    /**
     * 算术交叉： offspring = alpha * p1 + (1-alpha) * p2
     * 也可以扩展为SBX（模拟二进制交叉），这里采用简化版
     */
    @Override
    public RealChromosome crossover(RealChromosome other) {
        double[] childGenes = new double[genes.length];
        double alpha = random.nextDouble();
        for (int i = 0; i < genes.length; i++) {
            childGenes[i] = alpha * this.genes[i] + (1 - alpha) * other.genes[i];
            // 边界保护
            childGenes[i] = Math.max(minBounds[i], Math.min(maxBounds[i], childGenes[i]));
        }
        return new RealChromosome(childGenes, minBounds, maxBounds, fitnessFunc, random);
    }

    /**
     * 高斯变异：在基因值上叠加一个服从高斯分布的随机扰动
     * 扰动幅度随搜索范围动态调整
     */
    @Override
    public void mutate() {
        for (int i = 0; i < genes.length; i++) {
            double range = maxBounds[i] - minBounds[i];
            double noise = random.nextGaussian() * range * 0.1; // 标准差为范围的10%
            genes[i] += noise;
            genes[i] = Math.max(minBounds[i], Math.min(maxBounds[i], genes[i]));
        }
        fitnessCache = Double.NaN; // 变异后需要重新计算适应度
    }

    @Override
    public RealChromosome copy() {
        RealChromosome copy = new RealChromosome(genes, minBounds, maxBounds, fitnessFunc, random);
        copy.fitnessCache = this.fitnessCache;
        return copy;
    }

    @Override
    public int compareTo(RealChromosome o) {
        return Double.compare(this.fitness(), o.fitness());
    }

    public double[] getGenes() { return genes.clone(); }

    @Override
    public String toString() {
        return String.format("RealChromosome[genes=%s, fitness=%.6f]",
            Arrays.toString(genes), fitness());
    }
}

/**
 * 函数优化测试类
 * 测试函数：Rastrigin函数（多峰值，全局最优在 origin）
 * f(x) = 10n + sum(xi^2 - 10*cos(2*pi*xi))
 */
class FunctionOptimizationDemo {
    public static void main(String[] args) {
        Random random = new Random(42);
        int dimensions = 10;          // 10维空间
        int populationSize = 100;     // 种群规模
        int maxGenerations = 500;     // 最大迭代次数
        double crossoverRate = 0.8;   // 交叉概率
        double mutationRate = 0.1;    // 变异概率
        int elitismCount = 2;         // 精英保留数

        // Rastrigin函数定义（求最小值，因此取负作为适应度）
        java.util.function.Function<double[], Double> rastrigin = (x) -> {
            double sum = 0;
            for (double xi : x) {
                sum += xi * xi - 10 * Math.cos(2 * Math.PI * xi);
            }
            return -(10 * x.length + sum); // 取负，使适应度越大越优
        };

        double[] minBounds = new double[dimensions];
        double[] maxBounds = new double[dimensions];
        Arrays.fill(minBounds, -5.12);
        Arrays.fill(maxBounds, 5.12);

        // 个体生成工厂
        java.util.function.Function<Random, RealChromosome> factory = (rnd) -> {
            double[] genes = new double[dimensions];
            for (int i = 0; i < dimensions; i++) {
                genes[i] = minBounds[i] + rnd.nextDouble() * (maxBounds[i] - minBounds[i]);
            }
            return new RealChromosome(genes, minBounds, maxBounds, rastrigin, rnd);
        };

        GeneticAlgorithm<RealChromosome> ga = new GeneticAlgorithm<>(
            populationSize, crossoverRate, mutationRate, elitismCount, factory, random);

        ga.initialize();
        System.out.println("===== 函数优化：Rastrigin函数（10维） =====");
        System.out.printf("初始最优适应度: %.6f%n", ga.getBestFitness());

        for (int gen = 1; gen <= maxGenerations; gen++) {
            ga.evolve();
            if (gen % 50 == 0 || gen == 1) {
                RealChromosome best = ga.getBestIndividual();
                System.out.printf("Generation %d: best fitness = %.6f, solution = %s%n",
                    gen, ga.getBestFitness(), Arrays.toString(best.getGenes()));
            }
        }

        System.out.printf("\n最终最优适应度: %.6f%n", ga.getBestFitness());
        System.out.printf("最优解: %s%n", Arrays.toString(ga.getBestIndividual().getGenes()));
        System.out.println("理论最优值: 0.0 (在 origin 处)");
    }
}

3. 应用二：TSP路径规划（排列编码）

旅行商问题（TSP）是组合优化的经典难题。这里使用排列编码，每个染色体是一个城市访问序列，采用顺序交叉（OX, Order Crossover） 和 交换变异。

/**
 * 排列编码染色体：用于TSP等组合优化问题
 * 基因序列表示城市的访问顺序
 */
class PermutationChromosome implements Chromosome<PermutationChromosome> {
    private final int[] permutation;      // 城市排列
    private final double[][] distanceMatrix; // 城市间距离矩阵
    private double fitnessCache = Double.NaN;
    private final Random random;

    public PermutationChromosome(int[] permutation, double[][] distanceMatrix, Random random) {
        this.permutation = permutation.clone();
        this.distanceMatrix = distanceMatrix;
        this.random = random;
    }

    /**
     * TSP适应度：路径总长度的倒数
     * 路径越短，适应度越高
     */
    @Override
    public double fitness() {
        if (Double.isNaN(fitnessCache)) {
            double total = 0;
            int n = permutation.length;
            for (int i = 0; i < n; i++) {
                int from = permutation[i];
                int to = permutation[(i + 1) % n]; // 回到起点形成闭环
                total += distanceMatrix[from][to];
            }
            fitnessCache = 1.0 / (total + 1e-6); // 加极小值防止除零
        }
        return fitnessCache;
    }

    /**
     * 顺序交叉（Order Crossover, OX）：保持子序列的相对顺序
     * 步骤：
     * 1. 随机选择两个切点
     * 2. 将parent1切点间的片段直接复制给子代
     * 3. 从parent2中按顺序填充剩余位置（跳过已存在的城市）
     */
    @Override
    public PermutationChromosome crossover(PermutationChromosome other) {
        int n = permutation.length;
        int[] child = new int[n];
        Arrays.fill(child, -1);

        int cut1 = random.nextInt(n);
        int cut2 = random.nextInt(n);
        if (cut1 > cut2) { int tmp = cut1; cut1 = cut2; cut2 = tmp; }

        // 复制parent1的切点片段
        boolean[] used = new boolean[n];
        for (int i = cut1; i <= cut2; i++) {
            child[i] = this.permutation[i];
            used[this.permutation[i]] = true;
        }

        // 从parent2按顺序填充剩余位置
        int idx = (cut2 + 1) % n;
        for (int i = 0; i < n; i++) {
            int p2Idx = (cut2 + 1 + i) % n;
            int city = other.permutation[p2Idx];
            if (!used[city]) {
                child[idx] = city;
                used[city] = true;
                idx = (idx + 1) % n;
            }
        }

        return new PermutationChromosome(child, distanceMatrix, random);
    }

    /**
     * 交换变异：随机选择两个位置交换城市
     * 保持排列的合法性（无重复城市）
     */
    @Override
    public void mutate() {
        int n = permutation.length;
        int i = random.nextInt(n);
        int j = random.nextInt(n);
        int tmp = permutation[i];
        permutation[i] = permutation[j];
        permutation[j] = tmp;
        fitnessCache = Double.NaN;
    }

    @Override
    public PermutationChromosome copy() {
        PermutationChromosome copy = new PermutationChromosome(permutation, distanceMatrix, random);
        copy.fitnessCache = this.fitnessCache;
        return copy;
    }

    @Override
    public int compareTo(PermutationChromosome o) {
        return Double.compare(this.fitness(), o.fitness());
    }

    public int[] getPermutation() { return permutation.clone(); }

    /**
     * 获取路径总长度（调试用）
     */
    public double getPathLength() {
        fitness(); // 触发计算
        return 1.0 / fitnessCache - 1e-6;
    }

    @Override
    public String toString() {
        return String.format("Permutation[pathLen=%.2f, route=%s]",
            getPathLength(), Arrays.toString(permutation));
    }
}

/**
 * TSP求解演示
 */
class TspSolverDemo {
    public static void main(String[] args) {
        Random random = new Random(42);
        int cityCount = 30;           // 30个城市
        int populationSize = 200;     // 较大种群以覆盖解空间
        int maxGenerations = 1000;
        double crossoverRate = 0.9;   // TSP中交叉概率通常较高
        double mutationRate = 0.15;   // 适当提高变异率维持多样性
        int elitismCount = 3;

        // 随机生成城市坐标（二维平面）
        double[][] cities = new double[cityCount][2];
        for (int i = 0; i < cityCount; i++) {
            cities[i][0] = random.nextDouble() * 100;
            cities[i][1] = random.nextDouble() * 100;
        }

        // 预计算距离矩阵（欧几里得距离）
        double[][] distMatrix = new double[cityCount][cityCount];
        for (int i = 0; i < cityCount; i++) {
            for (int j = 0; j < cityCount; j++) {
                double dx = cities[i][0] - cities[j][0];
                double dy = cities[i][1] - cities[j][1];
                distMatrix[i][j] = Math.sqrt(dx * dx + dy * dy);
            }
        }

        // 个体生成工厂：随机生成一个合法排列
        java.util.function.Function<Random, PermutationChromosome> factory = (rnd) -> {
            int[] perm = new int[cityCount];
            for (int i = 0; i < cityCount; i++) perm[i] = i;
            // Fisher-Yates洗牌
            for (int i = cityCount - 1; i > 0; i--) {
                int j = rnd.nextInt(i + 1);
                int tmp = perm[i]; perm[i] = perm[j]; perm[j] = tmp;
            }
            return new PermutationChromosome(perm, distMatrix, rnd);
        };

        GeneticAlgorithm<PermutationChromosome> ga = new GeneticAlgorithm<>(
            populationSize, crossoverRate, mutationRate, elitismCount, factory, random);

        ga.initialize();
        System.out.println("===== TSP路径规划（30城市） =====");
        System.out.printf("初始最优路径长度: %.2f%n",
            ga.getBestIndividual().getPathLength());

        double prevBest = Double.POSITIVE_INFINITY;
        int stagnantGenerations = 0;

        for (int gen = 1; gen <= maxGenerations; gen++) {
            ga.evolve();
            double currentBest = ga.getBestIndividual().getPathLength();

            if (gen % 100 == 0) {
                System.out.printf("Generation %d: best path = %.2f%n", gen, currentBest);
            }

            // 检测收敛：若连续50代无改进，可提前终止
            if (currentBest < prevBest - 1e-3) {
                prevBest = currentBest;
                stagnantGenerations = 0;
            } else {
                stagnantGenerations++;
            }
        }

        PermutationChromosome best = ga.getBestIndividual();
        System.out.printf("\n最终最优路径长度: %.2f%n", best.getPathLength());
        System.out.println("最优访问顺序: " + Arrays.toString(best.getPermutation()));

        // 输出城市坐标供可视化
        System.out.println("\n城市坐标:");
        for (int i = 0; i < cityCount; i++) {
            System.out.printf("  City %d: (%.2f, %.2f)%n", i, cities[i][0], cities[i][1]);
        }
    }
}

4. 完整测试主程序

/**
 * 遗传算法综合测试主程序
 */
public class GeneticAlgorithmDemo {
    public static void main(String[] args) {
        System.out.println("╔══════════════════════════════════════════════════════════════╗");
        System.out.println("║           遗传算法（Genetic Algorithm）Java实现              ║");
        System.out.println("╚══════════════════════════════════════════════════════════════╝\n");

        // 运行函数优化测试
        FunctionOptimizationDemo.main(args);

        System.out.println("\n" + "=".repeat(60) + "\n");

        // 运行TSP测试
        TspSolverDemo.main(args);
    }
}

关键设计决策与参数调优

选择策略的选择

• 轮盘赌选择：适应度差异大时容易早熟收敛，适合适应度分布均匀的初期
• 锦标赛选择：通过调整 tournamentSize 控制选择压力，鲁棒性更强，是工程实践的首选

本文实现同时提供了两种策略，默认使用锦标赛选择（size=3）。

编码方式的影响

参数调优经验法则

• 种群规模：通常 50~200。问题越复杂、维度越高，种群应越大
• 交叉概率 Pc：0.6~0.95。太低则搜索停滞，太高则破坏优良模式
• 变异概率 Pm：0.01~0.2。太低则多样性不足，太高则退化为随机搜索
• 精英保留：保留前 1~5% 的最优个体，防止优秀基因丢失

复杂度分析

扩展方向

自适应遗传算法

传统GA的交叉率和变异率固定，而自适应GA（如Srinivas & Patnaik, 1994）根据种群的收敛程度动态调整参数：当种群多样性高时降低变异，当陷入局部最优时提高变异。

多目标优化：NSGA-II

当问题存在多个冲突目标（如TSP中的路径长度与风险最小化），NSGA-II通过非支配排序和拥挤距离维护Pareto前沿，是工程中最常用的多目标进化算法。

混合算法：Memetic Algorithm

将遗传算法的全局搜索能力与局部搜索（如2-opt、爬山法）结合。在每一代进化后，对部分个体执行局部优化，显著提升解的质量，尤其适合TSP这类具有明显邻域结构的问题。

总结

本文从零实现了一个通用的遗传算法框架，并应用于函数优化与TSP路径规划两个经典场景。你掌握了：

• 遗传算法的五大核心组件：编码、适应度、选择、交叉、变异
• 实数编码与高斯变异在连续优化中的应用
• 排列编码与顺序交叉在组合优化中的应用
• 精英保留、锦标赛选择等关键技术的实现细节
• 参数调优的经验法则与算法扩展方向

遗传算法的真正威力不在于它总能找到理论最优解，而在于它提供了一套不依赖问题领域知识的通用搜索框架。面对NP-hard的组合爆炸，这种”让进化自己找到答案”的思想，依然是人工智能和运筹优化领域的重要基石。