3.7 遗传算法

遗传算法（Genetic Algorithm，GA）是一种模拟自然选择和遗传机制的优化算法。它是受达尔文的进化论启发而发展起来的一种启发式搜索技术。遗传算法通过模拟自然界中的遗传、交叉、变异等过程，以一种群体的方式寻找到解决问题的优质解。

在遗传算法中，问题的解被编码成染色体（Chromosome）或基因（Gene），这些编码通常是一串数字、字符串或其他数据结构。这些染色体组成了种群（Population）。遗传算法主要通过以下步骤来优化问题的解：

1. 初始化种群：随机生成一组初始解作为种群的起始点。

2. 适应度评估：计算每个个体（解）的适应度（Fitness），即解的优劣程度。

3. 选择：根据个体的适应度，选择一部分个体作为父代，用于产生下一代解。

4. 交叉：从父代中选择一对个体，通过染色体交叉产生新的个体（子代）。

5. 变异：对新个体进行变异操作，以增加种群的多样性。

6. 更新种群：根据选择、交叉和变异的结果，更新种群。

7. 重复迭代：重复执行上述步骤，直到达到停止条件（例如达到最大迭代次数或找到满意的解）。

通过不断迭代优化种群，遗传算法能够逐步改进解的质量，最终找到或接近最优解。

遗传算法适用于解决许多不同类型的优化问题，例如函数优化、组合优化、排课问题等。它的优势在于能够处理高维度、非线性、多模态等复杂问题，并且不需要问题的导数信息。

这个示例中，我们尝试最小化一个简单的函数 f(x) = x^2，其中 x 是一个二进制编码的数字。基因的长度为 5，代表可能的 x 的范围是 0 到 31。

以下是一个简单的遗传算法的Java代码示例，用于解决一个简单的优化问题，比如寻找函数的最小值：

import java.util.Random;

public class GeneticAlgorithm {
    private static final int POPULATION_SIZE = 10;
    private static final int NUM_GENERATIONS = 100;
    private static final double MUTATION_RATE = 0.1;

    public static void main(String[] args) {
        // 初始化种群
        Population population = new Population(POPULATION_SIZE);
        population.initialize();

        for (int i = 0; i < NUM_GENERATIONS; i++) {
            // 计算适应度
            population.calculateFitness();

            // 选择父代
            Population newPopulation = new Population(POPULATION_SIZE);
            for (int j = 0; j < POPULATION_SIZE; j++) {
                Individual parent1 = population.selectParent();
                Individual parent2 = population.selectParent();
                Individual child = parent1.crossover(parent2);
                newPopulation.saveIndividual(j, child);
            }

            // 变异
            for (int j = 0; j < POPULATION_SIZE; j++) {
                if (Math.random() < MUTATION_RATE) {
                    newPopulation.getIndividual(j).mutate();
                }
            }

            // 更新种群
            population = newPopulation;
        }

        // 打印结果
        population.calculateFitness();
        System.out.println("Best solution: " + population.getFittest());
    }
}

class Individual {
    private int[] genes;
    private double fitness;

    public Individual(int geneLength) {
        genes = new int[geneLength];
        fitness = 0;
        initializeGenes();
    }

    public void initializeGenes() {
        Random rand = new Random();
        for (int i = 0; i < genes.length; i++) {
            genes[i] = rand.nextInt(2); // 0或1
        }
    }

    public double calculateFitness() {
        // 这里以一个简单的例子为参考，比如最小化函数 f(x) = x^2，fitness = 1 / (1 + f(x))
        int x = 0;
        for (int i = 0; i < genes.length; i++) {
            x += genes[i] * Math.pow(2, i);
        }
        fitness = 1 / (1 + Math.pow(x, 2));
        return fitness;
    }

    public void mutate() {
        Random rand = new Random();
        int index = rand.nextInt(genes.length);
        genes[index] = (genes[index] == 0) ? 1 : 0; // 变异，0变为1，1变为0
    }

    public int[] getGenes() {
        return genes;
    }

    public double getFitness() {
        return fitness;
    }
}

class Population {
    private Individual[] individuals;

    public Population(int populationSize) {
        individuals = new Individual[populationSize];
    }

    public void initialize() {
        for (int i = 0; i < individuals.length; i++) {
            individuals[i] = new Individual(5); // 5是基因长度
        }
    }

    public void calculateFitness() {
        for (Individual individual : individuals) {
            individual.calculateFitness();
        }
    }

    public Individual selectParent() {
        Random rand = new Random();
        double totalFitness = 0;
        for (Individual individual : individuals) {
            totalFitness += individual.getFitness();
        }
        double randomNum = rand.nextDouble() * totalFitness;
        double sum = 0;
        for (Individual individual : individuals) {
            sum += individual.getFitness();
            if (sum >= randomNum) {
                return individual;
            }
        }
        return individuals[individuals.length - 1];
    }

    public Individual getFittest() {
        Individual fittest = individuals[0];
        for (int i = 1; i < individuals.length; i++) {
            if (individuals[i].getFitness() > fittest.getFitness()) {
                fittest = individuals[i];
            }
        }
        return fittest;
    }

    public Individual getIndividual(int index) {
        return individuals[index];
    }

    public void saveIndividual(int index, Individual individual) {
        individuals[index] = individual;
    }
}