遺伝的アルゴリズム
これは 人工知能アドベントカレンダー の17日目の記事です。
Advent Calendar 2015ランキング - Qiita によれば購読者数ランキングで3位になったそうです。最近は内容があまり充実していませんが引き続きよろしくお願いします。
そろそろ機械学習の話も終わりにして、次回からは具体的に脳の機能をいかにして再現するかという点に焦点を絞っていきますが、その前にすこし趣向を変えて、遺伝的アルゴリズムについて説明します。
遺伝的アルゴリズムとは
遺伝的アルゴリズム(genetic algorithm, GA)は、生命の進化を模して計算を行うことで、従来より柔軟な処理ができるのではないかという発想から生まれたものです*1。
生命は最初はごく単純な存在でしたが、非常に長い時間をかけて少しずつより環境に適応するよう進化してきました。「進化」という方法によって、最初は海を漂うタンパク質程度でしかなかったものが、泳ぐようになり、光合成するようになり、空を飛んだり、木に登ったり、さらには二足歩行をして月に行ったりすることができるようにまでなったことを考えれば、進化そのものをコンピュータで扱うという発想は自然なものといえます。
そんなわけで、1975年には John Henry Holland によって早くも遺伝的アルゴリズムが誕生しました(タイミング的には、パーセプトロンより後で、バックプロパゲーションよりは前、といったところ)。
初期の遺伝的アルゴリズムは効率の点からもはや使われていませんが、その改良アルゴリズムは今でも現役で使われています。有名な例だと、新幹線のN700系のノーズ形状は遺伝的アルゴリズムで設計されたようです。他の例としては、昔は巡回セールスマン問題*2の近似解法としてかなり盛んに研究されました。
遺伝的アルゴリズムが解けるのは基本的に組合せ最適化と言われる問題で、この世のありとあらゆる問題が解けるわけではありませんが、それでも強力な手法です。
アルゴリズム
進化を模倣するなんてさぞ複雑なアルゴリズムなのだろうと思われますが、実際のところその概念は非常にシンプルです。
ここではわかりやすく のときの x の値を求めましょう。
まず、解の候補をいくつか生成します。初期のビットストリング型GAと呼ばれる、値を2進数で扱うものにして、とりあえず4bitで表現することにします。ランダムに4つくらい解の候補を生成しましょう。カッコ内はわかりやすさのための10進数表記です。
- 0000 (0)
- 0101 (5)
- 1100 (12)
- 1101 (13)
この解の候補を個体(individual)と呼びます。つまり、ひとつひとつが生命（遺伝子）だと考えるわけです。この個体を進化させて正しい解を求めるのが遺伝的アルゴリズムの目的です。この後の操作は
- 選択(淘汰)
- 交叉
- 突然変異
の3つを繰り返すだけです。
選択
選択(selection)は、今の個体がどれくらい良いかを見ます。現実世界で例えるなら、環境に適応していない個体は厳しい自然界を生き残れず死ぬ可能性が高く、環境にうまく適応できる個体は生きて子孫を残す可能性が高くなるわけです。その適応度を測定します。ここでは、さきほどの の x に値を実際に当てはめてみましょう。
- 0000 (0) → 9
- 0101 (5) → 4
- 1100 (12) → 81
- 1101 (13) → 100
この世界では値が0に近い個体ほど優れた生命体なので、どうやら 1100 と 1101 の個体はイマイチのようです。逆に0101の個体はかなり適応度が高い(0に近い)ことがわかります。
交叉
交叉(crossover)はふたつの個体から新しい個体（子供）を誕生させる操作です。さきほどの結果を見ると、 0000 の個体と 0101 の個体が良さそうなので、この2つを選んで子供を作りましょう。交叉の仕方は様々ですが、今回は一点交叉という方法をとりましょう。
適当なところで遺伝子を二つに分割して
- 0000 → 00 | 00
- 0101 → 01 | 01
入れ替えます
- 0000 → 0001 (1)
- 0101 → 0100 (4)
これが新しい子供です。たいてい2つの個体から2つの子孫ができます。このままだと個体が無限に増えていってしまうので、適応度の低い 1100 と 1101 の個体には死んでもらいましょう。結果として、以下の4つの個体が生き残ります。
- 0000 (0) ←親
- 0101 (5) ←親
- 0001 (1) ←子
- 0100 (4) ←子
突然変異
突然変異(mutation)は文字通りある個体の遺伝子に突然変異を起こします。ここではどれかひとつの個体を選んで、遺伝子を1つ書き換えてしまいましょう。
- 0000 (0) → 0010 (2) に書き換え
- 0101 (5)
- 0001 (1)
- 0100 (4)
突然変異は大抵あまり良くない個体が生まれるので一見デメリットしかないように思えますが、個体の多様性が維持でき、後々良い解が出やすくなるというメリットがあるので基本的に必須の操作です*5。
これで1ステップ完了です。あとは解が得られるまで、つまり 0011 (3) の個体が誕生するまで計算を繰り返します*6。
より複雑な例
先の例は簡単すぎましたが、実際にはどのように設計すればよいのかわからないようなものであっても、「どれくらい良いか」の基準だけがあれば遺伝的アルゴリズムで解を探索できるので、以下の動画のように適当な身体と間接を与えてうまく移動できるような仮想生命体を作ったりすることができます。
まとめ
実際の生物も、どのような性質があればこの世界で上手く生き残っていけるかという正解がわからない環境でうまく適応していく必要があります。このようなときに、効率は悪いものの前提知識を必要とせずに適応していける遺伝子情報を子供に伝えて進化していくという方法はかなり強力です。
人間は脳の発達によって、後天的に獲得できる能力が非常に多いものの、たとえば反射や快・不快の基準、もっとミクロに言えばどのような神経細胞がどのような場所に配置されどう繋がるのかといったものは当然先天的なものであって、長年自然界に適応していった結果です。
人工知能、汎用人工知能を作る上でも、必ず本能に近い部分を作る必要は出てくると思われますから、このような特別な仮定をおかずに汎用的に最適解を探索できるようなアルゴリズムは少なくとも部分的には確実に必要になるでしょう。
【遺伝的アルゴリズム】
(^o^) (´・ω・｀)
＿人人人＿
＞ 選択 ＜
￣^Y^Y^Y￣
↓
(´^o^｀)
＿人人人＿
＞ 交叉 ＜
￣^Y^Y^Y￣
↓
(´へεへ`*)
＿人人 人人＿
＞ 突然変異 ＜
￣^Y^Y^Y^Y^￣
— かずー (@kazoo04) 2012, 10月 16*1:他にも遺伝的プログラミングや人工免疫システムなど色々な手法があり、総称としては進化的アルゴリズム(evolutionary algorithm, EA)や進化的計算(evolutionary computation)と呼ばれるが、ここでは遺伝的アルゴリズムだけに絞って説明する
*2:ある地点から出発して、特定の地点を1回ずつ訪問して、またスタート地点に戻ってくるようなときの最短経路を求める問題。具体的には郵便局員がすべての訪問先を回ってまた郵便局に帰ってくるような問題
*3:とはいっても主に組合せ最適化が対象になる
*4:ノーフリーランチ定理(no free lunch theorem)といって、どんな問題も完璧にできるアルゴリズムは存在せず、汎用的なアルゴリズムは幅広い問題が解ける一方で、特定の問題だけを見ればそれ専用のアルゴリズムには勝てない。万能ナイフはいろいろな状況で使えるが専用器具に比べるとどの機能も中途半端なのと似ている
*5:局所解に陥らないように探索範囲を広げる効果がある
*6:大抵はもっと複雑な問題を扱うため、どんなに繰り返し計算してもピッタリの解が得られない、またはそもそも最適解がわからないことが多いので、十分な数繰り返したら適当なところで計算を打ち切ったり、似たような個体しか生まれなくなったところで打ち切ったりする
