#04 遺伝的アルゴリズムについて

第4週。

今週は忙しかったので、プロジェクトできず。遺伝的アルゴリズムについて調査しました。

遺伝的アルゴリズムとは？

まず、遺伝的アルゴリズムについて。

遺伝的アルゴリズムは、問題の最適解を探索する手法のひとつで、生物が世代を重ねるごとに徐々に環境に適応していく様子を模しています。主に、以下の三種類の操作によって、多様な解を生み出しながら、より「強い」解を選別していきます。

1. 選択

強者が生き残り、弱者は淘汰される。それが自然の摂理です。アルゴリズム上では、より効果的な解を親として残し、次の世代を算出することで自然淘汰を再現します。

2. 交叉

解の一部を別の解と入れ替えます。生物の交配と同じです。強い遺伝子と強い遺伝子からさらに強い遺伝子が生まれたり、逆に弱い遺伝子が組み合わせによって強くなることもあるでしょう。

3. 突然変異

ランダムに解の一部を変更します。偶然にたよって、親世代にはない特徴をもった解が生みだすため、より広い可能性を探索することができます。

非常にシンプルなルールですね。しかし、この自然が何世代もかけて、我々が目にする動植物たちを形作ってきたことを考えてください。説得力が違います。

どこで使える？

実際に、ゲームなどで遺伝的アルゴリズムが使われていることもあるようです。親を引き継ぎつつ、ランダムな要素を入れ込みたい場合にはいいかもしれません。参考にした書籍「ウェブ最適化ではじめる機械学習」では、好みのピクセルアートを数世代にわたって生成するデモが掲載されています。#03 Droamにも遺伝システムを導入したいと思っています。

「強さ」の尺度さえ決まっていれば、いろいろな場面で役に立つのではないでしょうか。

なんでもいいんですが、たとえば、より「使いやすい」バッグを作りたいとします。実際にそのバッグを10タイプ用意して、使ってもらった感想から、使いやすいもの上位4タイプを親として次の世代を作ります。この世代は、親世代を受け継ぎつつ、特徴が組み合わさっていたり、新しい要素が追加されていたりすることでしょう。そのなかには、親世代より使いやすくなったバッグもあるかもしれません。このように世代を積み重ねていけば、当てずっぽうに探すよりもずっと早く、かつ多様な選択肢を模索しながら最高のバッグに辿り着けます。

まとめ

自然は偉大です。科学は日々進歩しているとは言え、まだまだ学ぶことは多いでしょう。自然法則を注意深く観察し、活用することは簡単ではありませんが、数億年の歴史の中で育まれてきたシステムです。参考にしないわけにはいきません。遺伝的アルゴリズムは、生物の遺伝を模したシンプルなアルゴリズムですが、使い方によってはその効果は絶大です。

今後のプロジェクトでどのように取り入れられるか、さらに研究を重ねたいと思います。

参考

飯塚修平 ウェブ最適化ではじめる機械学習 O'REILLEY JAPAN