6.3　第二个例子：遗传算法

6.3　第二个例子：遗传算法

遗传算法是基于自然选择原理的一种自适应启发式搜索算法，用于为最优化问题和搜索问题生成优质解决方案。遗传算法为一个问题提供可能的解决方案，而该问题被称为个体或者表现型（phenotype）。每个个体都由一组称作染色体的属性描述。通常，个体都由一个位序列表示，不过也可以选择更加适合具体问题的描述方法。

你还需要一个适应度函数，用来确定某个方案的优劣。遗传算法的主要目标是查找一个能够使该函数最大化或者最小化的解决方案。

遗传算法从问题的可能方案集合开始。这个可能方案的集合被称作种群。该初始集合可以随机生成或使用某种启发函数获得更好的初始解决方案。

一旦有了初始种群，可以启动一个含有三个阶段的迭代过程。该迭代过程的每一步称作一代。每一代有如下三个阶段。

选择：可以在种群中选择更好的个体，这些个体在适应度函数中具有较好的值。
交叉：对前一步选定的个体进行交叉，以生成构成新一代的新个体。这种操作需要两个个体参与并且生成两个新的个体。实现这种操作依赖于要解决的问题，以及所选择的个体的描述情况。
突变：可以应用突变运算符更改某个体的值。通常，只可以对极少量的个体执行该操作。虽然突变是一项对于查找优质解决方案非常重要的操作，但是并不应使用该操作简化本节的例子。

满足结束标准前，可以重复以上操作。结束标准可为以下几项。

固定的代的数目
适应度函数设置的预定值
找到了满足预定标准的解决方案
时间限制
手动停止

通常，将自己在上述过程中找到的最佳个体在种群外部储存起来。该个体将成为算法所建议的解决方案，而且通常它将成为较好的解决方案，因为还要产生新的一代。

本节将实现一个遗传算法解决著名的旅行商问题（TSP）。在该问题中，有一个城市集合和它们之间的距离集合，要找出一条最优路线，即在经过全部城市的同时旅行路线的总距离最短。与其他例子相同，我们实现了串行版程序和使用Phaser类的并发版程序。应用于TSP问题的遗传算法的主要特点如下。

个体：一个描述了城市遍历顺序的个体。
交叉：在交叉操作之后创建有效的解决方案。访问每个城市的次数必须只为一次。
适应度函数：该算法的主要目标是使遍历每个城市的总距离最短。
结束标准：将按照预定数目的代执行该算法。

如下表所示，有四个城市的距离矩阵。

	城市1	城市2	城市3	城市4
城市1	0	11	6	9
城市2	7	0	8	2
城市3	7	3	0	3
城市4	10	9	4	0

这意味着城市2到城市1的距离为7，但是城市1到城市2的距离为11。(2,4,3,1)可以为一个个体，而其适应度函数为2到4、4到3、3到1、1到2之间的距离之和，也就是2+4+7+11=24。

如果想在个体(1,2,3,4)和(1,3,2,4)之间进行交叉，那么就不能生成个体(1,2,2,4)，因为这样将访问城市2两次。可以生成(1,2,4,3)和(1,3,4,2)。

为测试该算法，使用了City Distance数据集中的两个例子，分别是15（lau15_dist）个城市和57（kn57_dist）个城市。

6.3.1　公共类

这两个版本都用到了以下三个公共类。

DataLoader类，用于从某个文件加载距离矩阵。此处并不给出该类的代码。它有一个静态方法，接收文件名，返回一个含有城市之间距离的int[][]矩阵。距离存放在一个CSV文件中（在原始格式中做了些许变换），这样很容易进行转换。
Individual类，该类存放了种群中某个个体的信息（即针对当前问题的可能解决方案）。为了表示每个个体，我们选择了一个整型数值的数组，它存放了访问不同城市的顺序。
GeneticOperators类，该类实现了交叉、选择和对种群或者个体的评估。

下面看看Individual类和GeneticOperators类的详细介绍。

Individual类

