2.4 基本实现
为了消除所有不必要的细节，保持最初的实现容易尝试，本书中介绍的第一个遗传算法将是简单的二进制遗传算法。
二进制遗传算法比较容易实现，对于解决许多种优化问题，它可能是非常有效的工具。你可能还记得第1章提到，二进制遗传算法是由Holland（1975）提出的原创的遗传算法。
2.4.1 问题
首先，让我们回顾一下“全一”问题，它是可以用二进制遗传算法来解决的一个非常基本的问题。
该问题不是很有趣，但作为一个简单的问题，它的作用是强调所涉及的基本技术。顾名思义，该问题就是发现全部由1构成的字符串。因此，对于长度为5的字符串，最优解是“11111”。
2.4.2 参数
既然有了要解决的问题，让我们继续研究实现。我们要做的第一件事就是建立遗传算法参数。如前所述，这3个主要参数是种群规模、变异率和交叉率。本章中，我们还引入了一个名为“精英主义（elitism）”的概念，并将它作为遗传算法的参数之一。
首先，创建一个名为GeneticAlgorithm的类。如果你使用Eclipse，可以通过选择File New Class来做到这一点。在本书中，我们选择用对应的章名来命名包，所以我们会在包“Chapter2”中工作。
这个GeneticAlgorithm类将包含遗传算法本身的操作所需的方法和变量。例如，这个类包括处理交叉、变异、适应度评估和终止条件检查的逻辑。该类创建后，添加一个构造方法，它接受4个参数：种群规模、变异率、交叉率和精英成员数。
package chapter2;
/**
* Lots of comments in the source that are omitted here!
*/
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) {
this.populationSize = populationSize;
this.mutationRate = mutationRate;
this.crossoverRate = crossoverRate;
this.elitismCount = elitismCount;
}
/**
* Many more methods implemented later...
*/
}
传入所需的参数，这个构造方法将利用所需的配置，创建GeneticAlgorithm类的新实例。
现在，我们应该创建引导类：回想一下，每章都需要一个引导类，用于初始化遗传算法，并作为应用程序的起点。将该类命名为“AllOnesGA”，并定义一个main方法：
package chapter2;
public class AllOnesGA {
public static void main(String[] args) {
// Create GA object
GeneticAlgorithm ga = new GeneticAlgorithm(100, 0.01, 0.95, 0);
// We’ll add a lot more here...
}
}
暂时，我们就用一些典型的参数值：种群规模=100，变异率=0.01，交叉率=0.95，精英计数为 0（实际上暂且禁用它）。在本章结束，当你已完成了以上的内容时，可以尝试更改这些参数，看看它们如何影响算法的表现。
2.4.3 初始化
下一步就是初始化一个潜在解构成的种群。这通常是随机的，但偶尔也可能采用系统化的方法会更好，可以利用对搜索空间的已知信息来初始化种群。在这个例子中，种群中每个个体将随机初始化。我们可以为染色体的每个基因随机选择1或0，实现这一点。
初始化种群之前，我们需要创建两个类，一个管理并创建种群，另一个管理和创建种群的个体。这此类包含一些方法，例如获取个体适应度，或在种群中取得最适应的个体。
首先，让我们从创建Individual类开始。请注意，为了节省篇幅，我们省略了所有注释和方法的文档注释块！你可以在附带的Eclipse项目中找到该类的完全注释版本。
package chapter2;
public class Individual {
private int[] chromosome;
private double fitness = -1;
public Individual(int[] chromosome) {
// Create individual chromosome
this.chromosome = chromosome;
}
public Individual(int chromosomeLength) {
this.chromosome = new int[chromosomeLength];
for (int gene = 0; gene < chromosomeLength; gene++) {
if (0.5 < Math.random()) {
this.setGene(gene, 1);
} else {
this.setGene(gene, 0);
}
}
}
public int[] getChromosome() {
return this.chromosome;
}
public int getChromosomeLength() {
return this.chromosome.length;
}
public void setGene(int offset, int gene) {
this.chromosome[offset] = gene;
}
public int getGene(int offset) {
return this.chromosome[offset];
}
public void setFitness(double fitness) {
this.fitness = fitness;
}
public double getFitness() {
return this.fitness;
}
public String toString() {
String output = "";
for (int gene = 0; gene < this.chromosome.length; gene++) {
output += this.chromosome[gene];
}
return output;
}
}
Individual类代表一个候选解，主要负责存储和操作一条染色体。请注意，Individual类也有两个构造方法。一个构造方法接受一个整数（代表染色体的长度），在初始化对象时将创建一条随机的染色体。另一个构造方法接受一个整数数组，用它作为染色体。
除了管理Individual的染色体，它也追踪个体的适应度值，也知道如何将自己打印为一个字符串。
下一步骤是创建Population类，它提供管理群体中一组个体所需的功能。
像往常一样，注释和文档注释块在这一章中已经省略了，一定要看看Eclipse项目，了解更多背景！
package chapter2;
import java.util.Arrays;
import java.util.Comparator;
public class Population {
private Individual population[];
private double populationFitness = -1;
public Population(int populationSize) {
this.population = new Individual[populationSize];
}
public Population(int populationSize, int chromosomeLength) {
this.population = new Individual[populationSize];
for (int individualCount = 0; individualCount <
populationSize; individualCount++) {
Individual individual = new
Individual(chromosomeLength);
this.population[individualCount] = individual;
}
}
public Individual[] getIndividuals() {
return this.population;
}
public Individual getFittest(int offset) {
Arrays.sort(this.population, new Comparator<Individual>() {
@Override
public int compare(Individual o1, Individual o2) {
if (o1.getFitness() > o2.getFitness()) {
return -1;
} else if (o1.getFitness() < o2.getFitness()) {
return 1;
}
return 0;
}
});
return this.population[offset];
}
public void setPopulationFitness(double fitness) {
this.populationFitness = fitness;
}
public double getPopulationFitness() {
return this.populationFitness;
}
public int size() {
return this.population.length;
}
public Individual setIndividual(int offset, Individual individual) {
return population[offset] = individual;
}
public Individual getIndividual(int offset) {
return population[offset];
}
public void shuffle() {
Random rnd = new Random();
for (int i = population.length - 1; i > 0; i--) {
int index = rnd.nextInt(i + 1);
Individual a = population[index];
population[index] = population[i];
population[i] = a;
}
}
}
Population类相当简单，它的主要功能是保存由个体构成的一个数组，能够通过类方法方便地访问。例如getFittest()和setIndividual()这样的方法，能够访问并更新种群中的个体。除了保存个体，它也存储了种群的总体适应度，在稍后实现选择方法时，这很重要。
既然我们有了种群和个体类，就可以在GeneticAlgorithm类中将它们实例化。要做到这一点，只需创建一个名为“initPopulation”方法，放在GeneticAlgorithm类中的任意位置。
public class GeneticAlgorithm {
/**
* The constructor we created earlier is up here...
*/
public Population initPopulation(int chromosomeLength) {
Population population = new Population(this.populationSize,
chromosomeLength);
return population;
}
/**
* We still have lots of methods to implement down here...
*/
}
既然有了Population和Individual类，我们就可以回到AllOnesGA类，开始使用initPopulation方法。回想一下，AllOnesGA类只有一个main方法，而且它代表本章前面介绍的伪代码。
在main方法中初始化种群时，还需要指定个体染色体的长度，这里，我们取长度为50：
public class AllOnesGA {
public static void main(String[] args){
// Create GA object
GeneticAlgorithm ga = new GeneticAlgorithm(100, 0.01, 0.95, 0);
// Initialize population
Population population = ga.initPopulation(50);
}
}
2.4.4 评估
在评估阶段，种群中的每个个体都计算其适应度值，并存储以便将来使用。为了计算个体的适应度，我们使用所谓的“适应度函数”。
遗传算法通过选择来引导进化过程，得到更好的个体。因为正是适应度函数使得这种选择成为可能，所以适应度函数应该设计良好，提供个体适应度的准确值，这很重要。如果适应度函数设计得不够好，可能需要更长的时间才能找到满足的最低标准的解，也可能根本找不到可以接受的解。
适应度函数往往是遗传算法中需要最多计算的组件。正因为如此，适应度函数做好优化，有助于预防瓶颈，让算法高效地运行。这很重要。
每个特定的优化问题，都需要一个特别开发的适应度函数。在“全一”问题的例子中，适应度函数相当简单，只需计算个体染色体中1的数量。
现在为GeneticAlgorithm类添加一个calcFitness方法。该方法将计算染色体中1的个数，然后除以染色体的长度，使输出规格化，在0和1之间。你可以在GeneticAlgorithm类的任意位置添加此方法，因此下面省略了其周围的代码：
public double calcFitness(Individual individual) {
// Track number of correct genes
int correctGenes = 0;
// Loop over individual's genes
for (int geneIndex = 0; geneIndex < individual.getChromosomeLength();
geneIndex++) {
// Add one fitness point for each "1" found
if (individual.getGene(geneIndex) == 1) {
correctGenes += 1;
}
}
// Calculate fitness
double fitness = (double) correctGenes / individual.
getChromosomeLength();
// Store fitness
individual.setFitness(fitness);
return fitness;
}
我们也需要一个简单的辅助方法，遍历每个个体并评估它们（即对每个个体调用calcFitness）。我们称这个方法为evalPopulation，并将它也添加到GeneticAlgorithm类中。它看起来应该像下面这样，同样可以将它添加在任何位置：
public void evalPopulation(Population population) {
double populationFitness = 0;
for (Individual individual : population.getIndividuals()) {
populationFitness += calcFitness(individual);
}
population.setPopulationFitness(populationFitness);
}
此时，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) { }
}
如果缺少其中任何属性或方法，请现在就回去实现它们。我们还有4个方法要在GeneticAlgorithm类中实现：isTerminationConditionMet、selectParent、crossoverPopulation和mutatePopulation。
2.4.5 终止检查
接下来需要检查终止条件是否已经满足。有许多不同类型的终止条件。有时可能知道最佳解是什么（更确切地说，是可能知道最佳解的适应度值），在这种情况下，我们可以直接检查正确解。然而，并非总是能够知道最佳解的适应度是什么，所以我们可以在解变得“足够好”时终止，即解超过某个适应度阈值。如果算法运行了太长时间（太多世代），我们也可以终止，或者可以结合一些因素，决定终止该算法。
由于“全一”问题很简单，事实上，我们知道正确的适应度应该是1，在这种情况下，找到正确的解就终止，这是合理的。但情况并非总是这样！事实上，很少会这样。但我们很幸运，这是一个简单的问题。
首先，我们必须构建一个函数，检查终止条件是否已发生。我们可以在GeneticAlgorithm类中添加如下代码来实现这一点。代码添加在任意位置，和往常一样，为了简洁，我们省略了其他的类。
public boolean isTerminationConditionMet(Population population) {
for (Individual individual : population.getIndividuals()) {
if (individual.getFitness() == 1) {
return true;
}
}
return false;
}
上述方法检查种群中的每个个体，如果种群中任何个体的适应度为1，就返回true（这表明，我们已经找到了一个终止条件，可以停止）。
既然已经建立了终止条件，就可以在AllOnesGA类的主引导方法中添加一个循环，并使用新添加的终止检查作为其循环条件。如果终止检查返回true，遗传算法将停止循环，并返回其结果。
为了创建进化循环，将执行类AllOnesGA的main方法修改为如下所示。下面代码片段的前两行已经在main方法中。通过添加这段代码，我们将继续实现本章开头展示的伪代码：回忆一下，main方法是遗传算法伪代码的具体表现。下面是main方法现在的样子：
public static void main(String[] args) {
// These two lines were already here:
GeneticAlgorithm ga = new GeneticAlgorithm(100, 0.001, 0.95, 0);
Population population = ga.initPopulation(50);
// The following is the new code you should be adding:
ga.evalPopulation(population);
int generation = 1;
while (ga.isTerminationConditionMet(population) == false) {
// Print fittest individual from population
System.out.println("Best solution: " + population.
getFittest(0).toString());
// Apply crossover
// TODO!
// 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());
}
我们添加了一个进化循环，检查isTerminationConditionMet的输出。main方法的新内容还包括在循环之前和循环之内添加了evalPopulation调用，用于追踪世代数目的generation变量，以及调试消息，以便让你知道每一代的最佳解是怎样的。
我们还增加了程序结束时的代码：循环退出时，打印关于最终解的一些信息。
然而，现在我们的遗传算法会运行，但不会永远进化！我们将陷入一个无限循环中，除非我们很幸运，随机产生的一个个体恰好是“全一”。你可以点击Eclipse中的“Run”按钮，直接看到这样的行为。相同的解将一遍又一遍地提交，循环永远不会结束。你不得不点击Eclipse控制台上方的“Terminate”按钮，强制程序停止。
为了继续建立我们的遗传算法，需要实现另外两个概念：交叉和变异。通过随机变异和最适者生存，这些概念实际上推动了种群向前进化。
2.4.6 交叉
现在，是时候开始运用变异和交叉来进化种群了。交叉算子是一个过程，在这个过程中，种群中的个体交换它们的遗传信息，希望创建一个新的个体，包含亲代基因组中最好的部分。
在交叉过程中，考虑种群中每个个体是否参与交叉，这时使用交叉率参数。通过比较交叉率和一个随机数，我们可以决定个体是应该参与交叉，还是应该直加入下一个种群，不受交叉影响。如果选择了一个个体参与交叉，就需要找到第二个亲代。要找到第二个亲代，我们需要在多种可能的选择方法中挑一种。