遺伝的アルゴリズムの各要素を解説していきます。
「はじめに」にも書きましたが、生物の進化の考え方を取り入れたのが遺伝的アルゴリズムです。
ゴールであるりんごに向かってネコを動かすのですが、そのひとつひとつの動きをアルファベット一文字で表します。上はUPの頭文字を取ってU、下はDOWNの頭文字D、右はRIGHTの頭文字R、そして左はLEFTの頭文字Lです。これら4つのアルファベットをつなげてネコの動きを表します。たとえば、DDDULDRDLURUであれば、ネコは下・下・下・上・左・下・右…（以降略）のように動くのです。
一方遺伝子の本体であるDNAはアデニン (A) とチミン (T)、グアニン (G) とシトシン (C)の4つの塩基が連なっている構造をしていることが知られています。(*1)たとえば、ATTAGCCGACCAという具合です。ネコの動きを表す文字列を遺伝子とみなし、生物の進化の考え方を取り入れてこの遺伝子を操作していくのが遺伝的アルゴリズムです。
環境の変化などに対応できた種が生き残って次の世代にその遺伝子を残すと考えられており、これを「自然淘汰」あるいは単に「淘汰」と呼びます。たとえば、脚が速いものだけが天敵から逃げ延びることができた、あるいは獲物をつかまえることができて飢えないで済んだから、草食動物も肉食動物もある程度脚が速いように進化してきた。あるいは自分の体の色や形を変化させたり、硬い殻を持つように進化してきた生物もいたりするという具合です。
本稿の例では、りんごを食物とみなして、この食物に到達できた、あるいはより近くまで移動できたネコが生き残り、次の世代にその遺伝子を残せると考えるようにします。
ネコが次の世代に遺伝子を残すとき、単に優秀だった遺伝子の完全なコピーを残すのではなく、生物がそうなっているように、父親と母親の遺伝子の両方からそれぞれの一部を引き継ぐようにします。
また、それほど頻繁には起こらないのですが、突然変異で遺伝子の一部が全く違うものに変わってしまうという要素も取り入れています。
このようにして生物の進化を取り入れて、ネコを何世代にも渡って進化させていくと、そのうちに段々と獲物であるりんごに近づくことができるようになり、最後にはりんごに到達することができるようになります。
無限に猿にランダムにタイプライターをタイプさせているとそのうちシェイクスピアの作品を打ち出すことができる(*2)という例のように、ネコを上下左右にランダムに動かせば、そのうちりんごに到達することはできます。ですが、その場合途方も無い組み合わせを試す必要があり、とても長い時間がかかってしまいます。遺伝的アルゴリズムを使えば、ネコをりんごのもとにたどり着かせるという課題をもっと効率よく解決することができます。
次章より、いよいよScratchで実装した遺伝的アルゴリズムを解説していきます。
を開き、右上の「中を見る」ボタンをクリックして、コードを見ていきましょう。