非エンジニアでも直感的にわかる「遺伝的アルゴリズム」とは？ ｜ SiTest (サイテスト) ブログ

以前のエントリ、『人工知能の基本。文系人間向けアルゴリズム解説「逐次検索」とは？』では誰もが普段の生活で使っているアルゴリズム、「逐次検索」について説明しました。
このエントリだけ読むと、「アルゴリズム」ってなんて単純で簡単なんだ、と思った人もいるかもしれませんが、アルゴリズムにもわかりやすいのもあれば、数学的な知識があって初めて理解できるものもあります。
今回のエントリは、同じく直感的にわかりやすい「遺伝的アルゴリズム」について解説します。

遺伝は、親から子へとに形質が伝わるという現象のこと

とWikipedia
には解説されています。

「遺伝的アルゴリズム」は、生物界の進化の仕組みをシミュレーションするようにテストを繰り返す探索方法として、1975年に考案されました。
発案したのはミシガン大学のジョン・H・ホランド。
探索の手順を「偶然の変化」と「たまたま良く出来たものを採用」という、まるで運任せのような手順で行なうため、最初は「はたしてこのような方法がアルゴリズム（計算手順）と呼べるのか？」批判を受けたとも言われます。
言ってみればトライ＆エラー（淘汰と進化）をシミュレーションするという力任せの方法ですので、実際の探索には膨大なリソースを使うことにもなりかねないからです。
しかし、1990年代に入り「遺伝的アルゴリズム」は人工知能の主要分野に採用され、世界中で研究が行なわれるようになりました。
その背景にはコンピュータの性能の飛躍的向上があります。
地球に生命が誕生してヒトに到達するまで、40億年の時間がかかっていますが、「遺伝的アルゴリズム」は生物の進化と同様に、非常に多くの繰返しが必要だったのです。

遺伝的アルゴリズムの説明には、直感的に理解しやすい動画が多数公開されていますので紹介します。

動画出典：How Do Genetic Algorithms Work? | Two Minute Papers（YouTube）

この画像で紹介されているBoxCar 2Dという研究は、定められたコースをできるだけ先まで進めるクルマを自動で生成するという目的に遺伝的アルゴリズムで挑んだもの。

三角とタイヤで形作られた「クルマ」をコンピュータが作成、最初のうちはランダムに生み出されるのでタイヤの位置がめちゃくちゃで接地面を考えていないようなものが多数出てきます。
初期設定では1世代で20個の個体が生み出される設定なので、「たまたまうまくいった」いくつかをもとに、次世代が生み出されていきます。
何世代化すると、タイヤの配置もそれらしい、「クルマ」と呼べそうなものが増えてきます。

タイヤすらないもの、まともに走ることができず壊れてしまうのものをいくつも生み出し、そのうち上記の図のように走行距離がだんだん伸びてくる個体が増えてくることがわかります。

もう一つの事例として挙げられているのがGenetic Programming: Evolution of Mona Lisa。

50種類の半透過色のポリゴンを使い、遺伝的アルゴリズムで名画「モナ・リザ」を再現するという実験です。

最初はほとんど絵画として成り立っていない画像が・・・

世代を重ねることでだんだん「モナ・リザ」が浮かび上がってくるようになります。

他にも人工知能が試行錯誤し「スーパーマリオワールド」をプレイする動画や、

動画出典：MarI/O – Machine Learning for Video Games（YouTube）

ガンダムの3Dモデルを遺伝的アルゴリズムを使って歩かせることに挑戦する動画が公開されています。

動画出典：ガンダムを遺伝的アルゴリズムで歩かせた。walked the Gundam By genetic algorithm（YouTube）

遺伝的アルゴリズムの最大の特徴として、優れた解法が存在しておらず、全検索が不可能と思われる問題に対して非常に有用です。
まさに現在の「答えのないものに対して最適な解を見出そうとする」人工知能のアルゴリズムとして注目を集めています。
進化によって問題の答えを導き出す、というと人知を超えた存在が誕生したようにも感じますが、WEBマーケティングにおけるABテストも淘汰と世代を重ねるという部分において非常に似ています。
現在のマーケティングの現場では前述の実験のように並行して多数のサンプル、世代を重ねることは時間的にも、コスト的にも難しいですが、いつかWEBマーケティングのおいても人工知能がシステム上でシミュレーションしてくれる時代が訪れるに違いありません。