Tenpuzzle - Find the solution of the 10 puzzles in Genetic Algorithm
10 パズル <- 10 パズル知らない人向け
なぜ作ったか
大学の講義で遺伝的アルゴリズムの考えをレポートにまとめるか、遺伝的アルゴリズムを使った何かのプログラムを作ってくるかのどっちかだったため、作った。この記事がいつの日か誰かの役に立てばいいなと願い、記録する。
仕組み
遺伝的アルゴリズムは存在する個体に対して大まかに 3 つの出来事を必要とする。それが、
- 交叉
- 突然変異
- 個体の死滅
である。簡単に言うと自然界において優秀な存在は生き残るというのと同じことである。
※優秀なイメージ
交叉
10 パズルの解というものは 10 になるような四則演算を用いた式のことである。式はこんな感じで二分木で表現することが可能である。
この場合だと$((7+3)∗(5−2))$ということになる。
10 パズルのルール上このような二分木のパターンが 5 パターンしか存在しない。どんなパターンが存在するかはコメントで簡単に記載している。
つまりこれらの部分木を使って交叉を行う。 2 つの親となる木を用意してあげ、各親の木の同じ形をした部分木(葉も含む)同士を交換して新しい木を生成していくことになる。
突然変異
いろいろ考えられるが、今回行った方法は生き残った木を 2 パターン使って突然変異させることである。
- 演算子の変更
- 数値の変更
個体の死滅
悲しいことではあるが、遺伝的アルゴリズムでは必須な機能である。
劣勢な個体を排除するために適応度関数というものを用いて優秀な個体か、優秀ではないかというものを判断する。今回の場合だと生成された式の計算結果と 10 の距離がどれだけ離れているかで優秀かどうか判断した。そして 10 から遠ければ遠いほど優秀ということにした。（式を見てこれは 10 になりやすい式だ！！ってならんでしょー...）
その部分のソースコードである。
つまり、この判断さえできれば優秀な順でソートすることが可能になる。ソート後に劣勢な個体を全体の半分削除する。
以上の交叉、突然変異、死滅を行った後の最終的な個体の数は、初期で作成した集団の数と同じ数になる。
一連の流れのコードはこんな感じになる。
実行
go get github.com/Code-Hex/tenpuzzle
go get github.com/Code-Hex/tenpuzzle/cmd/ga
のあとに
ga
で実行可能である。
感想
10 パズルのすべての解を見つけたいなら普通に総当たりを行ったほうが早いし、このプログラムが何の役に立つのかすら未だに分からないが、遺伝的アルゴリズムの学習にはとても役立った。
生物の生き残り競争は本当に厳しいものであることも分かった。