BlankTar

about | blog | works | photo

遺伝的アルゴリズムっていいよね。やばいよね。浪漫だよね。
という訳で、解説記事です。

次回は(覚えてれば)pythonでの遺伝的アルゴリズムのやりかたとか書くよ。

追記:次回書きました。
pythonのpyevolveで遺伝的アルゴリズム。

遺伝的とは

生き物には遺伝子ってのがあって、良い遺伝子は淘汰されて生き残っていく。
っていうのはまあ、ご存知のところだと思います。
こいつをコンピューター上でもやろうぜ、ってのが遺伝的アルゴリズム。

手順としては、
  1. 大量の遺伝子をランダムに作る
  2. 良い遺伝子を幾つか選ぶ
  3. で、その遺伝子を
    • 交叉させる
    • 優秀な遺伝子同士を組み合わせる。
      つまりは次の世代に子孫を残すってこと。
    • 突然変異させる
    • そのまんまの意味で突然変異っす。
    • 生き残らせる
    • 優秀な遺伝子を次の世代にそのまま残す事もあります。やらないこともある。
      エリートって言います。
  4. 作った遺伝子で世代交代させる
  5. 新しい世代について2からの手順をやり直す
みたいな感じ。
これを繰り返して進めていきます。
良い遺伝子だけが生き残るので、総当りより効率的に問題をとくことができます。

どんな時に使うのか

遺伝的アルゴリズムは、
  • 最適な解法が無い(あるいは凄い難しい)
  • 与えられた解がどのくらい正解に近いかを評価するのは簡単
みたいな時に使われます。

例を挙げるならば、

nクイーン問題

n×nのマスの盤にn個のクイーンを置きます。
置くんだけど、クイーン同士がお互いを取れる位置に置いちゃダメ。
クイーンはタテ・ヨコ・ナナメに動けるので、タテ・ヨコ・ナナメに並んじゃダメってことね。

これを素直に解くのはすごく大変・・・ってほど大変でもないんだけれど。
まあ、遺伝的アルゴリズムの例にはよく使われるよね。

参考:エイト・クイーン - wikipedia

ナップサック問題

X kgまで入れられるナップサックに商品を詰める時に、どれをいくつ詰めれば一番高価な組み合わせになるか。みたいな問題。
ややっこいので、wikipedia参照でお願いします。

参考:ナップサック問題 - wikipedia

余談:遺伝的プログラミング

アルゴリズムと同じ感じで、遺伝的プログラミングなんてものもあります。
この場合、分岐とか繰り返しとかの条件を遺伝子として扱って、プログラムを書かせます。
遺伝的アルゴリズムと比べるとあんまりメジャーじゃないけどね。

発展してゆけばプログラムを書くプログラムを書くプログラムを・・・みたいな素敵なことに。
いやー、浪漫だね。
< C言語のu_int16とかって何なのよ。 pythonのpyevolveで遺伝的アルゴリズム。 >