TOUCH THE SECURITY Powered by Security Service G
AIの分野でよく耳にする「遺伝的アルゴリズム」という言葉を知っていますか。意味は分からないが言葉は聞いたことがあるという方もいらっしゃるのではないでしょうか。
遺伝的アルゴリズムはコンピュータに遺伝のメカニズムに似た操作を取り入れることで学習させる学習方法です。今回はこの遺伝的アルゴリズムについて、どのような場面で利用されるのかや欠点まで詳しく説明していきます。
目次
遺伝的アルゴリズムとは？
遺伝的アルゴリズム（G.A.:Genetic Algorithm）とは簡単にいうと、生物の進化の仕組みを模した、最適化のためのアルゴリズムのことです。
生物の進化の過程で起きる「環境に適応し、より強い個体が生き残り、環境に適応できない弱い個体は淘汰される」という現象からヒントを得て、プログラム上で優秀な個体を次世代へと受け継ぐ仕組みが遺伝的アルゴリズムです。
この遺伝的アルゴリズムにおいて最も重要なことは遺伝子の最適な組み合わせの模索です。
遺伝的アルゴリズムにおける「組合せ最適化問題」とは？
遺伝的アルゴリズムにおける「組合せ最適化問題」を考えるうえで有名なナップサック問題というものをご紹介します。ナップサックに入れたいいくつかの候補があらかじめ用意されているとします。そして、その候補の価値と重さ、大きさなどは事前にわかっている状態で、容量に制限のあるナップサックにトータルで最も価値の高いものの入れ方を求めるという問題です。この最適な組み合わせを考える問いを「組合せ最適化問題」といいます。
このような問題でどのように効率的に組み合わせてナップサックにものを入れるかを考えたとき、膨大な計算が必要になってきます。ここで登場するのが遺伝的アルゴリズムです。
カモノハシのような新幹線N700系の先頭形状のデザインは遺伝的アルゴリズムによるもの。空力、強度、静音など複数の性能を満たすデザインを探すのが目的。
遺伝的アルゴリズムにおける遺伝子とは？
遺伝的アルゴリズムを考えるうえで「遺伝子」は必要不可欠です。遺伝的アルゴリズムにおいての遺伝子とは、パラメータや解のことです。
自動車の運転免許試験に合格する遺伝的アルゴリズムの例として考えてみましょう。自動車の運転免許試験の学科試験は「対面する信号が赤色灯火のとき、車両は必ず停車しなければならない」「対面する信号が青色灯火のとき、車両は直進、左折、右折することができる」などの超難問に○×で解答し、50問中45問を正解すると合格です。
まず、第１問から第50問までの解答を並べた「○××○×○…」と○と×をランダムに並べた「遺伝子」をたくさん作ります。そのすべての遺伝子を正解と照らし合わせて、得点を計算します。そして、成績上位の遺伝子のみ次世代に生き残るようにします。例えば、成績上位20％の遺伝子のみ生き残るようにするとか、成績に応じて生き残る確率が高くなっていくなど、具体的な手法はさまざまです。いずれの手法でも、「成績がいい遺伝子が生き残る」という点は同じです。これは生物界での淘汰や自然選択を模倣しているのです。
ランダムに生成した大量の遺伝子を評価し、成績上位のものだけが、次世代の子孫を作ることができる。上位20％を残す方法、成績がいいほど次世代に遺伝子を残す確率が高くなるなど、選択の仕方はいろいろある。
遺伝子乗り換え
生き延びた遺伝子は、自分のコピーを作って子孫を作りますが、ただコピーを作るだけでは、それ以上優秀な遺伝子は残せません。そこで遺伝子をシャッフルする仕組みとして、「遺伝子乗り換え」（クロスオーバー）という現象があります。遺伝的アルゴリズムでも、このクロスオーバーと似た仕組みを使って、遺伝子をシャッフルします。
子孫を作るときは、２つの遺伝子が父親と母親になって子孫を作ります。それぞれの遺伝子は、○と×が50個並んだ構成になっています。これがあるポイントで、そっくり遺伝子を入れ替えてしまうのです。クロスオーバーが起こるポイントは、1から50までのすべてのポイントで同じ確率で起こります。私たちの体の中では、精子や卵子といった生殖細胞を生産するときにクロスオーバーが起きています。私たちの体の細胞の中には、父親から受け継いだ遺伝子と、母親から受け継いだ遺伝子の２つがあって、生殖細胞を作るときに、クロスオーバーを起こし、シャッフルして子孫に伝えます。
遺伝子乗り換えは、２つの遺伝子がある場所以降、入れ替わってしまう現象。これで遺伝子がシャッフルされる。実際の生物でも精子や卵子などの生殖細胞を生産するときに、このようなクロスオーバーが起きている。
突然変異
クロスオーバー以外のシャッフルの仕組みに突然変異があります。突然変異とは生物体に、親の系統になかった形質が突然生じ、ある遺伝子がランダムに変わってしまう現象です。実際にはかなりの低確率でしか起こりません。しかし、まれに優秀な遺伝子に突然変異することがあります。
このようなシャッフルを行なって、次世代の遺伝子を生成し、再び採点をして、上位20％を子孫として残します。これを繰り返していくことで、何世代か後には得点が延びなくなっていきます。これが収束で解が求められるようになっています。
突然変異は、ある遺伝子が小さい確率で変化してしまう現象。現実の生物では、他の遺伝子に変わるというより、今まで存在しなかった遺伝子に変異することで、遺伝的な多様性を高めることに寄与している。
遺伝的アルゴリズムにおける欠点
遺伝的アルゴリズムは最適解を模索するための効率的なアルゴリズムである一方で、いくつかの欠点も知られています。
過剰適応
1つ目の欠点に「過剰適応」があります。過剰適応とはある水準以上の解を求めようとしたとき、偶然その水準に近い解を求められた場合、その求めようとする水準以下で解が収束してしまうことです。
例えば、先ほどの運転免許試験を例に挙げると、免許試験で90点以上取れる遺伝子が欲しいのに、初期段階で偶然80点ぐらい取れる遺伝子があると、この遺伝子は生き残りやすいので、集団の中で拡散していくことになります。すると、かなり早い段階で80点程度が取れる状態に収束してしまうことがあるのです。
つまり過剰適応は最初にそこそこ優秀な個体がある程度いる集団は伸び悩んでしまうということです。それよりも、かなり優秀な個体から劣等な個体までバラエティに富んでいる方が、最終的に優秀な結果をもたらすのです。遺伝的な多様性は優秀な子孫を残すためには重要であるといえます。
ヒッチハイク問題
2つ目の欠点に「ヒッチハイク問題」があります。ヒッチハイク問題とは、生物が交配によって子孫を残すことをモデル化したものにおいて、最適解の生成を妨げる遺伝をしてしまうことです。
例えば、ある３つの遺伝子が端のふたつは正解なのに、真ん中が不正解という場合、この不正解の遺伝子は、周りの正解遺伝子に守られて、なかなか淘汰されません。うまいこと、不正解遺伝子の前後でクロスオーバーが起こるか、突然変異が起こるかという確率の低い事象に期待するしかありません。不具合を完全に除去できないという、遺伝システムのバグや不具合のように思えますが、ひょっとしたらこれも遺伝的多様性を保障する何らかの意味がある仕組みなのかもしれません。
最適解が○×○の時、○○○という遺伝子は両端が正解だが、真ん中は不正解になる。この真ん中の不正解の遺伝子はなかなか淘汰されない。両端の正解の遺伝子に守れれて、次世代に伝えられてしまうからだ。まるでヒッチハイカーのように、タダ乗りを続けるのだ。
まとめ
遺伝的アルゴリズムはいくつかの欠点もありますが、優秀な子孫を残すため、つまり最適解を導くための効率的な学習方法です。日常生活においてもさまざまな場面で最適解を考える、遺伝的アルゴリズムを用いる場面が多くあります。
遺伝的アルゴリズムはアイデア次第でさまざまなものに応用できます。どんな問題に遺伝的アルゴリズムを応用できるか、ぜひ一度考えてみてください。
遺伝的アルゴリズムを用いて、道路をうまく走れる車を自動生成させる例、半透明の図形を重ね合わせてモナリザの絵画を再現する例を紹介。
