3-SAT with 遺伝的アルゴリズム

遺伝的アルゴリズムを使って問題を解いてみよう企画、第一弾。第二段の予定はありません。なぜならこれはそのままレポートとして提出されるからです。
さて、遺伝的アルゴリズムを使えば、ひょっとして3-SATをすばやく解くことが可能になるのではないか、という妄想から解いてみることにしました。問題の設定としては次の通り。

3-SATは、いわゆる主乗法標準形で表され、各節が3つの要素からなっているものの真偽値割り当てを行うものである。例えば、
(X1 + X2 + ^X3) * (X2 + X3 + X4) * (^X1 + ^X2 + X5)
のような形で表されている式の、各Xnに1もしくは0を割り当てて、全体が真になるようにする。ちなみに、+や*はbool代数で定義されているものなので、1 + 1 = 1である。
この時、全ての節を真にすることと、全体が真になることは同値であるので、「なるべく多くの節を真にするような」真偽値割り当てと言うのが優秀であるということを仮定して、その仮定の下で遺伝的アルゴリズムを設計する。

さて、まずこれをやってみるためには3-SATの問題を作らなくてはなりません。どうしたってgenerateする必要があるのですが、これが意外と難しいです。解の無い3-SATの問題を与えたところで意味が無いのですが、逆に3-SATは複数の解を持っていても構わないので、どうしたらよいのでしょうか。
その一つの回答として、まず一つ真理値割り当てをランダムに生成し、それを解とするような3-SATの問題を作ることにしました。
まず、ランダムな真理値割り当てを行います。次に、この真理値割り当てに対して矛盾の無い3-SATの節を生成します。具体的には3-SATの節をランダムに生成し、矛盾のあるもののみ捨てます。十分に多くの節を生成してやれば、おそらく解は一つに近づいていくと考えられます。
これで問題の生成はできました。で、次はselectionとmutationとcrossoverの三つを実装してやる必要があります。
一番簡単なのはcrossoverです。これは、各真理値割り当てをランダムに両親のものから取ってやればよいです。こうすることで、完全にmixされた真理値割り当てが出来上がります。mutationも簡単です。ある一定の確率で、ランダムに真理値割り当てを逆転させてやれば良いのです。
一番難しいのがselectionの関数です。どのような割合で選別が起こるのかを設定しなくてはならないのですが、暫定的に設定してやった「節が真になっている割合」では、90%を超えるのは一瞬ですが、その後100%には中々なりません。というのは、90%を超えたものは中々選別によって死なないので、新しい子供が生まれてくることが滅多にないからです。もっと選別の関数をうまく設定してやる必要があると思われます。
もう少しいじってみて、追記するかもしれません。