本文共 11016 字，大约阅读时间需要 36 分钟。
本节书摘来异步社区《Java遗传算法编程》一书中的第2章，第2.8节，作者： 【英】Lee Jacobson（雅各布森） , 【美】Burak Kanber（坎贝尔），更多章节内容可以访问云栖社区“异步社区”公众号查看。
为了实现轮盘赌选择，在GeneticAlgorithm类的任意位置增加一个selectParent( )方法。
public Individual selectParent(Population population) { // Get individuals Individual individuals[] = population.getIndividuals(); // Spin roulette wheel double populationFitness = population.getPopulationFitness(); double rouletteWheelPosition = Math.random() * populationFitness; // Find parent double spinWheel = 0; for (Individual individual : individuals) { spinWheel += individual.getFitness(); if (spinWheel >= rouletteWheelPosition) { return individual; } } return individuals[population.size() - 1];} selectParent( )方法基本上是反着玩轮盘赌。在赌场，轮盘上已经有标记，然后旋转的轮盘，等待球落入位置。但在这里，我们先选择一个随机位置，然后反向工作，弄清楚哪个个体位于该位置。在算法上，这样更容易实现。选择一个介于0和种群总适应度的随机数，然后逐个检查每个个体，同时累加它们的适应度值，直到达到起初选择的随机位置。
既然已经添加了选择方法，下一步就是创建一个交叉方法，利用这个selectParent()方法来选择交叉伙伴。首先，将下面的交叉方法添加到GeneticAlgorithm类。
public Population crossoverPopulation(Population population) { // Create new population Population newPopulation = new Population(population.size()); // Loop over current population by fitness for (int populationIndex = 0; populationIndex < population.size(); populationIndex++) { Individual parent1 = population.getFittest(populationIndex); // Apply crossover to this individual? if (this.crossoverRate > Math.random() && populationIndex > this.elitismCount) { // Initialize offspring Individual offspring = new Individual(parent1. getChromosomeLength()); // Find second parent Individual parent2 = selectParent(population); // Loop over genome for (int geneIndex = 0; geneIndex < parent1. getChromosomeLength(); geneIndex++) { // Use half of parent1's genes and half of parent2's genes if (0.5 > Math.random()) { offspring.setGene(geneIndex, parent1.getGene(geneIndex)); } else { offspring.setGene(geneIndex, parent2.getGene(geneIndex)); } } // Add offspring to new population newPopulation.setIndividual(populationIndex, offspring); } else { // Add individual to new population without applying crossover newPopulation.setIndividual (populationIndex, parent1); } } return newPopulation;} 在crossoverPopulation()方法的第一行，为下一代创建一个新的空种群。接下来，遍历种群，利用交叉率来考虑每个个体的交叉（这里还有一个神秘的术语“精英主义”，我们将在下一节讨论）。如果个体不经过交叉，它就直接加入下一个种群，否则就创建一个新个体。后代染色体的填充方法是遍历亲代染色体，随机从每个亲代选择基因，加入后代的染色体。针对种群的每个个体完成这个交叉过程后，交叉方法返回下一代的种群。
至此，我们可在以AllOnesGA类的main方法中，实现交叉的功能。整个AllOnesGA类和main方法打印如下，但和以前比，唯一的变化是在“Apply crossover”注释下面，加入一行crossoverPopulation()调用。
package chapter2;public class AllOnesGA { public static void main(String[] args) { // Create GA object GeneticAlgorithm ga = new GeneticAlgorithm(100, 0.001, 0.95, 0); // Initialize population Population population = ga.initPopulation(50); // Evaluate population ga.evalPopulation(population); // Keep track of current generation int generation = 1; while (ga.isTerminationConditionMet(population) == false) { // Print fittest individual from population System.out.println("Best solution: " + population. getFittest(0).toString()); // Apply crossover population = ga.crossoverPopulation(population); // Apply mutation // TODO // Evaluate population ga.evalPopulation(population); // Increment the current generation generation++; } System.out.println("Found solution in " + generation + " generations"); System.out.println("Best solution: " + population. getFittest(0).toString()); }} 现在，运行程序应该能工作，并返回一个有效的解！你可以尝试一下，点击Eclipse中的Run按钮，观察控制台中的结果。
正如你所看到的，单独的交叉足以进化种群。然而，如果没有变异，遗传算法很容易陷入局部最优而不能找到全局最优。在这样简单的问题中，我们不会看到这种现象，但在更复杂的问题领域，我们需要某种机制，将一个种群推离局部最优，试试看是否有其他更好的解。这就是变异的随机性发挥作用的地方：如果一个解停滞在局部最优，随机事件可能将它踢向正确的方向，让它朝着更好的解前进。
在讨论变异之前，先来看看我们在交叉方法中引入的elitismCount参数。
由于交叉和变异算子的效果，基本遗传算法往往会在世代之间失去种群中最好的个体。然而，我们需要这些算子来找到更好的解。要在实战中看到这个问题，只需编辑遗传算法的代码，针对每一代打印出最适应个体的适应度。你会发现，尽管它通常会增长，有时候在交叉和变异时最优解会丢失，代之以非最优解。
解决这个问题的一个简单的优化技术，就是始终让最适合的个体不作改变，添加到下一代的种群中。这样，最优个体不会在世代之间丢失。虽然这些个体没有进行交叉操作，但它们仍会被选为另一个个体的亲代，让它们的遗传信息仍然可以和种群中的其他个体分享。将最优解保留到下一代的过程称为“精英主义”。通常情况下，群体中“精英”个体的最佳数目只占种群总规模的很小一部分。原因是如果该值太高，就会减缓遗传算法搜索过程，因为保留太多个体导致缺乏遗传多样性。和以前讨论的其他参数类似，为最佳表现找到一种平衡，这是非常重要的。
实现精英主义在交叉和变异中都很简单。让我们重新检查crossover Population( )，看看是否应该应用交叉：
// Apply crossover to this individual?if (this.crossoverRate > Math.random() && populationIndex >= this.elitismCount) { // ...} 仅当交叉条件满足且个体不是精英，才交叉。
个体如何才算精英？此时，种群中的个体已经按它们的适应度排序，因此最强大的个体索引值最小。因此，如果我们需要3个精英个体，应该跳过索引0～2。这将保留最强大的个体，让它们保持不变，传递到下一代。在接下来的变异代码中，我们将使用完全相同的条件。
要完成进化过程，最后要添加的是变异。像交叉一样，有许多不同的变异方法可供选择。如果使用二进制串，一种比较常见的方法是所谓的“位翻转”变异。你可能已经猜到，位翻转变异就是根据位的初始值，将它从1翻转为0，或从0翻转到1。如果染色体使用另外某种形式编码，通常会采用不同的变异方法，以便更好地利用这种编码。
在选择变异和交叉方法时，有一点非常重要，即确保你选择的方法仍然得到一个有效解。我们将后续章节中看到这一概念的实战，但对于这个问题，我们只需要确保基因变异只能产生0和1。例如，基因变异为7将给出一个无效的解。
在本章中，这个建议似乎没有实际意义，而且过于明显，但请考虑另一个简单的问题，如果你需要不重复地从1到6排序（即得到“123456”）。变异算法如果简单地选择1到6之间的随机数，可能产生“126456”，使用“6”两次，这将是一个无效的解，因为每个数字只能用一次。正如你所看到的，即使简单的问题，有时也需要复杂的技术。
与交叉类似，变异基于变异率应用于个体。如果变异率设定为0.1，那么每个基因在变异阶段发生变异的机会是10％。
让我们继续，为GeneticAlgorithm类添加变异的功能。可以将它添加到任何位置：
public Population mutatePopulation(Population population) { // Initialize new population Population newPopulation = new Population(this.populationSize); // Loop over current population by fitness for (int populationIndex = 0; populationIndex < population.size(); populationIndex++) { Individual individual = population. getFittest(populationIndex); // Loop over individual's genes for (int geneIndex = 0; geneIndex < individual. getChromosomeLength(); geneIndex++) { // Skip mutation if this is an elite individual if (populationIndex >= this.elitismCount) { // Does this gene need mutation? if (this.mutationRate > Math.random()) { // Get new gene int newGene = 1; if (individual.getGene(geneIndex) == 1) { newGene = 0; } // Mutate gene individual.setGene(geneIndex, newGene); } } } // Add individual to population newPopulation.setIndividual(populationIndex, individual); } // Return mutated population return newPopulation;} mutatePopulation( )方法开始为变异的个体创建一个新的空种群，然后开始遍历当前种群。然后，遍历每个个体的染色体，基于变异率，考虑每个基因是否进行位翻转变异。个体的整个染色体遍历完成后，该个体就被加入新的变异种群。所有的个体都通过变异过程后，返回该变异种群。
现在，我们可以完成进化循环的最后一步，将变异功能加到main方法。完成的main方法如下。与前面相比有两处不同：首先，我们在“Apply mutation”注释的下面添加了mutatePopulation()调用。此外，既然已经明白了精英主义的工作原理，我们在new GeneticAlgorithm构造方法中，将elitismCount参数从0改为2。
package chapter2;public class AllOnesGA { public static void main(String[] args) { // Create GA object GeneticAlgorithm ga = new GeneticAlgorithm(100, 0.001, 0.95, 2); // Initialize population Population population = ga.initPopulation(50); // Evaluate population ga.evalPopulation(population); // Keep track of current generation int generation = 1; while (ga.isTerminationConditionMet(population) == false) { // Print fittest individual from population System.out.println("Best solution: " + population. getFittest(0).toString()); // Apply crossover population = ga.crossoverPopulation(population); // Apply mutation population = ga.mutatePopulation(population); // Evaluate population ga.evalPopulation(population); // Increment the current generation generation++; } System.out.println("Found solution in " + generation + " generations"); System.out.println("Best solution: " + population. getFittest(0).toString()); }} 现在，你已经完成了第一个遗传算法。Individual和Population类在本章前面已经完全打印，你的这些类应该看起来就像上面一样。最后的AllOnesGA执行类（引导和运行算法的类）直接在上面提供。
GeneticAlgorithm类相当长，你一块一块地创建了它，所以此时，请检查是否已经实现了以下属性和方法。为了节省篇幅，这里省略了所有的注释和方法体（我只是显示了类的折叠视图），但要确保你的类有这些方法，像前面介绍的一样实现。
package chapter2;public class GeneticAlgorithm { private int populationSize; private double mutationRate; private double crossoverRate; private int elitismCount; public GeneticAlgorithm(int populationSize, double mutationRate, double crossoverRate, int elitismCount) { } public Population initPopulation(int chromosomeLength) { } public double calcFitness(Individual individual) { } public void evalPopulation(Population population) { } public boolean isTerminationConditionMet(Population population) { } public Individual selectParent(Population population) { } public Population crossoverPopulation(Population population) { } public Population mutatePopulation(Population population) { }} 如果你使用Eclipse IDE，现在可以运行该算法，打开AllOnesGA文件，然后点击“Run”按钮，该按钮通常在IDE的顶部菜单中。
在运行时，该算法将信息打印到控制台，点击Run时，控制台会自动出现在Eclipse中。因为每一个遗传算法的随机性，每次运行看起来有点不同，但输出看起来可能如下所示：
Best solution: 11001110100110111111010111001001100111110011111111Best solution: 11001110100110111111010111001001100111110011111111Best solution: 11001110100110111111010111001001100111110011111111[ ... Lots of lines omitted here ... ]Best solution: 11111111111111111111111111111011111111111111111111Best solution: 11111111111111111111111111111011111111111111111111Found solution in 113 generationsBest solution: 11111111111111111111111111111111111111111111111111
此时，你应该尝试给GeneticAlgorithm构造方法提供不同的参数：populationSize、mutationRate、crossoverRate和elitismCount。不要忘记，统计决定了遗传算法的表现，所以不能通过运行一次来评价一个算法或一种设置的表现：每种不同的设置至少要尝试10次，才能判断其表现。
转载地址：http://trdvl.baihongyu.com/