本节书摘来异步社区《Java遗传算法编程》一书中的第2章，第2.8节，作者： 【英】Lee Jacobson（雅各布森） , 【美】Burak Kanber（坎贝尔），更多章节内容可以访问云栖社区“异步社区”公众号查看。
2.8 交叉实现
为了实现轮盘赌选择，在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按钮，观察控制台中的结果。
正如你所看到的，单独的交叉足以进化种群。然而，如果没有变异，遗传算法很容易陷入局部最优而不能找到全局最优。在这样简单的问题中，我们不会看到这种现象，但在更复杂的问题领域，我们需要某种机制，将一个种群推离局部最优，试试看是否有其他更好的解。这就是变异的随机性发挥作用的地方：如果一个解停滞在局部最优，随机事件可能将它踢向正确的方向，让它朝着更好的解前进。
2.8.1 精英主义
在讨论变异之前，先来看看我们在交叉方法中引入的elitismCount参数。
由于交叉和变异算子的效果，基本遗传算法往往会在世代之间失去种群中最好的个体。然而，我们需要这些算子来找到更好的解。要在实战中看到这个问题，只需编辑遗传算法的代码，针对每一代打印出最适应个体的适应度。你会发现，尽管它通常会增长，有时候在交叉和变异时最优解会丢失，代之以非最优解。
解决这个问题的一个简单的优化技术，就是始终让最适合的个体不作改变，添加到下一代的种群中。这样，最优个体不会在世代之间丢失。虽然这些个体没有进行交叉操作，但它们仍会被选为另一个个体的亲代，让它们的遗传信息仍然可以和种群中的其他个体分享。将最优解保留到下一代的过程称为“精英主义”。
通常情况下，群体中“精英”个体的最佳数目只占种群总规模的很小一部分。原因是如果该值太高，就会减缓遗传算法搜索过程，因为保留太多个体导致缺乏遗传多样性。和以前讨论的其他参数类似，为最佳表现找到一种平衡，这是非常重要的。
实现精英主义在交叉和变异中都很简单。让我们重新检查crossover Population( )，看看是否应该应用交叉：
// Apply crossover to this individual?
if (this.crossoverRate > Math.random() && populationIndex >= this.
elitismCount) {
// ...
}仅当交叉条件满足且个体不是精英，才交叉。
个体如何才算精英？此时，种群中的个体已经按它们的适应度排序，因此最强大的个体索引值最小。因此，如果我们需要3个精英个体，应该跳过索引0～2。这将保留最强大的个体，让它们保持不变，传递到下一代。在接下来的变异代码中，我们将使用完全相同的条件。
2.8.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());
}
}2.8.3 执行
现在，你已经完成了第一个遗传算法。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: 11001110100110111111010111001001100111110011111111
Best solution: 11001110100110111111010111001001100111110011111111
Best solution: 11001110100110111111010111001001100111110011111111
[ ... Lots of lines omitted here ... ]
Best solution: 11111111111111111111111111111011111111111111111111
Best solution: 11111111111111111111111111111011111111111111111111
Found solution in 113 generations
Best solution: 11111111111111111111111111111111111111111111111111此时，你应该尝试给GeneticAlgorithm构造方法提供不同的参数：populationSize、mutationRate、crossoverRate和elitismCount。不要忘记，统计决定了遗传算法的表现，所以不能通过运行一次来评价一个算法或一种设置的表现：每种不同的设置至少要尝试10次，才能判断其表现。
