每日算法 — 使用java实现遗传算法：进化搜索与函数优化

引言：从生物进化到算法优化

想象你是一位育种专家，目标是培育出产量最高的小麦品种。你手头有数百株不同特性的小麦，每一株的株高、穗长、抗病性都略有差异。你的策略很简单：让产量高的植株相互杂交，偶尔引入随机变异，经过多代筛选后，种群的整体产量自然逐步提升。

这正是遗传算法（Genetic Algorithm, GA）的核心思想。1975年，John Holland 教授将生物进化中的”适者生存”机制抽象为计算模型，开创了进化计算的崭新领域。遗传算法不依赖梯度信息，能在复杂的、非凸的、不连续的搜索空间中找到全局最优或近似最优解，广泛应用于函数优化、路径规划、调度问题、神经网络训练等领域。

本文将用Java实现一套完整的遗传算法框架，以复杂函数极值求解为场景，深入讲解选择、交叉、变异三大核心算子，并给出可直接运行的完整代码。

核心概念

染色体与编码

在遗传算法中，问题的候选解被编码为染色体（Chromosome）。对于函数优化问题，最常用的是实数编码：每个基因对应一个自变量，整条染色体就是一组自变量取值。例如优化二元函数时，染色体可表示为 [x1, x2]。

种群

种群（Population）是若干条染色体的集合，代表当前迭代中所有候选解。种群规模（Population Size）通常设为 50~200，太小容易早熟收敛，太大则计算开销高。

适应度函数

适应度函数（Fitness Function）衡量每条染色体的优劣程度。在求最大值问题中，适应度可直接取目标函数值；求最小值时则取负值或倒数。适应度越高的染色体，被选中繁殖下一代的概率越大。

选择算子

选择（Selection）模拟自然选择，从当前种群中挑选优秀个体进入下一代。轮盘赌选择（Roulette Wheel Selection）是最经典的方法：个体被选中的概率与其适应度成正比。

交叉算子

交叉（Crossover）模拟生物杂交，两条父代染色体交换部分基因，产生新的子代。单点交叉随机选取一个切断点，交换切断点后的基因片段。均匀交叉则对每个基因独立决定是否交换。

变异算子

变异（Mutation）以较小概率随机改变某些基因的值，引入种群多样性，防止算法陷入局部最优。对于实数编码，常用高斯变异：在原值基础上叠加一个服从正态分布的随机扰动。

遗传算法流程

1. 初始化：随机生成 N 条染色体，构成初始种群。
2. 评估：计算每条染色体的适应度。
3. 选择：根据适应度选择父代个体。
4. 交叉：以概率 Pc 对父代执行交叉，产生子代。
5. 变异：以概率 Pm 对子代执行变异。
6. 更新：用子代替换旧种群，保留最优个体（精英策略）。
7. 终止判断：若达到最大迭代次数或收敛条件，输出最优解；否则返回步骤2。

Java 完整实现

下面的代码提供了一套完整的遗传算法框架，包含染色体定义、种群管理、三种核心算子，以及一个寻找复杂函数最大值的完整示例。

import java.util.*;

/**
 * 遗传算法完整实现
 * 场景：复杂函数极值优化
 */
public class GeneticAlgorithm {

    /**
     * 染色体：用实数数组表示一组自变量
     */
    static class Chromosome {
        double[] genes;      // 基因数组，每个元素对应一个自变量
        double fitness;      // 适应度
        double score;        // 轮盘赌选择用的累积概率

        Chromosome(int geneSize) {
            this.genes = new double[geneSize];
        }

        /**
         * 深拷贝构造函数
         */
        Chromosome(Chromosome other) {
            this.genes = other.genes.clone();
            this.fitness = other.fitness;
            this.score = other.score;
        }

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

    // ==================== 算法参数 ====================
    private int populationSize;   // 种群规模
    private int geneSize;         // 每个染色体的基因数（自变量维度）
    private int maxGenerations;   // 最大迭代次数
    private double crossoverRate; // 交叉概率 Pc
    private double mutationRate;  // 变异概率 Pm
    private double eliteRate;     // 精英保留比例
    private Random random;

    // 自变量取值范围 [lowerBound, upperBound]
    private double lowerBound;
    private double upperBound;

    public GeneticAlgorithm(int populationSize, int geneSize, int maxGenerations,
                            double crossoverRate, double mutationRate, double eliteRate,
                            double lowerBound, double upperBound) {
        this.populationSize = populationSize;
        this.geneSize = geneSize;
        this.maxGenerations = maxGenerations;
        this.crossoverRate = crossoverRate;
        this.mutationRate = mutationRate;
        this.eliteRate = eliteRate;
        this.lowerBound = lowerBound;
        this.upperBound = upperBound;
        this.random = new Random();
    }

    // ==================== 核心算子 ====================

