Solving Sudoku with genetic algorithms(遺伝的アルゴリズムを使って数独を解く) というブログエントリを読んで，遺伝的アルゴリズムの入門記事として面白かったので紹介。
遺伝的アルゴリズムとは，生命の遺伝の仕組みを模した方法を使って解を探索する手法のこと。データを遺伝子で表現した個体を複数用意し，適応度によって個体を選択し，遺伝子に突然変異を起こしたりして解を探索してゆく。実装例としては，PostgreSQLが問い合わせを最適化するのに遺伝的アルゴリズムを使っている。上記エントリでは，この遺伝的アルゴリズムを使って数独の問題を解く手法を紹介している。
遺伝的アルゴリズムは，どのように動くのだろうか。エントリにある文章を拝借して訳すと。
- 乱数を使って個体群を作る
- 個体を選択，個体の適応度を見ながらソートする
- 適応度の一番低い個体を新しい個体に置き換える。置き換えに使う新しい個体としては「最も適応度の高い個体のコピー」「その変異体」「乱数生成された全く新しい個体」「適応度上位の個体の交叉」を使う
- 適応度がより高い個体が見つかったら，保存しておく
- 適応度がより高い個体が発生しない(進化が止まる)状態が一定の世代続いたら，全個体を消して1に戻る
- 2に戻る
この手順を見ると分かるとおり，遺伝的アルゴリズムでは，問題を解くのに「どうすれば問題が解けるか」をほとんど考えなくて良い。個体の適応度を測る手法だけ与えて計算を繰り返せば，最適な解がでてくるというのが面白い。
遺伝的アルゴリズムを使って数独を解くには，適応度を測る評価関数を作る必要がある。2つの(でたらめな)マトリックスを比べて，どちらがより数独の解として優れているかを計算する関数を書く。エントリの「Sudoku fitness function」というセクションに貼られている43行のコードがそれで，数独の2次元のマスを1次元にした遺伝子を評価している。
この評価関数を使って遺伝的アルゴリズムに従って遺伝子を処理し，数分待てば答えが出てくる。もっと速い数独solverはあるけど，遺伝子とか突然変異という手法を使って，有機的に数独を解けてしまうのがとても面白い。
遺伝的アルゴリズムの概要を知るには良い記事だ。コードはPythonで書かれていて，とても読みやすいので，コード部分だけでも読んでみてはどうだろうか。
