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

9.11　智能火箭：整合代码

1、Population类

• 现在，我们有了DNA类（基因型）和Rocket类（表现型）。还剩下一个Population类没有实现，这个类的作用是管理火箭数组，实现选择和繁殖功能。
• 告诉你一个好消息：我们可以使用猴子敲键盘示例程序的代码，而且也不需要做太多修改。对于这两个程序，创建交配池和生成子代个体数组的实现过程是完全一样的。

class Population {
    float mutationRate; 记录突变率、种群数组、交配池数组及代计数器的种群变量
    Rocket[] population;
    ArrayList<Rocket> matingPool;
    int generations;
    void fitness() {} 这些函数没有发生变化，因此无需列举
    void selection() {}
    void reproduction() {}
}

• 但它们之间还是存在显著的区别。
  在猴子敲键盘程序中，随机语句在创建完成之后就进行适应度评估；字符串也没有生命期，它的存在仅仅是为了计算适应度。
  但在本例中，火箭需要先尝试如何击中靶子，运行一段时间后才能做适应度评估。
  因此，我们需要在Population类中加入一个函数，该函数的职责是模拟物理运动，它的实现方式和粒子系统中的run()函数一样——更新所有粒子的位置，并绘制它们。

void live() {
    for (int i = 0; i < population.length; i++) {
        population[i].run(); run()函数负责操纵力，更新火箭的位置及显示火箭
    }
}

• 最后，我们可以实现setup()函数和draw()函数。主标签页程序的主要职责是按序调用Population的成员函数，执行遗传算法的每个步骤。
  population.fitness();
  population.selection();
  population.reproduction();
• 不过，本例和猴子打字程序有所不同，我们不需要在每一帧中做这些事情。正确的执行步骤如下：
  1.创建火箭种群
  2.让所有火箭运行N帧
  3.进化出下一代
    选择
    繁殖
  4.回到步骤2

2、改进1：障碍物

• 为了让系统更复杂，并进一步展示进化算法的威力，我们可以在系统中加入障碍物，火箭在飞行过程中必须避开这些障碍物。我们可以创建一个静止的矩形障碍物，只需在系统中引入一个Obstacle类，该类存放了障碍物的位置和尺寸。
• 我们还可以在Obstacle类中加入一个contains()函数，该函数用于判断火箭是否撞到障碍物，返回值是true或false。
• 如果存在一个障碍物数组，每个火箭都需要检查它是否会撞到这些障碍物，我们可以在Rocket类中增加一个函数：如果火箭撞到任何障碍物，返回true；如果没有撞到，则返回false。
• 如果火箭撞到障碍物，它应该停止运动，不再更新位置。
• 我们还应该调整火箭的适应度：火箭撞到障碍物是一件很可怕的事情，在这种情况下，火箭的适应度应该大大降低。

Obstacle.pde

class Obstacle {

  PVector position;
  float w,h;
  
  Obstacle(float x, float y, float w_, float h_) {
    position = new PVector(x,y);
    w = w_;
    h = h_;
  }

  void display() {
    stroke(0);
    fill(175);
    strokeWeight(2);
    rectMode(CORNER);
    rect(position.x,position.y,w,h);
  }

  boolean contains(PVector spot) {
    if (spot.x > position.x && spot.x < position.x + w && spot.y > position.y && spot.y < position.y + h) {
      return true;
    } else {
      return false;
    }
  }

}

3、改进2：更快地击中靶子

• 适应度函数的唯一变量是火箭与靶子之间的距离。实际上，某些火箭在运动过程中曾经非常接近靶子，但由于其运动速度过快，最终超越了靶子。因此，火箭的运动应该更加缓慢而平稳。
• 优化火箭飞行速度的方式有很多种。首先，我们可以记录在飞行期火箭与靶子的最近距离，用这个距离代替两者的最终距离。我们用recordDist变量表示这个最近距离。
• 除此之外，火箭到达靶子所花费的时间应该成为奖赏因素。换句话说，火箭越快到达靶子，它的适应度就越高；越慢到达靶子，适应度就越低。为了实现这一特性，我们需要引入一个计数器，在火箭生命期的每一轮递增这个计数器，直到它到达靶子。最后，计数器的值等于火箭到达靶子所花费的时间。
• 适应度和finishTime成反比

