この前遺伝的アルゴリズムのJavaライブラリをJavaScriptにゆるく移植したものを作成したのですが、それで今回黒ギャルにハンバーガーをあげるデモを作成してみました。
ランダムな初期値で生成したデータを使ってハンバーガーの初期位置、投げる速度、減速率を計算して移動させています。
そして遺伝的アルゴリズムによって、ハンバーガーは世代を重ねるごとに少しずつ黒ギャルの口へ近づいていきます。
※ただ、上のデモはアルゴリズムとしては粗末なものです。そのことについては改善版と一緒に後述します。
今回ある程度遺伝的アルゴリズムについて理解が深まったと思うので、備忘も兼ねてご紹介します。
デモもうちょっと詳しく
デモをみるだけじゃ一体何をしているのかよくわからないと思うので、もうちょっと補足します。
何をしているのか
遺伝的アルゴリズムを使い、黒ギャルにハンバーガーをあげています。
最初変なところでハンバーガーは止まってしまい、黒ギャルもたいそうご機嫌ななめな感じですが、繰り返していくごとに、徐々にハンバーガーは黒ギャルの近くまで届くようになります。
最初変なところで止まってしまうのは、ハンバーガーを投げる設定が全てランダムだからです。
徐々にハンバーガーが口に届くようになるのは、遺伝的アルゴリズムによってハンバーガーが投げる速度、位置などを学習していくからです。
ハンバーガーの初期位置、投げる速度と方向、減速率をそれぞれ遺伝子として持たせました。
評価は黒ギャルの口までの距離で行いました。
100点に近いほど高得点ということになります。
遺伝的アルゴリズムとは
読んで字のごとく「遺伝」をモデルにした学習アルゴリズムです。
最適化アルゴリズムというものの一種だそうで、だいたい以下のような感じで試行を繰り返して最適解を導き出していきます。
- 試行するインスタンス（生命クラス）に「遺伝子」を持たせ，その遺伝子の値によって動作を決める
- 遺伝子は最初ランダムに決める（ルールに沿って決めることもある）
- 微妙に異なる遺伝子を持った試行インスタンスを大量に生成し，定めたルールで成績をつけて順位付けする
- それぞれの遺伝子を交配し，次の試行インスタンスを生成する
- 交配と評価（＝適者生存）を繰り返していく
- 交配の際にときどき突然変異が起き，一部の遺伝子が反対に書き換えられる
最適化アルゴリズムには、他にも「丘のぼり法（山登り法）」や「焼きなまし法」「蟻コロニー最適化」といった様々な方法があるそうです。
遺伝子に役割を持たせる
今回のデモでは、33個の遺伝子を以下のように割り振りました。
- 1〜8番目の遺伝子で、Y座標を決める
- 9〜12番目の遺伝子で、Xの速度および向きを決める
- 13〜16番目の遺伝子で、Yの速度および向きを決める
- 17〜24番目の遺伝子で、Xの減速率を決める
- 25〜32番目の遺伝子で、Yの減速率を決める
- 33番目の遺伝子で、X座標の位置を決める
それぞれの遺伝子は、0か1かの値しか持ちません。
その0と1の組み合わせで初期値が決まり、結果の評価値も決まります。
評価値をもって弱者は切り落とし、後者のみが残っていきます。
実をいうと、ひとつのハンバーガーが投げられるまでには、画面にも表示されない100個のハンバーガー達が毎回作成されています。
水面下では毎回熾烈な競争を繰り広げられており、画面にはその中で勝ち残ったたったひとつのエリートバーガーだけを表示しています。
それぞれの親の遺伝を受け継ぐ
さて、そんな風にディスプレイという表舞台にたてるのは100個中1個のエリートバーガーのみという過酷な競争が毎回繰り広げられているわけですが、
その他のバーガー達はそのまま捨て置くわけではありません。
選別の後には「交配」というフェーズが待っており、彼らの遺伝子を使って次の世代が作られます。
もちろんエリートバーガーも交配に加わります。
交配にはいろんな方法があるみたいですが、今回移植したJGAPでは、単純に「DNA配列のランダムなN番目から最後までを交換する」というものでした。
交配によって、親のそれぞれの特徴を受け継いだ子供、兄弟が生まれてきます。
また、まれに遺伝子のある部分が突然変異を起こし、全く新しい子が生まれることもあります。
実際の遺伝子配列は0と1の組み合わせですが、上の図ではわかりやすくABCで表現してます。
上のデモでは「母親のコピー＋突然変異」「父親のコピー＋突然変異」「母親似＋突然変異」「父親似＋突然変異」を子供として作成してます。
ハーレムを形成する方が進化には有利？
ただ、最初にも書いたように上のデモはアルゴリズムとしては粗末なものです。
理由としては、カップリングの決め方がランダムなため、成績トップの子と成績最下位の子が結婚するというシンデレラストーリーが起こりうる為、遺伝子が相殺されちゃうんですね。
その可能性を排除してエリート同士だけが結婚して子孫を残せるようにすると、優秀な遺伝子だけが残るかもしれませんね。なんだか悪名高いナチスの優越主義を思い起こさせます。
なんだかそれはいたたまれないんで、もうちょっと別な子孫の残し方を考えます。
というわけで採用したのが、ハーレムです。エリートバーガー達には、全員ともれなく交配させます。
その部分だけ変えたのが下の方です。
遺伝的アルゴリズムで黒ギャルにハンバーガーをあげるデモ(ハーレム編)
わかりづらい？(´･ω･`)
でも見比べると結構一目瞭然なくらいハーレムの方が早く口に届いてる気がしません？
ちなみに
変えたのはGenotypeクラスの以下のメソッドだけです。
Genotype.prototype.evolve = function(){
this.workingPool = [];
for( var i = 0; i < this.chromosomes.length; i++){
this.workingPool.push(this.chromosomes[i].reproduce());
var firstMate = this.chromosomes[nextInt(this.chromosomes.length)];
var secondMate = this.chromosomes[nextInt(this.chromosomes.length)];
firstMate.crossover( secondMate );
this.workingPool.push(firstMate);
this.workingPool.push(secondMate);
}
for( var i = 0; i < this.workingPool.length; i++) {
var currentChromosome = this.workingPool[i];
currentChromosome.mutate();
var nextEvaluate = this.objectiveFunction.evaluate(currentChromosome);
this.populationSelector.add( currentChromosome , nextEvaluate);
}
this.chromosomes = this.populationSelector.select(
this.chromosomes.length);
};
これを、下のに置き換えました。
JsGap.Genotype.prototype.evolve = function(){
this.workingPool = [];
var length = this.chromosomes.length;
var sortChromosomes = this.getSortedChromosomes();
for (var i = 0 ; i < sortChromosomes.length; i++){
this.workingPool.push(sortChromosomes[i].reproduce());
var firstMate = sortChromosomes[i];
var secondMate = sortChromosomes[nextInt(10)].reproduce();
firstMate.crossover( secondMate );
this.workingPool.push(firstMate);
this.workingPool.push(secondMate);
}
for( var i = 0; i < this.workingPool.length; i++) {
var currentChromosome = this.workingPool[i];
currentChromosome.mutate();
var nextEvaluate = this.objectiveFunction.evaluate(currentChromosome);
this.populationSelector.add( currentChromosome , nextEvaluate);
}
this.chromosomes = this.populationSelector.select(
this.chromosomes.length);
};