「遺伝的アルゴリズム」がどのような仕組みなのかが2分でわかるムービー

by fdecomite

複数の個体の中から、適応度の高い個体を優先的に選んで組み換え・突然変異などを繰り返し、解を探索していく「遺伝的アルゴリズム」がどういう仕組みなのか、2分で説明したムービーがYouTubeで公開されています。

Two Minute Papers - How Do Genetic Algorithms Work? - YouTube

これは、物事を2分間で説明する「Two MinutePapers」というYouTubeのムービーシリーズの1本で、Károly Zsolnai-Fehérさんが作ったもの。

ムービーの中でわかりやすい事例としてあげられているのは、「できるだけ既定のコースを進める車を自動で生み出す」という目的を遺伝的アルゴリズムでやってみるというBoxCar2D。

三角形といくつかのタイヤをつけた「車」をコンピューターが生成、できるだけ先へ進むことを目指します。しかし、最初のうちはランダムなので、タイヤがなくて前へ進むことができない、車と呼べないようなものも生まれます。

時には、こうやってうまく走るものが誕生します。デフォルトだと1世代で20の個体が生まれる設定で、遺伝的アルゴリズムにより、この上手く走れた「車」をいくつかもとにして、次の世代を生み出していきます。

なので、10世代ほど重ねると、このようにいかにも走れそうなものが生まれてきました。自然界の進化と同じようなものです。

4つの個体を用いてモデル化したものがこの図。

優れた結果を残した3つの個体をもとに次の世代を生み出します。

生物でいうと交配して子孫を残す工程がオレンジ色の矢印で示した「組み換え」で、2つの個体の要素を入れ替えます。これを繰り返すと局所的最適解に収束してしまうため、生物の遺伝子が突然変異するのと同じような「突然変異」も行われます。これは赤矢印で示したもので、左から右に突然変異することで0と1が入れ替わってしまっている部分があります。突然変異の確率を高めるとランダムに解を探索するのと同じになってしまうので、確率は高くても数％にするとのこと。

Zsolnai-Fehérさんが挙げたもう1つの事例は、ロジャー・ヨハンソン氏による「Genetic Programming: Evolution of Mona Lisa」。これは、50個の半透過のポリゴンだけを使った遺伝的アルゴリズムでモナ・リザを再現できるかという試みです。画面左がアルゴリズムで生み出された「モナ・リザ」、右が目指す「モナ・リザ」。だいたい1200～1300世代だと、ぼんやりと色の位置は合っているかな、というレベルですが……

1万2000世代を重ねると幾何学模様の中にモナ・リザの姿が浮き上がってきている気がします。

ちなみに、ヨハンソン氏によれば、90万世代ほどかければほぼモナ・リザっぽい絵が作れるそうです。

遺伝的アルゴリズムを知りたい人のためにZsolnai-Fehérさんが挙げた参考書籍は、「利己的な遺伝子」で知られるリチャード・ドーキンスの著作「The Blind Watchmaker」。「盲目の時計職人」の題で翻訳されていて、Amazonなどで入手可能です。

盲目の時計職人 | リチャード・ドーキンス, 日高 敏隆, 中島 康裕, 遠藤 彰, 遠藤 知二, 疋田 努 | 本 | Amazon.co.jp