TIM Labs

突然変異の実装

| コメント(0) | トラックバック(0)
突然変異とは、文字通り、染色体のどこかを突然変更してしまうことである。

このパズルの場合には、ランダムに長方形を1つ選んで、その周囲を少々破壊して作り直すとかが考えられる。

しかし、これはほぼ確実にダメな染色体ができるだけに過ぎず、進化を促すような奇跡が起きることは極めて少なく、延々と計算が続き、欲しい結果が得られないまま終わることが非常に多い。

それで、少々工夫をしていみた。その工夫を以下の図にまとめてみた。

na-ga19.png

(1) まず、与えられた盤面をしっかり観察しよう。この問題を解くと、緑色の部分が確定し、右上の2、4、6の一部が決まる。

(2) ということで、どこでも適当に破壊するのではなく、ダメなところを破壊して作り直すことにしよう。ということで、候補は、この3つの長方形から選ぶことにしよう。

(3) どれを選んでも良いのだが、6を選択したとして説明を続ける。6の長方形と、それに隣接した長方形を破壊する、つまり白紙に戻すことにする。
ただし、隣接とは何かを決めないといけない。実は、あまりたくさん壊すと、悪影響の方が多くなる。少な過ぎると、意味がなくなる。それで、結局現在やっている方法は、選んだ長方形を上下または左右に±1だけ動かしてぶつかる長方形だけを白紙に戻すことにしている。それで、黄色で×をした3つの長方形を白紙に戻す。

(4) 白紙に戻してしまった状態である。この状態から、適当に長方形に切り直す。

(5) 適当に分割し直してみた結果である。

以上が、現在の突然変異の実装である。

白紙に戻した部分を再度分割しているが、この分割の方法次第で、どのように破壊するのが良いかが影響する。


さて、これで、交叉、突然変異ができたので、組み合わせれば遺伝的アルゴリズムが動くようになる。でも、現実はそんなに甘くないのである。動いて、一応問題は作れるようになるのだが、それほど良い問題が作れるようになる訳ではない。これは、このパズルの場合に限らず、遺伝的アルゴリズムは、対象分野毎に、いろいろな工夫をしないとさっぱり使い物にならないことが多い。

これについては、話が長くなるので、次回以降に説明しよう。


トラックバック(0)

トラックバックURL: http://labs.timedia.co.jp/mt/mt-tb.cgi/396

コメントする

このブログ記事について

このページは、fujiが2013年8月13日 00:00に書いたブログ記事です。

ひとつ前のブログ記事は「JavaScript でオセロを実装する(AI高速化編)」です。

次のブログ記事は「Azure Cache Service」です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。