用java写一个遗传算法的列子

以下是一个基本的遗传算法示例，用Java编写，用于解决TSP问题（旅行商问题）。

1.定义染色体

首先，我们需要定义一个染色体类，该类将包含一组基因，每个基因代表一个城市，并存储该基因的适应度。

public class Chromosome { private int[] genes; private double fitness;

public Chromosome(int[] genes) {
    this.genes = genes;
}

public double getFitness() {
    return fitness;
}

public void setFitness(double fitness) {
    this.fitness = fitness;
}

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

public int getGene(int index) {
    return genes[index];
}

public void setGene(int index, int value) {
    genes[index] = value;
}

public int size() {
    return genes.length;
}

}

2.初始化种群

接下来，我们需要生成一组随机的染色体，作为初始种群。

public class Population { private Chromosome[] chromosomes;

public Population(int size, boolean initialize) {
    chromosomes = new Chromosome[size];
    if (initialize) {
        for (int i = 0; i < size; i++) {
            int[] genes = new int[Main.CITIES.length];
            for (int j = 0; j < genes.length; j++) {
                genes[j] = j;
            }
            shuffle(genes);
            chromosomes[i] = new Chromosome(genes);
        }
    }
}

private void shuffle(int[] array) {
    Random random = new Random();
    for (int i = array.length - 1; i > 0; i--) {
        int index = random.nextInt(i + 1);
        int temp = array[index];
        array[index] = array[i];
        array[i] = temp;
    }
}

public Chromosome getChromosome(int index) {
    return chromosomes[index];
}

public Chromosome getFittest() {
    Chromosome fittest = chromosomes[0];
    for (int i = 1; i < size(); i++) {
        if (chromosomes[i].getFitness() > fittest.getFitness()) {
            fittest = chromosomes[i];
        }
    }
    return fittest;
}

public int size() {
    return chromosomes.length;
}

public void setChromosome(int index, Chromosome chromosome) {
    chromosomes[index] = chromosome;
}

}

3.计算适应度

接下来，我们需要编写一个函数来计算每个染色体的适应度。在TSP问题中，适应度是路径的长度，我们将尽量缩短路径。

public static double calcFitness(Chromosome chromosome) { int[] genes = chromosome.getGenes(); double distance = 0; for (int i = 0; i < genes.length - 1; i++) { int city1Index = genes[i]; int city2Index = genes[i + 1]; City city1 = CITIES[city1Index]; City city2 = CITIES[city2Index]; distance += city1.distanceTo(city2); } int lastIndex = genes[genes.length - 1]; int firstIndex = genes[0]; City lastCity = CITIES[lastIndex]; City firstCity = CITIES[firstIndex]; distance += lastCity.distanceTo(firstCity); double fitness = 1 / distance; chromosome.setFitness(fitness); return fitness; }

4.选择操作

接下来，我们需要编写一个函数来选择两个染色体进行交叉。在这个例子中，我们使用轮盘赌选择法，即每个染色体的选择概率与其适应度成正比。

public static Chromosome selectParent(Population population) { double totalFitness = 0; for (int i = 0; i < population.size(); i++) { totalFitness += population.getChromosome(i).getFitness(); } double randomFitness = Math.random() * totalFitness; double cumulativeFitness = 0; for (int i = 0; i < population.size(); i++) { Chromosome chromosome = population.getChromosome(i); cumulativeFitness += chromosome.getFitness(); if (cumulativeFitness > randomFitness) { return chromosome; } } return null; }

5.交叉操作

接下来，我们需要编写一个函数来交叉两个染色体，生成两个新的染色体。

public static Chromosome[] crossover(Chromosome parent1, Chromosome parent2) { int size = parent1.size(); int[] child1Genes = new int[size]; int[] child2Genes = new int[size]; int startPos = (int) (Math.random() * size); int endPos = (int) (Math.random() * size); if (startPos > endPos) { int temp = startPos; startPos = endPos; endPos = temp; } for (int i = startPos; i <= endPos; i++) { child1Genes[i] = parent2.getGene(i); child2Genes[i] = parent1.getGene(i); } int index1 = endPos + 1; int index2 = endPos + 1; while (index1 != startPos) { if (!contains(child1Genes, parent1.getGene(index1))) { child1Genes[index2] = parent1.getGene(index1); index2++; if (index2 == size) { index2 = 0; } } index1++; if (index1 == size) { index1 = 0; } } index1 = endPos + 1; index2 = endPos + 1; while (index1 != startPos) { if (!contains(child2Genes, parent2.getGene(index1))) { child2Genes[index2] = parent2.getGene(index1); index2++; if (index2 == size) { index2 = 0; } } index1++; if (index1 == size) { index1 = 0; } } Chromosome child1 = new Chromosome(child1Genes); Chromosome child2 = new Chromosome(child2Genes); return new Chromosome[] { child1, child2 }; }

private static boolean contains(int[] array, int value) { for (int i = 0; i < array.length; i++) { if (array[i] == value) { return true; } } return false; }

6.变异操作

最后，我们需要编写一个函数来对染色体进行变异，即随机交换两个基因的位置。

public static void mutate(Chromosome chromosome) { for (int i = 0; i < chromosome.size(); i++) { if (Math.random() < Main.MUTATION_RATE) { int j = (int) (Math.random() * chromosome.size()); int temp = chromosome.getGene(i); chromosome.setGene(i, chromosome.getGene(j)); chromosome.setGene(j, temp); } } }

7.主函数

现在，我们可以编写主函数来运行遗传算法并解决TSP问题。

public static void main(String[] args) { Population population = new Population(POPULATION_SIZE, true); int generationCount = 0; while (generationCount < MAX_GENERATIONS) { Chromosome parent1 = selectParent(population); Chromosome parent2 = selectParent(population); Chromosome[] children = crossover(parent1, parent2); mutate(children[0]); mutate(children[1]); calcFitness(children[0]); calcFitness(children[1]); Chromosome leastFittest = population.getFittest(); if (children[0].getFitness() > leastFittest.getFitness()) { population.setChromosome(population.indexOf(leastFittest), children[0]); } else if (children[1].getFitness() > leastFittest.getFitness()) { population.setChromosome(population.indexOf(leastFittest), children[1]); } generationCount++; } Chromosome fittest = population.getFittest(); System.out.println("Final distance: " + (1 / fittest.getFitness())); }

这个遗传算法例子可以帮助您理解遗传算法的基本原理和实现。您可以将其扩展到其他问题和应用程序中。