TOUCH THE SECURITY Powered by Security Service G

コラム

2018.10.02

4枚の図解でわかる遺伝的アルゴリズム

寒さに強い稲を作るには、田んぼの水の取り入れ口にある稲から種籾を取るということを繰り返します。冷たい水にさらされ、寒さに強い稲を次世代に残す。これを何世代も繰り返していきます。

実はコンピュータの世界でも、同じようなアルゴリズムが存在します。遺伝子に相当するようなデータ構造を大量に作り、評価をし、高得点のものだけを次世代に残して子孫を作らせ、高速に何世代も繰り返して、優秀なデータ構造に進化させる。これを遺伝的アルゴリズムと呼びます。

1.遺伝的アルゴリズムが用いられる場面 ――組合せ最適化問題

「遠足のおやつは300円以内」という制限の中で、どのお菓子を何個持っていけば糖分を最大化できるのか、などといったことを考える際には、様々なお菓子の組合せのから最適な解を探る必要があります。いわゆる、「組合せ最適化」と呼ばれる問題です。

カモノハシのような新幹線N700系の先頭形状のデザインは遺伝的アルゴリズムによるもの。空力、強度、静音など複数の性能を満たすデザインを探すのが目的。

とは言え、遠足のおやつぐらいでは計算するまでも無いのですが、例えば大規模土木作業において、建設機器をどのように効率的に組み合わせて利用するかといった問いになると、果てしなく膨大な計算が必要になってくるはずです。このようなとき、100点の結果は得られないけど、そこそこ使える結果を短時間で導きたい。そんな時に登場するのが遺伝的アルゴリズムです。

ここでは例として、自動車の運転免許試験に合格する遺伝的アルゴリズムを考えましょう。

2.遺伝子のピックアップ

自動車の運転免許試験は「対面する信号が赤色灯火のとき、車両は必ず停車しなければならない」「対面する信号が青色灯火のとき、車両は直進、左折、右折することができる」などの超難問に○×で解答し、50問中45問を正解すると合格です。(ちなみにこの2問は、いずれも×が正解。緊急車両は停車しなくてもいいので「必ず」ではありません。車両といっても自転車などの軽車両は交差点を右折できず、二段階右折をしなければなりません)。

まず、第1問から第50問までの解答を並べた「○××○×○…」と○と×をランダムに並べた「遺伝子」をたくさん作ります。そのすべての遺伝子を正解と照らし合わせて、得点を計算します。そして、成績上位の遺伝子のみ次世代に生き残るようにします。例えば、成績上位20%の遺伝子のみ生き残るようにするとか、成績に応じて生き残る確率が高くなっていくなど、具体的な手法はさまざまです。

いずれの手法でも、「成績がいい遺伝子が生き残る」という点は同じです。これは生物界での淘汰や自然選択を模倣しているのです。キリンの首はなぜ長い。首の長さは個体によって違うけど、首が長いキリンの方が高い木の葉を食べることができ、生き延びる確率が増え、子孫を作る確率が高くなるというものです。

ランダムに生成した大量の遺伝子を評価し、成績上位のものだけが、次世代の子孫を作ることができる。上位20%を残す方法、成績がいいほど次世代に遺伝子を残す確率が高くなるなど、選択の仕方はいろいろある。

3.遺伝子乗り換え ――クロスオーバー

生き延びた遺伝子は、自分のコピーを作って子孫を作りますが、ただコピーを作るだけでは、それ以上成績があがっていきません。そこで遺伝子をシャッフルする仕組みとして、「遺伝子乗り換え」(クロスオーバー)という現象があります。遺伝的アルゴリズムでも、このクロスオーバーと似た仕組みを使って、遺伝子をシャッフルします。

子孫を作るときは、2つの遺伝子が父親と母親になって子孫を作ります。それぞれの遺伝子は、○と×が50個並んだ構成になっています。これがあるポイントで、そっくり遺伝子を入れ替えてしまうのです。クロスオーバーが起こるポイントは、1から50までのすべてのポイントで同じ確率で起こります。

私たちの体の中では、精子や卵子といった生殖細胞を生産するときにクロスオーバーが起きています。私たちの体の細胞の中には、父親から受け継いだ遺伝子と、母親から受け継いだ遺伝子の2つがあって、生殖細胞を作るときに、クロスオーバーを起こし、シャッフルして子孫に伝えます。

遺伝子乗り換えは、2つの遺伝子がある場所以降、入れ替わってしまう現象。これで遺伝子がシャッフルされる。実際の生物でも精子や卵子などの生殖細胞を生産するときに、このようなクロスオーバーが起きている。