该类存放了TSP问题的所有可能解。每个可能的解都称作一个个体，将其描述称作染色体。在我们的例子中，将每个可能的解都表示为一个整型数组。该数组包含旅行商经过各个城市的顺序。该类还有一个整数值，用于存放适应度函数的结果。代码如下：

public class Individual implements Comparable<Individual> {
  private Integer[] chromosomes;
  private int value;

我们有两个构造函数。第一个接收必须访问的城市的数量作为参数，创建一个空数组。另一个构造函数接收Individual对象作为参数，并且复制其染色体，如下所示：

public Individual(int size) {
  chromosomes=new Integer[size];
}
public Individual(Individual other) {
  chromosomes = other.getChromosomes().clone();
}

我们也实现了compareTo()方法，使用适应度函数的结果比较两个个体。

@Override
public int compareTo(Individual o) {
  return Integer.compare(this.getValue(), o.getValue());
}

最后，还引入了获取和设定这些属性的方法。

GeneticOperators类

这是一个复杂类，因为它实现了遗传算法的内部逻辑。正如在本节开始介绍的那样，它提供了进行初始化、选择、交叉和评估操作的方法。我们将仅介绍该类提供的方法而非它们如何实现，以避免陷入不必要的复杂细节中。你可以下载本例的源代码分析该方法的实现。

该类提供的方法有如下几个。

initialize(int numberOfIndividuals, int size)：该方法创建了一个种群。该种群的个体数由numberOfIndividuals参数确定。染色体（本例中就是城市）的数目由size参数确定。该方法将返回一个Individual对象数组。它使用initialize(Integer[])方法初始化每个Individual对象。
initialize(Integer[] chromosomes)：该方法以随机方式初始化某一个体的染色体，生成合法的个体（即每个城市只访问一次）。
selection(Individual[] population)：该方法实现了选择操作，获取一个种群的最优个体。它用一个数组返回这些个体。该数组的大小将是种群大小的一半。可以测试其他标准以确定选定个体的数目。使用最适合函数选定这些个体。
crossover(Individual[] selected, int numberOfIndividuals, int size)：该方法接收一代中被选定的个体作为参数，并且使用交叉操作生成下一代的种群。下一代的个体数目将由同名的参数（即numberOfIndividuals）确定。个体的染色体数目将由size参数确定。它使用crossover (Individual, Individual, Individual, Individual)方法依据两个选定个体生成两个新个体。
crossover(Individual parent1, Individual parent2, Individual individual1, Individual individual2)：该方法实现了交叉操作，使用parent1个体和parent2个体生成下一代的individual1个体和individual2个体。
evaluate(Individual[] population, int [][] distanceMatrix)：该方法使用参数中接收的距离矩阵，将适应度函数应用到种群的全部个体。最后，该方法还按照解决方式从优到劣的顺序对种群进行排序，使用evaluate(Individual, int[][])方法评估每个个体。
evaluate(Individual individual, int[][] distanceMatrix)：该方法将适应度函数应用到某个体。
借助该类及其方法，可以满足实现遗传算法解决TSP问题的所有需求。

6.3.2　串行版本

我们使用如下两个类实现该算法的串行版本。

SerialGeneticAlgorithm类：用于实现该算法。
SerialMain类：根据输入参数执行算法并且度量执行时间。

下面详细分析一下这两个类。

SerialGeneticAlgorithm类

该类实现了遗传算法的串行版。从内部来看，它用到了如下四个属性。

含有所有城市之间距离的距离矩阵。
代的数目。
种群中的个体数。
每个个体中的染色体数目。
该类也有一个初始化所有属性的构造函数。

private int[][] distanceMatrix;
private int numberOfGenerations;
private int numberOfIndividuals;
private int size;
public SerialGeneticAlgorithm(int[][] distanceMatrix,
             int numberOfGenerations, int numberOfIndividuals) {
  this.distanceMatrix = distanceMatrix;
  this.numberOfGenerations = numberOfGenerations;
  this.numberOfIndividuals = numberOfIndividuals;
  size = distanceMatrix.length;
}

该类的主方法是calculate()方法。首先，使用initialize()方法来创建初始种群。然后，评估初始种群并且获取其最优个体作为算法的第一个解。

public Individual calculate() {
  Individual best;
  Individual[] population = GeneticOperators.initialize(
                            numberOfIndividuals, size);
  GeneticOperators.evaluate(population, distanceMatrix);
  best = population[0];

然后，执行由numberOfGenerations属性判定的循环。在每次循环中，使用selection()方法获取选定的个体，使用crossover()方法计算下一代、评估新一代，而且如果新一代的最优解优于到目前为止最好的个体，那么替换该个体。循环结束后，返回最优个体作为算法给出的解。

  for (int i = 1; i <= numberOfGenerations; i++) {
    Individual[] selected =
                    GeneticOperators.selection(population);
    population = GeneticOperators.crossover(selected,
                                 numberOfIndividuals, size);
    GeneticOperators.evaluate(population, distanceMatrix);
    if (population[0].getValue() < best.getValue()) {
      best = population[0];
    }
  }
  return best;
}

SerialMain类

该类针对本节用到的两个数据集执行遗传算法，即含有15个城市的lau15和含有57个城市的kn57。

main()方法必须接收两个参数。第一个参数是将要创建的代的数目，而第二个参数是希望每一代应有的个体数目。

public class SerialMain {
  public static void main(String[] args) {
  Date start, end;
  int generations = Integer.valueOf(args[0]);
  int individuals = Integer.valueOf(args[1]);

在每个例子中，均使用DataLoader类中的load()方法加载距离矩阵，创建SerialGeneticAlgorith对象，在执行calculate()方法的同时度量时间，并且在控制台输出执行时间和结果。

for (String name : new String[] { "lau15_dist", "kn57_dist" }) {
  int[][] distanceMatrix = DataLoader.load(Paths.get("data",
                                            name + ".txt"));
  SerialGeneticAlgorithm serialGeneticAlgorithm = new
           SerialGeneticAlgorithm(distanceMatrix, generations,
           individuals);
  start = new Date();
  Individual result = serialGeneticAlgorithm.calculate();
  end = new Date();
  System.out.println ("=======================================");
  System.out.println("Example:"+name);
  System.out.println("Generations: " + generations);
  System.out.println("Population: " + individuals);
  System.out.println("Execution Time: " + (end.getTime() -
                      start.getTime()));
  System.out.println("Best Individual: " + result);
  System.out.println("Total Distance: " + result.getValue());
  System.out.println ("=======================================");
}

6.3.3　并发版本

我们实现了遗传算法并发版本的不同类，如下所示。

SharedData类存放了所有将在任务之间共享的对象。
GeneticPhaser类扩展了Phaser类并且重载了它的onAdvance()方法，以便当所有任务都完成第一阶段后执行代码。
ConcurrentGeneticTask类实现了那些将用于执行遗传算法各个阶段的任务。
ConcurrentGeneticAlgorithm类使用前面的类实现遗传算法的并发版本。
ConcurrentMain类将在两个数据中集测试遗传算法的并发版本。

从内部来看，ConcurrentGeneticTask类将执行三个阶段。第一阶段是选择阶段，而且只能由一个任务执行。第二个阶段是交叉阶段，所有的任务都将使用选定的个体来构建新的一代。而最后一个阶段是评估阶段，所有任务都将对新一代个体进行评估。

让我们详细来看这其中的每一个类。

SharedData类

如前所述，该类包括由多任务共享的所有对象。其中包括如下内容。

种群数组，其中含有某一代的全部个体。
精选数组，其中含有精选的个体。
一个名为index的原子整型变量。这是唯一线程安全的对象，用于指明一个任务要生成或处理的个体的索引。
所有各代中的最优个体，将作为算法的解返回。
距离矩阵，其中含有城市之间的距离。
所有的对象都将被所有线程共享，但我们只需要用到一个并发数据结构。index是唯一被所有任务高效共享的属性。其余对象，要么仅供读取（例如距离矩阵），要么每个任务将访问对象（例如种群数组和精选数组）的不同部分，并不需要使用并发数据结构或者同步机制避免竞争条件。

public class SharedData {
  private Individual[] population;
  private Individual selected[];
  private AtomicInteger index;
  private Individual best;
  private int[][] distanceMatrix;
}

该类还含有用来获取和设定这些属性取值的方法。

GeneticPhaser类

我们需要在任务的阶段变化时执行代码，因此必须实现自己的分段器并且重载onAdvance()方法，在所有的参与方都完成某个阶段且即将开始执行下一阶段时执行该方法。GeneticPhaser类就实现了这样一个分段器。它存储了需要用到的SharedData对象，并且将其作为构造函数的参数之一。

public class GeneticPhaser extends Phaser {
  private SharedData data;
  public GeneticPhaser(int parties, SharedData data) {
    super(parties);
    this.data=data;
  }

onAdvance()方法将接收分段器的阶段编号和已注册参与方的编码作为参数。从内部来看，该分段器用整数表示阶段编号，每次阶段变化时该值都会按顺序增长。相反，我们的算法只有三个阶段，将被多次执行。必须将分段器的阶段编号转换成遗传算法的阶段编号，这样才能知道任务究竟是在执行选择阶段、交叉阶段还是评估阶段。为实现这一目的，我们计算分段器的阶段编号除以3的余数，如下所示：

protected boolean onAdvance(int phase, int registeredParties) {
  int realPhase=phase%3;
  if (registeredParties>0) {
    switch (realPhase) {
      case 0:
      case 1:
        data.getIndex().set(0);
        break;
      case 2:
        Arrays.sort(data.getPopulation());
      if (data.getPopulation()[0].getValue() <
           data.getBest().getValue()) {
        data.setBest(data.getPopulation()[0]);
      }
      break;
    }
    return false;
  }
  return true;
}

如果余数为0，任务完成了选择阶段并且准备执行交叉阶段。使用0值对该索引对象进行初始化。

如果余数为1，任务完成交叉阶段并且准备执行评估阶段。使用0值来初始化该索引对象。

最后，如果余数为2，任务已经完成了评估阶段且准备再次开始选择阶段。我们基于适应度函数对种群进行排序，并且如果必要，还要更新最优个体。

请注意，这种方法只能由任务中一个独立的线程执行。它在前一阶段结束时，由最后一个任务的线程执行（在arriveAndAwaitAdvance()调用的内部）。其他任务将休眠并且等待分段器。

ConcurrentGeneticTask类

该类实现了那些协作执行遗传算法的任务。这些任务执行了算法的三个阶段（选择、交叉和评估）。选择阶段仅由一个任务执行（称为主任务），而所有任务都将执行剩下的阶段。

从内部来看，该类用到了四个属性。

一个GeneticPhaser对象，用于在每个阶段结束时进行任务同步。
一个SharedData对象，用于访问共享数据。
必须计算的代的数目。
用于表明是否为主任务的布尔标志。
所有属性将在该类的构造函数中初始化。

public class ConcurrentGeneticTask implements Runnable {
  private GeneticPhaser phaser;
  private SharedData data;
  private int numberOfGenerations;
  private boolean main;
  public ConcurrentGeneticTask(GeneticPhaser phaser, int
                       numberOfGenerations, boolean main) {
    this.phaser = phaser;
    this.numberOfGenerations = numberOfGenerations;
    this.main = main;
    this.data = phaser.getData();
  }

run()方法实现了遗传算法的逻辑。它有一个生成指定代的循环。正如前面提到的，只有主任务会执行选择阶段。其他任务将使用arriveAndAwaitAdvance()方法等待该阶段结束，参看如下代码。

@Override
public void run() {
  Random rm = new Random(System.nanoTime());
  for (int i = 0; i < numberOfGenerations; i++) {
    if (main) {
      data.setSelected(GeneticOperators.selection(data
                      .getPopulation()));
    }
    phaser.arriveAndAwaitAdvance();

第二阶段是交叉阶段。使用在SharedData类中存放的AtomicInteger变量索引获得种群数组（每个任务都会计算）中的下一个位置。如前所述，交叉操作生成了两个新的个体，因此每个任务首先在种群数组中保留两个位置。为达到这一目的，使用getAndAdd(2)方法返回变量的实际值，并且按照两个单位的步长递增其取值。AtomicInteger变量是一个原子变量，因此并没有用到任何同步机制，这是原子变量的固有属性。参看下面的代码。

// 交叉阶段
int individualIndex;
do {
  individualIndex = data.getIndex().getAndAdd(2);
  if (individualIndex < data.getPopulation().length) {
    int secondIndividual = individualIndex++;
    int p1Index = rm.nextInt (data.getSelected().length);
    int p2Index;
    do {
      p2Index = rm.nextInt (data.getSelected().length);
    } while (p1Index == p2Index);
    Individual parent1 = data.getSelected() [p1Index];
    Individual parent2 = data.getSelected() [p2Index];
    Individual individual1 = data.getPopulation()
                       [individualIndex];
    Individual individual2 = data.getPopulation()
                       [secondIndividual];
    GeneticOperators.crossover(parent1, parent2,
                        individual1, individual2);
  }
} while (individualIndex < data.getPopulation().length);
phaser.arriveAndAwaitAdvance();

新种群的所有个体生成之后，各任务将使用arriveAndAwaitAdvance()方法同步该阶段的末尾。

最后阶段是评估阶段。我们再次使用AtomicInteger索引。每个任务都获取该变量的实际值，该值代表了个体在种群中的位置，并且使用getAndIncrement()值增加取值。一旦对所有个体的评估结束，就可使用arriveAndAwaitAdvance()方法同步该阶段的末尾。请记住，所有任务都完成该阶段后，GeneticPhaser类将执行排列种群数组的代码，如果有必要，还要更新最优个体变量，如下所示：

  // 评估阶段
  do {
    individualIndex = data.getIndex().getAndIncrement();
    if (individualIndex < data.getPopulation().length) {
      GeneticOperators.evaluate(data.getPopulation()
                   [individualIndex], data.getDistanceMatrix());
      }
    } while (individualIndex < data.getPopulation().length);
    phaser.arriveAndAwaitAdvance();
  }
  phaser.arriveAndDeregister();
}

最后，当所有的代都计算完毕后，各任务使用arriveAndDeregister()方法表示执行完毕，这样分段器就进入终止状态。

ConcurrentGeneticAlgorithm类

该类是遗传算法的外部接口。从内部来看，该类创建、启动那些计算不同代的任务，并且等待这些任务完成。该类用到了四个属性：代的数目、每一代的个体数目、每个个体的染色体数目以及距离矩阵，如下所示：

public class ConcurrentGeneticAlgorithm {
  private int numberOfGenerations;
  private int numberOfIndividuals;
  private int[][] distanceMatrix;
  private int size;
  public ConcurrentGeneticAlgorithm(int[][] distanceMatrix, int
               numberOfGenerations, int numberOfIndividuals) {
    this.distanceMatrix=distanceMatrix;
    this.numberOfGenerations=numberOfGenerations;
    this.numberOfIndividuals=numberOfIndividuals;
    size=distanceMatrix.length;
  }

calculate()方法执行遗传算法并且返回最优个体。首先，它使用initialize()方法创建最初的种群并对该种群进行评估，同时创建并初始化SharedData对象，其中含有所有必要的数据，如下所示：

public Individual calculate() {
  Individual[] population=
           GeneticOperators.initialize(numberOfIndividuals,size);
  GeneticOperators.evaluate(population,distanceMatrix);
  SharedData data=new SharedData();
  data.setPopulation(population);
  data.setDistanceMatrix(distanceMatrix);
  data.setBest(population[0]);

然后，创建各个任务。使用计算机可用的硬件线程数作为将要创建的任务数，该数目使用Runtime类的availableProcessors()方法返回。我们还创建了GeneticPhaser对象同步这些任务的执行，如下所示：

int numTasks=Runtime.getRuntime().availableProcessors();
GeneticPhaser phaser=new GeneticPhaser(numTasks,data);
ConcurrentGeneticTask[] tasks=new ConcurrentGeneticTask[numTasks];
Thread[] threads=new Thread[numTasks];
tasks[0]=new ConcurrentGeneticTask(phaser, numberOfGenerations,
                                   true);
for (int i=1; i< numTasks; i++) {
  tasks[i]=new ConcurrentGeneticTask(phaser, numberOfGenerations,
                                     false);
}

然后，创建Thread对象执行这些任务，启动任务并且等待其执行结束。最后，返回存放于ShareData对象的最优个体，如下所示：

for (int i=0; i<numTasks; i++) {
  threads[i]=new Thread(tasks[i]);
            threads[i].start();
        }
        for (int i=0; i<numTasks; i++) {
            try {
                threads[i].join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        return data.getBest();
    }
}

ConcurrentMain类

该类针对本节用到的两个数据集执行遗传算法，即含有15个城市的lau15和含有57个城市的kn57。该类的代码与SerialMain类相似，只不过使用ConcurrentGeneticAlgorithm而非SerialGeneticAlgorithm。

6.3.4　对比两种解决方案

现在对两种方案进行测试，看看哪一种具有更好的性能。如前所述，使用了来自City Distance Datasets的两个数据集——含有15个城市的lau15和含有57个城市的kn57。我们也测试了不同规模的种群（100、1000和10 000个个体），以及不同数目的代（10、100和1000）。

我们使用JMH框架（请查看名为“Code Tools: jmh”的文章）执行算例，这样可以在Java中实现微型基准测试。使用面向基准测试的框架是很好的解决方案，因为可以直接使用currentTimeMillis()或nanoTime()方法度量时间。在两种不同的架构上分别执行这些算例10次。

一台计算机配置了Intel Core i5-5300处理器、Windows 7操作系统和16 GB的RAM。该处理器有两个核，且每个核可以执行两个线程，这样我们就有四个并行线程。
另一台计算机配置了AMD A8-640处理器、Windows 10操作系统和8GB的RAM。该处理器有四个核。
Lau15数据集

第一个数据集的执行时间如下（单位：毫秒）。

AMD架构种群 100100010 000 代串行版并发版串行版并发版串行版并发版 1011.5927.1553.9854.40208.67121.10 10042.8058.61180.2496.541849.15904.76 1000148.01117.931412.81517.1415040.815660.30

Intel架构种群 100100010 000 代串行版并发版串行版并发版串行版并发版 109.2715.7928.6729.12117.0193.29 10045.5325.08115.4187.381041.76756.16 100094.9274.70724.77440.367867.564464.52

Kn57数据集

第二个数据集的执行时间如下（单位：毫秒）。

AMD架构种群 100100010 000 代串行版并发版串行版并发版串行版并发版 1025.2931.33104.72124.88889.07347.62 10095.2176.80795.64280.208479.723052.44 1000778.21267.677913.982524.2883 131.0929 417.48

Intel架构种群 100100010 000 代串行版并发版串行版并发版串行版并发版 1020.5132.0469.2786.12449.80274.99 10057.4656.54418.39224.934423.522183.10 1000417.38221.474069.092161.4641 714.9521 858.51

结论

在两种架构上，该算法针对两个数据集的表现情况相似。你会发现，当个体数目和代的数目都较少时，算法的串行版本执行时间较优，而当个体数目或代的数目增加时，并发版本将会有更好的吞吐量。以代的数目为1000且个体数目为10 000的kn57数据集为例，可得出加速比如下。

$\begin{aligned}&S_{{\rm AMD}}=\frac{T_{{\rm serial}}}{T_{{\rm concurrent}}}=\frac{83~131.09}{29~417.48}=2.82\\&S_{{\rm Intel}}=\frac{T_{{\rm serial}}}{T_{{\rm concurrent}}}=\frac{41~417.95}{21~858.51}=1.91\end{aligned}$

6.3 第二个例子：遗传算法