進化を利用した不思議なアルゴリズム?遺伝的アルゴリズムについて解説
2022-05-16
azblob://2022/11/11/eyecatch/2022-04-07-ascii-blog-orientation-000.jpg

皆さんこんにちは。新卒で入った前田です。今回での記事では、私が在学していた当時研究していた、遺伝的アルゴリズムというものについてざっくりと、できるだけわかりやすく、説明していこうと思います。

遺伝的アルゴリズムってなに?

ざっくり言うと、「進化」を利用したアルゴリズムです。 …...ざっくりしすぎですかね。 でも遺伝的アルゴリズムというのは、この進化の仕組みさえわかってしまえば案外簡単に理解できちゃうんです。 それじゃあ進化の仕組みについて説明しよう!...といきたいところですが、その前に皆さんにはまず遺伝子というものについて理解してもらう必要があります。

まずは遺伝子について... 

遺伝子とは、その個体がどのような性質かを記した配列のことです。 簡単に例えると設計図みたいなものですね! 遺伝子の情報は個体それぞれで異なります。つまり遺伝子次第で同じ種でも個体差が出るというわけです(遺伝子がまるっと同じだと個体もまるっと同じものが出来上がります。これが所謂クローンってやつです!) 。また、個体の遺伝子はその個体の親の遺伝子によって左右されます。これは子の遺伝子は親のものを引き継いで生まれてくるというルールがあるためです。親が2体であれば、2体それぞれの遺伝子が混ざったものを引き継ぎます。これが遺伝子の名前にもある「遺伝」です。

進化の仕組み

遺伝子について理解を深めたところで、進化についての説明に入ります。まず進化とは、既存の種(ある基準によって区分けされた個体群)が世代を経て、形質を変化させていく現象のことです。この現象は種が生息する環境や外的要因によって発生します。

例えば、キリン。キリンの先祖はもともと首は短く、体も小さい種でした。しかし彼らの住んでいた環境では、エサである葉が高所にあったため、なかなか餌にありつける機会がありませんでした。そんな環境に適応するため、彼らの種には上述の進化が発生します。高所の餌を食べるという目的のために首はぐんぐんと伸び、体も立派な大きさになりました。その果てがキリンというわけです。

(これは数ある説の中の一つであり、太く長いほど同種にモテる説、突然変異が環境に適応した説など、様々な説があります。)

さて、進化が発生する理由はわかりました。...では進化によって形質はどんな仕組みで変化したのか?そうです、ここで上述した遺伝子が関わってきます。

先ほどのキリンの例を用いると、「種全体と比べて首が短い」という情報の遺伝子を持つキリンは「餌が高所にある」という環境に適応できず死んでいきます。逆に「種全体と比べて首が長い」という情報の遺伝子を持つキリンは、環境に適し生き残っていきます。生き残った首の長いキリンたちが子を成すと、遺伝のルールによって、子の世代のキリンには親世代よりも「種全体と比べて首が長い」という遺伝子を持ったキリンが多くなります。この淘汰と交配が何世代にも渡って繰り返されていくと、環境に完全に適応した首の長さを持った現在のキリンになるのです。

以上をまとめると進化という現象は、環境に適応するという目標の設定と、そこに到達するための淘汰と交配のサイクルで構成されています。

突然変異

実は進化にはもう一つ重要なファクターがあります。それは「突然変異」です。

突然変異とは、遺伝子の引継ぎの際に起こるエラーのようなもので、親に無かった遺伝子が発生する現象のことです。これ、一見すると意味の無いように見えますが、ちゃんと発生する理由があります。

実は、種の進化の途中で遺伝子が環境に完全に適応した形になる前に、その世代で遺伝子情報が一様になり、進化が停滞してしまうことがあります。これを打開するのが突然変異です。突然変異により新たな遺伝情報が進化のサイクルに交じり、遺伝子情報が多様化し、停滞が防がれます。

突然変異はエラーでありながら、進化という現象に必須とも言うべきものなのです。

進化と遺伝的アルゴリズム

お待たせしました。遺伝的アルゴリズムについて説明していきましょう。

上記の説明では、 "「進化」を利用したアルゴリズム"とざっくり書きましたが、さらに詳細にいうなれば

"データを遺伝子情報で表し、進化を適用して最適化を図るアルゴリズム"

です。

環境への適応評価値、遺伝子情報を数値で表し、遺伝子へ

  • 評価(適応評価値と遺伝子の比較)
  • 淘汰
  • 交叉(交配)
  • 突然変異

の操作を繰り返し行います。これにより、最終的には適応評価値に近づいた遺伝子のデータが生成されるのです!

応用

遺伝的アルゴリズムを応用した身近なものとしては、

  • 新幹線の先頭車両の形状
  • カーナビの最短経路の選択

などがあります。さらにはゲームに適用して自動でクリアさせることも...!(YouTubeで"マリオ 遺伝的アルゴリズム"で検索)

まとめ

今回は遺伝的アルゴリズムについて説明していきました。以外と単純ながら面白いアルゴリズムなので、興味のある方は実装してみてくださいませ!