もうひとつのシャッフルの仕組みが突然変異です。突然変異は、ある遺伝子がランダムに変わってしまう現象です。現実の世界では非常に小さな確率でしか起こりません(さらに、多くの突然変異は生物にとって不利な変化をもたらすので、生殖細胞の段階で死滅するなどして、ほとんどの場合、子孫を残すことができません)。

このようなシャッフルを行なって、次世代の遺伝子を生成します。そして、再び採点をして、上位20%を残して、さらに子孫を残す。これを繰り返していくと、何世代後かには得点が延びなくなっていきます。これが収束で、解が求められるようになっています。自動車の運転免許の例で言えば、合格点の90点を突破するようになっているはずです。

突然変異は、ある遺伝子が小さい確率で変化してしまう現象。現実の生物では、他の遺伝子に変わるというより、今まで存在しなかった遺伝子に変異することで、遺伝的な多様性を高めることに寄与している。

4.遺伝的アルゴリズムにおける欠点 ――過剰適応

このような遺伝的アルゴリズムにもいくつかの欠点、問題点が知られています。

ひとつは過剰適応です。免許試験で90点以上取れる遺伝子が欲しいのに、初期段階で偶然80点ぐらい取れる遺伝子があると、この遺伝子は生き残りやすいので、集団の中で拡散していくことになります。すると、かなり早い段階で80点程度が取れる状態に収束してしまうことがあるのです。

富士山の山頂を目指して、目の前の坂を登って行ったら、高尾山にたどり着いてしまい、降りるに降りられなくなってしまったような話です。

最初にそこそこ優秀な個体がたくさんいる集団は伸び悩んでしまう。それよりも、超優秀から超ダメまでバラエティに富んでいる方が、最終的には良好な結果をもたらす(ただし、過酷な淘汰が必要になりますが)。遺伝的な多様性が集団にとって重要だというのは、現実の生物の世界でも、遺伝的アルゴリズムでも同じなのです。ひょっとしたら、企業という集団でもそうなのかもしれません。

5.遺伝的アルゴリズムにおける欠点 ――ヒッチハイク問題

もうひとつの問題点は、ヒッチハイク問題です。

例えば、ある3つの遺伝子が端のふたつは正解なのに、真ん中が不正解という場合、この不正解の遺伝子は、周りの正解遺伝子に守られて、なかなか淘汰されません。うまいこと、不正解遺伝子の前後でクロスオーバーが起こるか、突然変異が起こるかという確率の低い事象に期待するしかありません。不正解の遺伝子は、周りの優秀な遺伝子にタダ乗りするようにして、子孫に受け継がれてしまいます。

これも実際の生物にも起きていることです。私たち人間は、致死性の遺伝子を平均して3個から4個持っているという説があります。なぜそれで生き延びることができているのかというと、父親から致死性遺伝子を受け継いでも、母親から良質の遺伝子を受け継いでいるからです。

不具合を完全に除去できないという、遺伝システムのバグや不具合のように思えますが、ひょっとしたらこれも遺伝的多様性を保障する何らかの意味がある仕組みなのかもしれません。

最適解が○×○の時、○○○という遺伝子は両端が正解だが、真ん中は不正解になる。この真ん中の不正解の遺伝子はなかなか淘汰されない。両端の正解の遺伝子に守れれて、次世代に伝えられてしまうからだ。まるでヒッチハイカーのように、タダ乗りを続けるのだ。

6.遺伝というアルゴリズムの応用

遺伝的アルゴリズムは私たちの日常感覚にも馴染みやすいものです。休みの日に「クリーニングを受け取る」「スーパーで牛乳を買う」「郵便局で荷物を発送する」という3つの仕事を1度の外出で片付けたい時、どの経路で回ると効率的か、それと同時に大きな荷物を持って歩くのをできるだけ短くするにはどうしたらいいか。これはかなり難しい問題なのですが、さほど考えることもなく用事を済ませられます。

それは日頃から近所で用事をすませて試行錯誤をして、その小さな試行錯誤を何世代も繰り返しているので、頭の中に最適解の近似解のようなものができあがっているからです。

遺伝的アルゴリズムは、アイディア次第でさまざまなものに応用できます。どんな問題に遺伝的アルゴリズムが応用できるか。ぜひ考えて見てください。

遺伝的アルゴリズムを用いて、道路をうまく走れる車を自動生成させる例、半透明の図形を重ね合わせてモナリザの絵画を再現する例を紹介。

記事一覧に戻る