【機械学習を学ぼう】#7　遺伝的アルゴリズム

　涌井 良幸著「Excelでわかる機械学習 超入門 ―AIのモデルとアルゴリズムがわかる 」で勉強しています。

　今回は遺伝的アルゴリズム（Genetic Algorithm、GA）と呼ばれる手法を学びます。本書では、「遺伝的アルゴリズムは、生命の進化を模した計算によって、局所解を解決しようとするもの」と説明されています。遺伝的アルゴリズムを用いるのは「#3 最小２乗法」でも扱ったように、機械学習においてはモデルの最適化が重要になりますが、その際に障害となるのが、最小値を求めたいのに極小値にはまってしまう問題です。

遺伝的アルゴリズムで最小値問題を解く

　例題として、関数f(x)=x^4-16/3x^3+6x^2の最小値を求めていきます。グラフで書くと以下のとおりとなり最小値はxが3のときに-9となります。これを遺伝的アルゴリズムを使って求めていきます。

ｘの候補を選んで２進数で表示する

　最初に行うのは、xの値をいくつか「候補」として生成していきます。本書ではランダムに生成したとする[7, 9, 12, 13]を使っていっています。これを２進数で表すと[0111, 1001, 1100, 1101]となります。

　これらの「候補」１つ１つを生命に例えて「個体(indivisual)」と呼びます。これらの個体を進化させて解を求めるのが遺伝的アルゴリズムになります。

　遺伝的アルゴリズムは３つの操作から成り立ちます。「選択(selection)」、「交叉(crossover)」、「突然変異(mutation)」

環境に適合するものを「選択」

　選択は、現在の個体（すなわち親）がどれくらい環境に適しているかを確認する操作です。実際に関数f(x)に当てはめると次のようになります。

　ここでは最小値を求めたいので、この環境に適している小さい解が求まる7(0111)と９(1001)を親として「選択」し、ほかは捨てる（淘汰）することにします。

優れた個体を作るために「交叉」させる

　交叉とは、親から新しい個体を誕生させる操作です。交叉の仕方は様々ありますが、ここでは「一点交叉」という単純な方法で交叉していきます。

　まず、適当なところで遺伝子を２つに分割します。

（親）　0111 → 01 | 11、1001 → 10 | 01

　つぎに、各々の下位2ビットを入れ替えます。

（交叉）01 | 01、10 | 11

　こうすることで、新生代として次の４つの遺伝子が残ります。

　0111 、1001 、0101、1011・・・①

突然変異

　突然変異は、文字どおりある個体の遺伝子に突然変異を起こさせることをいいます。

　ここでは、新世代①からランダムに１つの個体を選び、その個体のランダムな1ビットを書き換えることにします。

　「0111」の最下位ビットを0に変更します。

　以上の３操作（選択、交叉、突然変異）が１サイクルとなり、このサイクルを繰り返すことで、最小値が得られる確率が高まっていきます。

エクセルで遺伝的アルゴリズムを行ってみる

　ここでの作業はエクセルに関数が入っているとはいえかなりアナログです。１ステップ目の突然変異の箇所は手入力で２ステップ目以降はランダム関数を使っています。

　今回のケースでは６ステップ目で最小値が求まりました。

　この本のサンプルでついているエクセルファイルには９ステップ目までの表が入っていますが、９ステップでは最小値が求まらないケースもあります。