ある解決すべき問題があり、それを解くために生物の進化の考え方を取り入れたのが遺伝的アルゴリズムです。
上下左右に動けるネコを操作し、障害物をよけながら、ゴールであるりんごの所まで到達させるという問題を設定して、これを解く遺伝的アルゴリズムを教育向けプログラミング環境として人気のあるScratch(*1)で実装します。
こども向けと侮るなかれ、Scratchでも高度なプログラミングができるということを紹介したいと思います。また、「遺伝的アルゴリズム」と聞いて「難しそう」と思われる方もいるかもしれません。ですが、Scratchなら、ロジックの部分が例えば「もし〜なら」のように日本語で読むことができるので、プログラミングの素養がなくても、本稿の解説を読みながらScratchのコードを追っていくだけでも「遺伝的アルゴリズム」がどのようなものなのかが何となく分かってくるのではと思います。
実際に動くScratchのプロジェクトは
で公開しております。これを動かしながら、解説を読むだけでも良いですし、「リミックス」して自分で少しいじってみるとより理解が深まると思います。あるいは、次章からの解説を参考にしながら、まったくゼロから新しいプロジェクトを作っていくのも良いでしょう。
動かすときは、シフトキーを押しながら緑の旗をクリックする「ターボモード」で実行してください。通常モードだと、処理に長い時間がかかってしまいます。
実行している様子を早回しにして撮った動画がこちらです。
最初はランダムに動いていたネコが、次第に進化していき、障害物を避けながら最後にはりんごに確実に到達するようになります。下の方に表示されている青いグラフは、りんごからの距離の平均をとったもので、世代が進むに従いその値が小さくなって進化している様子を表しています。
*1 Scratch はMITメディアラボ（MIT Media Lab）のライフロング・キンダーガーデン（Lifelong Kindergarten Group）により開発されました。参照： http://scratch.mit.edu