nature of code:今日の練習「遺伝的アルゴリズム」

See the Pen Genetic Algorithms(遺伝的アルゴリズム) by kanaparty (@kanaparty) on CodePen.

遺伝的アルゴリズムを使ってランダムな文字列から「音はしぐれか」 種田山頭火 - Wikipediaへ進化させる。

遺伝的アルゴリズム

ステップは大きく分けて3つ

  • 集団の生成
  • 選択
  • 生殖

これを繰り返して進化させていくアルゴリズム (「進化させていく」って表現でいいのかしらと思ったら本には「特定の問題を解決することを意図して実装される」と書いてあった。 遺伝的アルゴリズム - Wikipedia wikipediaでは「解を探索する」と書いてあった。) 解は決まっていて、そこまでたどり着くための手法。 この経過の様子を眺めているのが結構楽しい。

ダーウィン自然選択説

遺伝的アルゴリズムを実装するときに必要な、ダーウィンの進化論の中核の3つの要素

  • 遺伝  子が親の性質を受け継ぐ
  • 変異  集団に多様な形質があるか、突然変異しないとすべての個体が同じ形質になってしまって進化が止まる
  • 選択  適者生存。自然選択でいうところの環境に適している個体が生き残ること。解決したい解によって異なる。

集団の生成

初期化部分。 解、初期集団を生成する。 コードでいうとこの部分

//ターゲット句
var target = 'おとはしぐれか';
//集団の初期化
var population = new Population();
population.init();

//個体
class DNA{
  constructor(){
    this.genes = [];
    this.fitness = 0;//適合度
  }
  //初期化
  init(){
    for (var i = 0; i < targetLength; i++) {
      this.genes[i] = String.fromCharCode(Math.floor(Math.random() * 81) + 12354);
    }
  }
}

//個体群
class Population{
  constructor(){
    this.List = [];
    this.length = 100;
    this.children = [];
    this.finished = false;
  }
  init(){
    for (var i = 0; i < this.length; i++) {
      this.List.push(new DNA());
      this.List[i].init();
    }
  }
}

目指す句の文字列を決めて、ランダムな文字列の句の集団を100個作る。

選択

今回は7文字の文字列が「おとはしぐれか」に近いものをより選択しやすくする状況を作る。 選択するときは、一致している具合に応じた数(適応度が高ければ多く、低ければ少ない)親を入れ物(配列)にコピーしていれておいて そこから次の世代の親を2つ拾うようにする。 結果的に適応度が高い個体が選ばれやすくなる。

適応度に応じてプールにいれているところ↓

//プール
var matingPool = [];

//個体
class DNA{
  //適合度をはかる
  calcFitness(){
    var score = 0;
    for (var i = 0; i < targetLength; i++) {
      if(this.genes[i] === target.charAt(i)){
        score++;
      }
    }
    this.fitness  = score / targetLength;
  }
}
//個体群
class Population{
  //淘汰
  naturalSelection(){
    matingPool = [];

    for (var i = 0; i < this.length; i++) {
      this.List[i].calcFitness();
      var fitness = this.List[i].fitness;
      //完全一致していたら止める
      if(fitness === 1){
        this.finished = true;
      }
      //適応度に応じた数をプールに入れる
      for (var j = 0; j < count; j++) {
        matingPool.push(population.List[i]);
      }
    }
  }
}

生殖

親をプールから選んで次の世代を作っているところ

//個体群
class Population{
  createNextGenelation(){
    //プールから親二つを取り出す
    for (var i = 0; i < this.length; i++) {
      var parentA = matingPool[Math.floor(Math.random() * matingPool.length)];
      var parentB = matingPool[Math.floor(Math.random() * matingPool.length)];
      //生殖(突然変異含む)
      this.children[i] = parentA.crossover(parentB);
    }
  }
}

//個体
class DNA{
  //交配
  crossover(partner){
    var child = new DNA();
    var midpoint = Math.floor(Math.random() *  targetLength);
    var mutate = (Math.random() < 0.1) ? true : false ;

    //突然変異
    if(mutate){
      child.init();
    }
    else{
      for (var i = 0; i < targetLength; i++) {
        if(i < midpoint){
          child.genes[i] = this.genes[i];
        }
        else{
          child.genes[i] = partner.genes[i];
        }
      }
    }

    return child;
  }
}

という感じでこれを繰り返すといつか「おとはしぐれか」になる!