书名：代码本色：用编程模拟自然系统
作者：Daniel Shiffman
译者：周晗彬
ISBN：978-7-115-36947-5
第9章目录

9.8　遗传算法：整合代码

• 我们已经学习了两次遗传算法的实现步骤：
  第1次用文字形式描述，
  第2次用代码片段实现。
• 在本节，我们要把前面的内容合并，用代码描述算法的各个步骤。

1、示例

示例代码9-1　遗传算法：进化出莎士比亚名言

• 主标签页的实现代码反映了遗传算法的各个步骤，它调用的功能函数是在DNA类中实现的。

GA需要的变量
float mutationRate = 0.01;    // 突变率
int totalPopulation = 150;      // 个体总数

DNA[] population;             // 个体数组
ArrayList<DNA> matingPool;    //交配池数组 "mating pool"
String target;                // 目标答案

PFont f;

void setup() {
  size(800, 200);
  target = "to be or not to be";  //初始化目标答案和突变率

  population = new DNA[totalPopulation]; //步骤1：初始化种群

  for (int i = 0; i < population.length; i++) { //步骤2a：计算适应度
    population[i] = new DNA(target.length());
  }
  
  f = createFont("Courier",12,true);
}

void draw() {
  for (int i = 0; i < population.length; i++) { //步骤2：选择
    population[i].calcFitness(target);
  }

  ArrayList<DNA> matingPool = new ArrayList<DNA>();  // 步骤2b：创建交配池 "mating pool"

  for (int i = 0; i < population.length; i++) {
    int nnnn = int(population[i].fitness * 100);  // 根据适应度分值将个体加入交配池
    for (int j = 0; j <nnnn; j++) {              // and pick two random numbers
      matingPool.add(population[i]);
    }
  }

  for (int i = 0; i < population.length; i++) { //步骤3：繁殖
    int a = int(random(matingPool.size()));
    int b = int(random(matingPool.size()));
    DNA partnerA = matingPool.get(a);
    DNA partnerB = matingPool.get(b);
    DNA child = partnerA.crossover(partnerB); //步骤3a：交叉
    child.mutate(mutationRate);   //步骤3b：变异
    population[i] = child;        //用新的子代覆盖种群draw()循环会重复执行这些步骤
  }
  
  background(255);
  fill(0);
  String everything = "";
  for (int i = 0; i < population.length; i++) {
    everything += population[i].getPhrase() + "     ";
  }
  textFont(f,12);
  text(everything,10,10,width,height);
}

• DNA.pde

class DNA {

  // The genetic sequence
  char[] genes;
  
  float fitness;
  
  // Constructor (随机地创建DNA)
  DNA(int num) {
    genes = new char[num];
    for (int i = 0; i < genes.length; i++) {
      genes[i] = (char) random(32,128);  // Pick from range of chars
    }
  }
  
  // Converts character array to a String
  String getPhrase() {
    return new String(genes);
  }
  
  // 计算适应度(returns floating point % of "correct" characters)
  void calcFitness (String target) { 
     int score = 0;
     for (int i = 0; i < genes.length; i++) {
        if (genes[i] == target.charAt(i)) {
          score++;
        }
     }
     fitness = (float)score / (float)target.length();
  }
  
  // 交叉
  DNA crossover(DNA partner) {
    // A new child
    DNA child = new DNA(genes.length);
    
    int midpoint = int(random(genes.length)); // Pick a midpoint
    
    // Half from one, half from the other
    for (int i = 0; i < genes.length; i++) {
      if (i > midpoint) child.genes[i] = genes[i];
      else              child.genes[i] = partner.genes[i];
    }
    return child;
  }
  
  // 突变, picks a new random character
  void mutate(float mutationRate) {
    for (int i = 0; i < genes.length; i++) {
      if (random(1) < mutationRate) {
        genes[i] = (char) random(32,128);
      }
    }
  }
}

2、改进

• 在上例中加入一个额外的特性，使其能输出更多遗传算法的工作信息。
• 一旦得到目标语句，马上停止遗传算法
• 用一个Population类管理GA（替换draw()函数中的代码）。
  程序（略）

3、运行结果