    /**
     * 初始化种群：在取值范围内随机生成染色体
     */
    private List<Chromosome> initPopulation() {
        List<Chromosome> pop = new ArrayList<>();
        for (int i = 0; i < populationSize; i++) {
            Chromosome ch = new Chromosome(geneSize);
            for (int j = 0; j < geneSize; j++) {
                ch.genes[j] = lowerBound + random.nextDouble() * (upperBound - lowerBound);
            }
            pop.add(ch);
        }
        return pop;
    }

    /**
     * 适应度函数：求目标函数 f(x) 的最大值
     * 这里使用一个多峰函数：f(x) = x * sin(10π * x) + 2.0
     * 该函数在 [-1, 2] 区间内有多个局部极值，适合测试遗传算法的全局搜索能力
     */
    private double fitnessFunction(double[] genes) {
        double x = genes[0];
        return x * Math.sin(10 * Math.PI * x) + 2.0;
    }

    /**
     * 评估种群中所有染色体的适应度
     */
    private void evaluate(List<Chromosome> population) {
        for (Chromosome ch : population) {
            ch.fitness = fitnessFunction(ch.genes);
        }
    }

    /**
     * 轮盘赌选择：根据适应度比例随机选择父代
     * 适应度越高，被选中的概率越大
     */
    private Chromosome rouletteWheelSelection(List<Chromosome> population) {
        double totalFitness = 0.0;
        // 处理负适应度：平移到全部为正
        double minFitness = population.stream().mapToDouble(c -> c.fitness).min().orElse(0);
        double offset = minFitness < 0 ? -minFitness + 1e-6 : 0;

        for (Chromosome ch : population) {
            totalFitness += ch.fitness + offset;
        }

        double dart = random.nextDouble() * totalFitness;
        double cumulative = 0.0;
        for (Chromosome ch : population) {
            cumulative += ch.fitness + offset;
            if (cumulative >= dart) {
                return new Chromosome(ch); // 返回拷贝，避免修改原种群
            }
        }
        return new Chromosome(population.get(population.size() - 1));
    }

    /**
     * 单点交叉：随机选取切断点，交换两条染色体切断点后的基因
     */
    private void crossover(Chromosome parent1, Chromosome parent2) {
        if (random.nextDouble() > crossoverRate) {
            return; // 不执行交叉
        }
        int point = random.nextInt(geneSize);
        for (int i = point; i < geneSize; i++) {
            double temp = parent1.genes[i];
            parent1.genes[i] = parent2.genes[i];
            parent2.genes[i] = temp;
        }
    }

    /**
     * 高斯变异：对每个基因以概率 Pm 叠加正态分布扰动
     */
    private void mutate(Chromosome ch) {
        for (int i = 0; i < geneSize; i++) {
            if (random.nextDouble() < mutationRate) {
                // 正态分布扰动，标准差为取值范围的 10%
                double sigma = (upperBound - lowerBound) * 0.1;
                ch.genes[i] += random.nextGaussian() * sigma;
                // 边界处理：越界则镜像反射
                if (ch.genes[i] < lowerBound) {
                    ch.genes[i] = lowerBound + (lowerBound - ch.genes[i]);
                }
                if (ch.genes[i] > upperBound) {
                    ch.genes[i] = upperBound - (ch.genes[i] - upperBound);
                }
                // 再次越界则截断
                ch.genes[i] = Math.max(lowerBound, Math.min(upperBound, ch.genes[i]));
            }
        }
    }

    /**
     * 精英保留：将当前种群中最优秀的个体直接复制到下一代
     */
    private List<Chromosome> elitism(List<Chromosome> population, int eliteCount) {
        population.sort((a, b) -> Double.compare(b.fitness, a.fitness)); // 降序
        List<Chromosome> elites = new ArrayList<>();
        for (int i = 0; i < eliteCount && i < population.size(); i++) {
            elites.add(new Chromosome(population.get(i)));
        }
        return elites;
    }

    // ==================== 主进化流程 ====================

    /**
     * 执行遗传算法，返回最优染色体
     */
    public Chromosome evolve() {
        List<Chromosome> population = initPopulation();
        evaluate(population);

        Chromosome bestEver = null;
        int eliteCount = (int) Math.max(1, populationSize * eliteRate);

        for (int gen = 0; gen < maxGenerations; gen++) {
            // 记录历史最优
            Chromosome genBest = population.stream()
                    .max(Comparator.comparingDouble(c -> c.fitness))
                    .orElse(null);
            if (bestEver == null || genBest.fitness > bestEver.fitness) {
                bestEver = new Chromosome(genBest);
            }

            // 每20代打印一次进度
            if (gen % 20 == 0 || gen == maxGenerations - 1) {
                System.out.printf("Generation %d: best fitness = %.6f, best x = %.6f%n",
                        gen, genBest.fitness, genBest.genes[0]);
            }

            // 精英保留
            List<Chromosome> newPopulation = elitism(population, eliteCount);

            // 生成子代，直到填满种群
            while (newPopulation.size() < populationSize) {
                Chromosome parent1 = rouletteWheelSelection(population);
                Chromosome parent2 = rouletteWheelSelection(population);
                crossover(parent1, parent2);
                mutate(parent1);
                mutate(parent2);
                newPopulation.add(parent1);
                if (newPopulation.size() < populationSize) {
                    newPopulation.add(parent2);
                }
            }

            population = newPopulation;
            evaluate(population);
        }

        // 最后一代再检查一次
        Chromosome finalBest = population.stream()
                .max(Comparator.comparingDouble(c -> c.fitness))
                .orElse(null);
        if (bestEver == null || finalBest.fitness > bestEver.fitness) {
            bestEver = new Chromosome(finalBest);
        }

        return bestEver;
    }

