どうしても遺伝的アルゴリズムがしたかった

本稿は、遺伝的アルゴリズムを用いてナンプレを解く方法について、実装までを記録したものである。

ナンプレって何？

3×3のマス目からなるブロックに1～9の数字を重複なく入れる。
その3×3が9個集まって正方形になる。
正方形の9マスの行・列に数字が重複しないようにするゲーム。
あとは検索してください。

遺伝的アルゴリズムって？

問題に合わせた遺伝子情報を作る。
遺伝子を評価して強い遺伝子どうしを交叉させて次の世代をつくる。
たまに突然変異するとものすごく強くなったり弱くなったりする。
「俺の屍を越えてゆけ」システムでだんだん強い遺伝子だけに淘汰されるよねっていうアルゴリズム。
あとは検索してください。

実装

個体情報

今回は個体中に9×9の二次元配列で表現された遺伝子を登録する。各遺伝子には1～9までの数字が入り、個体はナンプレのルールに従って自分の「スコア」を知ることができ、これを評価値とする。
個体が持つ機能は以下のとおり。
- 生成・・・ランダムな遺伝子を持つ自身を生成する
- 個体の「お手本」が引数にあれば、その遺伝子情報をコピーする
- 評価・・・自分自身を評価する。
- 組換・・・指定部分の遺伝子情報を送信したり、変更したりする

ブレンダー

各個体を管理し、それらの交配を決定するブレンダーを導入する。
ブレンダーは決められた個数の個体を生成し、それらの世代交代を実行する。
ブレンダーが持つ機能は以下のとおり。
- 生成・・・指定個数の個体を生成する
- 交配・・・新しい世代を作る
- 選択・・・親となる個体を選ぶ
- 交叉・・・決められた操作により、2つの親から新しい子をひとつ作る
- 変異・・・極わずかな確率で、交叉により得られた子の遺伝子情報を変異させる

評価

今回は、遺伝子を9×9のマス目に見立てて、ナンプレのルールに従って評価した。
①ブロックの評価
　「同じブロック内に同一の数字が入らないようにする」というルールに従っっているかを判断する。1ブロックに10点を割り振り、そこに同じ数字が入っていたら、同じ数字の個数だけ減点を行う。
　例：
　　　111
　　　456
　　　789　→ 10点 - 3点 = 7点

　　　111
　　　111　
　　　111　→ 10点 - 9点 = 1点
　各遺伝子に9個のブロックがあるので、①は90点満点で評価する。
②行・列の評価
　「同じ行・列に同一の数字が入らないようにする」というルールに従っっているかを判断する。①と同様に、各行・列に10点を割り振り、同じ数字の個数だけ減点する。
　各遺伝子に9+9=18の評価行・列があるので、②は180点満点で評価する。

①，②の評価の合計を、270点満点で評価した。

選択について

ある世代の子の中から、ルーレット方式で親を2個体選び出す。
スコアを次々に足し合わせた合計のルーレットを作り、0～合計間の乱数をダーツの矢とする。
矢の示した位置にある個体を親として選択し、これを親の個数だけ繰り返す。

交叉について

交叉は一様交叉を選択した。新しくできる子の81個の遺伝子それぞれについて、同じ場所の遺伝子を、親の中からランダムに選んで採用する。

変異

5%の確率で子に突然変異が起きる。突然変異が起きると、子のランダムに選択された1箇所の数字がランダムに変化する。

結果

子の個数20,親の個数4,世代交代回数を100として実験した。
子の評価値の平均は200/270点で、およそ74点。70個の重複があるということは、ナンプレを解こうと思ったらかなり低い数値である。ランダムに生成した個体の評価値平均もおおよそ同じ数になる。
一様交叉はナンプレのような「よい遺伝子のかたまり」を容易に破壊してしまうので、パラメータを変化させても良い結果は出ないだろう。改良時は交叉方法を吟味したい。

おわりに

とりあえず形になったのでメモ書き程度に。。。今後追記をして、多少マシな遺伝子を作っていきます。