Global Information site~siruzou

遺伝子アルゴリズムとは?~難問を解く鍵は実は生命の進化にあった!

2014.04.20

遺伝子アルゴリズムとは?~難問を解く鍵は実は生命の進化にあった! はコメントを受け付けていません

人間の頭脳で考えても、そう簡単に答えの出せない問題があったとして、あなたならどうしますか? 

コンピューターに任せることができれば、それが簡単です。しかしコンピューターに問題を解かせるならば、解き方を教えなければなりません。

その解き方のひとつとして、生命が進化するかのように、理想的な答えを探る方法があるのです。あらゆる分野に応用可能なこの方法は「遺伝的アルゴリズム」と呼ばれています。

うまく使えば、あらゆる分野に応用可能なこのアルゴリズムは、新幹線の「顔」とも呼べる、先頭車両を設計したことでも話題となっています。実際、どのような考え方なのでしょう?

必要になった理由とは?

そもそも遺伝的アルゴリズムという手法は、なぜ必要になったのでしょう?

スポンサーリンク

よく引き合いに出されるのは「巡回セールスマン問題」です。セールスマンが、複数ある地域を効率よく巡る順番を導き出すという問題であり、そう簡単には答えを出せません。

No18-2-022画像02

地域が4つや5つなら手計算でも充分可能ですが、これが1000や2000という大きな数になると、コンピューターでさえ計算が困難になるのです。

最適な答えを導き出すことが困難な問題を、効率よく解決する方法を「アルゴリズム」と呼びます。アルゴリズムを利用すれば、スーパーコンピュータを使って数万年かかるような難問であっても、現実的な時間で答えを出すことができるのです。

遺伝的アルゴリズムは、そのうちの一つとして考えだされました。生命の遺伝子のように答えを組み上げていくことから、このような名前が付けられています。

私たち人間は、その体にいくつかの欠点を抱えている場合があり、完全な状態とはいえません。このアルゴリズムも同様に、導き出された答えは完璧でない場合があります。

しかし、その汎用性には目を見張るものがあり、あらゆる分野に応用の効く手法でもあります。

遺伝的アルゴリズムの仕組み

「遺伝的」と呼ばれているとおり、生命が遺伝子を残し育てていくようにそっくりです。例として「効率的な訪問販売の方法」を遺伝的アルゴリズムで作ってみましょう。ちなみに、非現実的なので真似はしないほうが良いと思われます。

はじめに、手当たりしだいに訪問し、デタラメなセールストークを行います。デタラメなので良い結果にはなりませんが、構わずやりましょう。

二番目に「評価」を行います。トークの結果に対し、優劣をつけるのです。

数多くこなした訪問の中で、より食いついたトークを選び出します。見込みのないトークは忘れましょう。生命の進化の過程でいえば淘汰に当たります。

スポンサーリンク

三番目に「交叉」を行います。選び出したトークを混ぜあわせて、新しいトークを構成します。いわば交配に当たります。新しいトークはたくさん用意し、再び訪問を行ったあと、二番目から繰り返します。

現実の生命と同じく、これを数世代繰り返すと(場合によっては数百、数千世代も繰り返します)じょうずな訪問販売の方法が確立できているはずです。

ここまで説明した方法ですが、実は一つ重要な要素が欠けています。

現実の生命には「突然変異」があります。遺伝的アルゴリズムにおいても突然変異は重要なのです。今回の例で言えば、三番目の「選び出したトークを混ぜあわせて、新しいトークを構成」する時に、低確率でデタラメなトークを行います。

これがない場合、よくある教科書的なトークに収まってしまい、新しい手法を生み出せないという状況に陥りやすくなります。初期収束と呼ばれる、遺伝的アルゴリズムの弱点でもあります。

以上、「評価」「交叉」「突然変異」の3点が、遺伝的アルゴリズムにおいて必要な項目となります。これらのさじ加減が結果へ繋がります。

遺伝的アルゴリズムの実用例

No18-2-022画像03

遺伝的アルゴリズムを応用した例としてもっとも有名なものといえば、新幹線N700系の「顔」の部分でしょう。トンネルを抜け出した時に発生する轟音を、可能な限り低下させるための最適な形を創りだしたのは、この方法なのです。

ほぼ無限にあるパターンの中から、最適な形を見つけ出すことに向いている手法と言えます。

先ほどのセールストークについては、あまり現実的ではありませんが、ビジネス面ではインターネット上のバナー広告や、最適な広告文の作り方などに、実際に応用されているようです。

現在は、個人で高性能なパソコンを使うことができますので、思いつく限りのことが可能となっています。下記で紹介しているのは、個人で行われた遺伝的アルゴリズムの使用例です。

人の動きを覚えさせる

物理演算ソフトにより、人型ロボットに「ハイハイ」をはじめ、さまざまな運動を覚えさせようと試みたのは「むにむに教授」です。

No18-2-022画像04

ハイハイで重要なのは、前進する速度であると結論付け、「速度が速い」個体を選び進化させ続けました。その結果によると、ハイハイは前後逆になって進んだ方が速いらしいです。

現実的には、前が見えないという欠点がありますので「速度が速い」上に「前を向いて移動する」個体を選んで進化させると、また違う結果になるかもしれません。

ゲームを攻略させる

スーパーマリオブラザーズやグラディウスを、遺伝的アルゴリズムに任せてクリアしたという方もいました。

No18-2-022画像05

印象的なのは、マリオが無意味なジャンプを繰り返している点です。直接的に評価されない部分には、多くの無駄な動きが残るわけです。

現実でも、命の生存に関係しない部分などが遺伝子から消え去らずに残っています。たとえば「薄毛」は多くの人にとって悩みの種ですが、子孫を残すことには関係しないようで、恨めしくも遺伝子に刻まれてしまっているわけです。

その他への応用は?

遺伝的アルゴリズムは「評価」「交叉」「突然変異」の3点に掛かっており、これらをうまく設定可能であれば、あらゆる分野で応用することができます。

上で示したような例のほかにも、投資に役立てたりされている方もいるようで、発想次第では何でも解決できる…かもしれません。

byヒビタカ

スポンサーリンク

この記事を読んだ人はこんな記事も読んでいます
Pocket
LINEで送る

関連記事

コメントは利用できません。

知る蔵のTwitter~フォーローをお願います

知る蔵グループ関連専門サイト