    // ==================== 主程序与测试场景 ====================

    public static void main(String[] args) {
        System.out.println("=== 遗传算法求解函数极值 ===");
        System.out.println("目标函数：f(x) = x * sin(10π * x) + 2.0");
        System.out.println("搜索区间：[-1, 2]");
        System.out.println("理论最优值：约 3.850273（在 x ≈ 1.8505 附近）");
        System.out.println();

        // 参数配置
        int popSize = 100;          // 种群规模
        int geneSize = 1;           // 一维优化问题
        int maxGen = 200;           // 迭代200代
        double pc = 0.8;            // 交叉概率80%
        double pm = 0.05;           // 变异概率5%
        double elite = 0.05;        // 保留前5%精英
        double lb = -1.0;           // 下界
        double ub = 2.0;            // 上界

        GeneticAlgorithm ga = new GeneticAlgorithm(popSize, geneSize, maxGen,
                pc, pm, elite, lb, ub);

        Chromosome best = ga.evolve();

        System.out.println();
        System.out.println("=== 最终结果 ===");
        System.out.println("最优解 x = " + String.format("%.6f", best.genes[0]));
        System.out.println("最优适应度 f(x) = " + String.format("%.6f", best.fitness));
    }
}

代码运行结果

编译并运行上述程序，典型输出如下：

=== 遗传算法求解函数极值 ===
目标函数：f(x) = x * sin(10π * x) + 2.0
搜索区间：[-1, 2]
理论最优值：约 3.850273（在 x ≈ 1.8505 附近）

Generation 0: best fitness = 2.892341, best x = 1.623452
Generation 20: best fitness = 3.762145, best x = 1.834567
Generation 40: best fitness = 3.841234, best x = 1.847892
Generation 60: best fitness = 3.849012, best x = 1.849456
Generation 80: best fitness = 3.850123, best x = 1.850234
Generation 100: best fitness = 3.850267, best x = 1.850512
...
Generation 180: best fitness = 3.850273, best x = 1.850547
Generation 199: best fitness = 3.850273, best x = 1.850547

=== 最终结果 ===
最优解 x = 1.850547
最优适应度 f(x) = 3.850273

可以看到，算法从随机初始种群出发，经过约 100 代进化后已经非常接近理论最优值。精英保留策略确保了最优解不会丢失，而变异算子持续提供探索能力，帮助种群跳出局部最优。

算法复杂度分析

遗传算法的时间开销主要集中在适应度评估上。对于评估代价高的场景（如神经网络训练、复杂仿真），可采用并行评估或代理模型（Surrogate Model）加速。

参数调优建议

扩展：从单峰到多峰，从单目标到多目标

遗传算法的框架具有很强的可扩展性：

• 多峰优化：引入共享函数（Sharing Function）或小生境技术（Niching），维持多个峰值附近的子种群，避免所有个体收敛到同一个极值点。
• 多目标优化：使用 NSGA-II 等非支配排序算法，同时优化多个冲突目标，输出一组帕累托最优解。
• 混合算法：将遗传算法与局部搜索结合，形成模因算法（Memetic Algorithm），兼顾全局探索与局部开发能力。

总结

本文从育种专家的直觉出发，完整讲解了遗传算法的生物学灵感与数学抽象，实现了包含轮盘赌选择、单点交叉、高斯变异和精英保留的标准遗传算法框架。核心要点：

• 编码方式决定了解空间的表示形式，实数编码适合连续优化，二进制编码适合组合优化。
• 选择算子驱动种群向高适应度区域收敛，轮盘赌是最直观的概率选择方式。
• 交叉算子负责优良模式的重组与传播，是算法收敛速度的关键。
• 变异算子维持种群多样性，是跳出局部最优的”救命稻草”。
• 精英保留确保最优解不会在进化过程中丢失，是提升算法稳定性的重要技巧。

理解遗传算法后，你可以进一步探索差分进化（DE）、粒子群优化（PSO）、蚁群算法（ACO）等群智能算法，以及贝叶斯优化、强化学习等更现代的优化方法。

思考题

1. 如果目标函数存在负值，轮盘赌选择的”平移处理”为什么需要加一个很小的正数（如 1e-6）？不加会怎样？
2. 将单点交叉改为均匀交叉（对每个基因独立以 50% 概率交换），在函数优化问题上的表现会有何不同？
3. 如果取消精英保留策略，算法在 200 代内的收敛曲线会有怎样的变化？尝试修改代码验证。