See the Pen Genetic Algorithms(遺伝的アルゴリズム） by kanaparty (@kanaparty) on CodePen.
遺伝的アルゴリズムを使ってランダムな文字列から「音はしぐれか」
種田山頭火 - Wikipediaへ進化させる。
ステップは大きく分けて３つ
これを繰り返して進化させていくアルゴリズム
（「進化させていく」って表現でいいのかしらと思ったら本には「特定の問題を解決することを意図して実装される」と書いてあった。
遺伝的アルゴリズム - Wikipedia
wikipediaでは「解を探索する」と書いてあった。）
解は決まっていて、そこまでたどり着くための手法。
この経過の様子を眺めているのが結構楽しい。
遺伝的アルゴリズムを実装するときに必要な、ダーウィンの進化論の中核の３つの要素
- 遺伝
子が親の性質を受け継ぐ
- 変異
集団に多様な形質があるか、突然変異しないとすべての個体が同じ形質になってしまって進化が止まる
- 選択
適者生存。自然選択でいうところの環境に適している個体が生き残ること。解決したい解によって異なる。
集団の生成
初期化部分。
解、初期集団を生成する。
コードでいうとこの部分
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個作る。
選択
今回は７文字の文字列が「おとはしぐれか」に近いものをより選択しやすくする状況を作る。
選択するときは、一致している具合に応じた数（適応度が高ければ多く、低ければ少ない）親を入れ物（配列）にコピーしていれておいて
そこから次の世代の親を２つ拾うようにする。
結果的に適応度が高い個体が選ばれやすくなる。
適応度に応じてプールにいれているところ↓
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;
}
}
という感じでこれを繰り返すといつか「おとはしぐれか」になる！