Rocket.pde

class Rocket {

  // All of our physics stuff
  PVector position;
  PVector velocity;
  PVector acceleration;

  // Size
  float r;

  // How close did it get to the target
  float recordDist;

  // Fitness and DNA
  float fitness;
  DNA dna;
  // To count which force we're on in the genes
  int geneCounter = 0;

  boolean hitObstacle = false;    // Am I stuck on an obstacle?
  boolean hitTarget = false;   // Did I reach the target
  int finishTime;              // What was my finish time?

  //constructor
  Rocket(PVector l, DNA dna_, int totalRockets) {
    acceleration = new PVector();
    velocity = new PVector();
    position = l.get();
    r = 4;
    dna = dna_;
    finishTime = 0;          // We're going to count how long it takes to reach target
    recordDist = 10000;      // Some high number that will be beat instantly
  }

  // FITNESS FUNCTION 
  // distance = distance from target
  // finish = what order did i finish (first, second, etc. . .)
  // f(distance,finish) =   (1.0f / finish^1.5) * (1.0f / distance^6);
  // a lower finish is rewarded (exponentially) and/or shorter distance to target (exponetially)
  void fitness() {
    if (recordDist < 1) recordDist = 1;

    // Reward finishing faster and getting close
    fitness = (1/(finishTime*recordDist));

    // Make the function exponential
    fitness = pow(fitness, 4);

    if (hitObstacle) fitness *= 0.1; // lose 90% of fitness hitting an obstacle
    if (hitTarget) fitness *= 2; // twice the fitness for finishing!
  }

  // Run in relation to all the obstacles
  // If I'm stuck, don't bother updating or checking for intersection
  void run(ArrayList<Obstacle> os) {
    if (!hitObstacle && !hitTarget) {
      applyForce(dna.genes[geneCounter]);
      geneCounter = (geneCounter + 1) % dna.genes.length;
      update();
      // If I hit an edge or an obstacle
      obstacles(os);
    }
    // Draw me!
    if (!hitObstacle) {
      display();
    }
  }

  // Did I make it to the target?
  void checkTarget() {
    float d = dist(position.x, position.y, target.position.x, target.position.y);
    if (d < recordDist) recordDist = d;

    if (target.contains(position) && !hitTarget) {
      hitTarget = true;
    } 
    else if (!hitTarget) {
      finishTime++;
    }
  }

  // Did I hit an obstacle?
  void obstacles(ArrayList<Obstacle> os) {
    for (Obstacle obs : os) {
      if (obs.contains(position)) {
        hitObstacle = true;
      }
    }
  }

  void applyForce(PVector f) {
    acceleration.add(f);
  }


  void update() {
    velocity.add(acceleration);
    position.add(velocity);
    acceleration.mult(0);
  }

  void display() {
    //background(255,0,0);
    float theta = velocity.heading2D() + PI/2;
    fill(200, 100);
    stroke(0);
    strokeWeight(1);
    pushMatrix();
    translate(position.x, position.y);
    rotate(theta);

    // Thrusters
    rectMode(CENTER);
    fill(0);
    rect(-r/2, r*2, r/2, r);
    rect(r/2, r*2, r/2, r);

    // Rocket body
    fill(175);
    beginShape(TRIANGLES);
    vertex(0, -r*2);
    vertex(-r, r*2);
    vertex(r, r*2);
    endShape();

    popMatrix();
  }

  float getFitness() {
    return fitness;
  }

  DNA getDNA() {
    return dna;
  }

  boolean stopped() {
    return hitObstacle;
  }
}

4、运行结果

前3代 26代进化后已经可以绕过障碍命中目标