書(shū)名：代碼本色：用編程模擬自然系統(tǒng)
作者：Daniel Shiffman
譯者：周晗彬
ISBN：978-7-115-36947-5
第9章目錄

9.11　智能火箭：整合代碼

1、Population類(lèi)

• 現(xiàn)在，我們有了DNA類(lèi)（基因型）和Rocket類(lèi)（表現(xiàn)型）。還剩下一個(gè)Population類(lèi)沒(méi)有實(shí)現(xiàn)，這個(gè)類(lèi)的作用是管理火箭數(shù)組，實(shí)現(xiàn)選擇和繁殖功能。
• 告訴你一個(gè)好消息：我們可以使用猴子敲鍵盤(pán)示例程序的代碼，而且也不需要做太多修改。對(duì)于這兩個(gè)程序，創(chuàng)建交配池和生成子代個(gè)體數(shù)組的實(shí)現(xiàn)過(guò)程是完全一樣的。

class Population {
    float mutationRate; 記錄突變率、種群數(shù)組、交配池?cái)?shù)組及代計(jì)數(shù)器的種群變量
    Rocket[] population;
    ArrayList<Rocket> matingPool;
    int generations;
    void fitness() {} 這些函數(shù)沒(méi)有發(fā)生變化，因此無(wú)需列舉
    void selection() {}
    void reproduction() {}
}

• 但它們之間還是存在顯著的區(qū)別。
  在猴子敲鍵盤(pán)程序中，隨機(jī)語(yǔ)句在創(chuàng)建完成之后就進(jìn)行適應(yīng)度評(píng)估；字符串也沒(méi)有生命期，它的存在僅僅是為了計(jì)算適應(yīng)度。
  但在本例中，火箭需要先嘗試如何擊中靶子，運(yùn)行一段時(shí)間后才能做適應(yīng)度評(píng)估。
  因此，我們需要在Population類(lèi)中加入一個(gè)函數(shù)，該函數(shù)的職責(zé)是模擬物理運(yùn)動(dòng)，它的實(shí)現(xiàn)方式和粒子系統(tǒng)中的run()函數(shù)一樣——更新所有粒子的位置，并繪制它們。

void live() {
    for (int i = 0; i < population.length; i++) {
        population[i].run(); run()函數(shù)負(fù)責(zé)操縱力，更新火箭的位置及顯示火箭
    }
}

• 最后，我們可以實(shí)現(xiàn)setup()函數(shù)和draw()函數(shù)。主標(biāo)簽頁(yè)程序的主要職責(zé)是按序調(diào)用Population的成員函數(shù)，執(zhí)行遺傳算法的每個(gè)步驟。
  population.fitness();
  population.selection();
  population.reproduction();
• 不過(guò)，本例和猴子打字程序有所不同，我們不需要在每一幀中做這些事情。正確的執(zhí)行步驟如下：
  1.創(chuàng)建火箭種群
  2.讓所有火箭運(yùn)行N幀
  3.進(jìn)化出下一代
  ??選擇
  ??繁殖
  4.回到步驟2

2、改進(jìn)1：障礙物

• 為了讓系統(tǒng)更復(fù)雜，并進(jìn)一步展示進(jìn)化算法的威力，我們可以在系統(tǒng)中加入障礙物，火箭在飛行過(guò)程中必須避開(kāi)這些障礙物。我們可以創(chuàng)建一個(gè)靜止的矩形障礙物，只需在系統(tǒng)中引入一個(gè)Obstacle類(lèi)，該類(lèi)存放了障礙物的位置和尺寸。
• 我們還可以在Obstacle類(lèi)中加入一個(gè)contains()函數(shù)，該函數(shù)用于判斷火箭是否撞到障礙物，返回值是true或false。
• 如果存在一個(gè)障礙物數(shù)組，每個(gè)火箭都需要檢查它是否會(huì)撞到這些障礙物，我們可以在Rocket類(lèi)中增加一個(gè)函數(shù)：如果火箭撞到任何障礙物，返回true；如果沒(méi)有撞到，則返回false。
• 如果火箭撞到障礙物，它應(yīng)該停止運(yùn)動(dòng)，不再更新位置。
• 我們還應(yīng)該調(diào)整火箭的適應(yīng)度：火箭撞到障礙物是一件很可怕的事情，在這種情況下，火箭的適應(yīng)度應(yīng)該大大降低。

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、改進(jìn)2：更快地?fù)糁邪凶?/h2>

• 適應(yīng)度函數(shù)的唯一變量是火箭與靶子之間的距離。實(shí)際上，某些火箭在運(yùn)動(dòng)過(guò)程中曾經(jīng)非常接近靶子，但由于其運(yùn)動(dòng)速度過(guò)快，最終超越了靶子。因此，火箭的運(yùn)動(dòng)應(yīng)該更加緩慢而平穩(wěn)。
• 優(yōu)化火箭飛行速度的方式有很多種。首先，我們可以記錄在飛行期火箭與靶子的最近距離，用這個(gè)距離代替兩者的最終距離。我們用recordDist變量表示這個(gè)最近距離。
• 除此之外，火箭到達(dá)靶子所花費(fèi)的時(shí)間應(yīng)該成為獎(jiǎng)賞因素。換句話說(shuō)，火箭越快到達(dá)靶子，它的適應(yīng)度就越高；越慢到達(dá)靶子，適應(yīng)度就越低。為了實(shí)現(xiàn)這一特性，我們需要引入一個(gè)計(jì)數(shù)器，在火箭生命期的每一輪遞增這個(gè)計(jì)數(shù)器，直到它到達(dá)靶子。最后，計(jì)數(shù)器的值等于火箭到達(dá)靶子所花費(fèi)的時(shí)間。
• 適應(yīng)度和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、運(yùn)行結(jié)果

前3代

26代進(jìn)化后已經(jīng)可以繞過(guò)障礙命中目標(biāo)