search
LoginSignup
8

posted at

updated at

Pythonによる人工知能入門1 「遺伝的アルゴリズム~理論編~」

初めに

 初めまして、機械学習好きの学生です。趣味と研究で様々な学習理論を学習し、実装したりしています。
 ここでは、他の理論と比べて比較的容易にフルスクラッチで書くことができる遺伝的アルゴリズム(GA)についてご紹介させていただければと思います。
 私自身もいまだ未熟ですので、玄人の方はお手柔らかにお願い致します。

比較的わかりやすい遺伝的アルゴリズム

 機械学習(もとい最適化問題)の中で、1から10まで理解するのに比較的体力を必要としないものの一つがこれです。
 ニューラルネットワークやベイズ最適化は数学やらの基礎知識を要しますが(まあなくても実装はできる)、この遺伝的アルゴリズムはそうでもないので、初学者にとってもとっかかりやすいと考えています。

「遺伝的」アルゴリズムとは

 例えば、100個のパラメータで動くゴキブリがいたとしましょう。
 パラメータはランダムで決定され、合計で50匹のゴキブリが存在すると仮定します。これらをかけっこか何かで競争させると、みんな違うパラメータを持っているので走るのが速い奴もいれば、遅い奴もいるでしょう。そうして順位をつけます。一位と二位で子供を産ませると、はたしてその子供は早い奴になれるでしょうか。
 「遺伝的」 には、なれます。
 そんな感じで、上位10匹程度で子供を産ませて、もともとの50匹のうちの遅い奴らとメンバーチェンジをすると、前よりも優秀なやつが多い集団ができることになります。

 そしてまた競争させて、遺伝的に優秀な子供を産ませて、入れ替えて、また競争させて、、、、を繰り返していくと、いつかはものすごい早い奴が出てくるでしょう。

 というのが遺伝的アルゴリズムの背景というか概念というか根本です。

 そもそも機械学習とは、他にもランダムフォレストやニューラルネットワークなどがありますが、そのほとんどが準最適化問題を解いていることと同じです。遺伝的アルゴリズム(GA)もその一つで、その概要は多くの生物を出現させ、生存競争をさせた後一番強い奴を決めるといったものです。

これは、以下の手順に分類できます。

         ⑴初期の集団を生成
         ⑵評価
         ⑶交叉(遺伝)
         ⑷突然変異
         ⑸集団交代(世代交代)
          あとは⑵~⑸の繰り返し

それぞれについてみていきましょう。

⑴初期集団(第一世代)

 例はゴキブリの話でしたが、もちろん設定は自分で考えます。ここでパラメータの集合を配列として見立てると、あたかも生物の遺伝子情報(ゲノム)のようですね。
 初期の個体数とパラメータの数を決めて、ランダムに個体を生成してそれを第一世代とします。

⑵評価

 何をもってランキング付けをするのかを決めて、それに則り個体一つ一つを評価します。上の例では、ゴキブリの「走る速さ」が評価基準となっていますね。

⑶交叉

 ここが遺伝という概念を利用している工程です。評価の段階で優秀なやつ同士を親として、子供を産ませます。そのときにその子供のパラメータをどう決めるか考えます。(生ませるといっても、プログラム上では親のゲノム配列を引き継いだ新しい個体を作ることになります。)
 よく使用されるのはn点交叉であり、親の遺伝子(パラメータを配列としたもの)をn点で分割して半分ずつ引き継ぐというものです。

⑷突然変異

 交叉で引き継がれた子の遺伝子を一定の確率でランダムに改変します。これにより同一個体が発生しても競争が膠着しないようにします(つまり、ランダム性をもたせてより個体同士に差を生ませるということ)

まとめ

 ここまで読んでくださりありがとうございました。簡単な理論についてはここで紹介したとおりになります。実際には、進化計算、共進化計算など様々なものがありますが、論文などを通して理解を深めることをお勧めいたします。
 また、pythonによる実装も以下で行っておりますので、引き続きよろしくお願い致します。

 Pythonによる人工知能入門2 「遺伝的アルゴリズム~実践編~」

 

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
What you can do with signing up
8