遺伝的アルゴリズム、フィットネス、突然変異でクロスワードパズルを解く

Question

私は学校のために研究室をやろうとしています。遺伝的アルゴリズムを使用してクロスワードパズルを解決しようとしています。問題は、それがあまり良くないことです（まだランダムすぎる）私は、私のプログラムが今どのように実装されているかについて簡単に説明しようとします：

パズルがある場合（＃はブロック、0は空きスペースです）

#000
00#0
#000

そして、このパズルのソリューションの候補者である言葉のコレクション。私のDNAは、単に1D配列としてのマトリックスです。

私の最初の個人のセットには、私の言葉に含まれる文字のプールからランダム生成DNAがあります。

ルーレット選択を使用して選択します。組み合わせと突然変異の可能性についてはいくつかのパラメーターがありますが、変異が発生する場合、私は常にDNAの25％を変えます。私は文字のプールからのランダムな文字でそれを変更します（これは、変異がすでに形成された言葉を破壊する可能性があるため、悪影響を与える可能性があります）

フィットネス関数：私は水平と垂直の両方のマトリックスを横断します：単語を見つけた場合、フィットネス += word.lengh +1

単語の一部である文字列を見つけた場合、fitness += word.length /（puzzle_size*4）。とにかく、それは0から1の間の値を与える必要があります。したがって、「ツール」と広告Xからフィットネスへの「TO」を見つけることができます。そして、「ツール」から「「ツール」から「」も見つけて、フィットネスに別のYを追加します。

私の世代は、実際には時間の経過とともに改善されていません。それらはランダムに見えます。したがって、1000〜2000のプールを持つ400世代（これらの数字は実際には重要ではありません）の後でも、ソリューションに6つの単語が必要な場合は、1〜2語（2文字または3文字）で解決策を取得します。

Answer 1

あなたのフィットネス機能は不明確であると思います。これをセットアップして、各行にバイナリフィットネスレベルがあります。行がフィットするか、そうではありません。 （たとえば、行は単語であるか、単語ではありません）、ソリューションの全体的なフィットネスは、#fit行 /合計行（水平方向と垂直の両方）になります。また、DNAをあまりにも多く変えているかもしれません。私はその変数を作り、それを実験します。

Answer 2

あなたのフィットネス機能は私には大丈夫に見えますが、詳細がなければ、あなたがしていることの本当に良い写真を撮るのは難しいです。

突然変異の確率を指定しませんが、変異を行うと、25％が非常に高い突然変異です。また、ルーレットホイールの選択が適用されます 多く 選択圧力の。よく見られるのは、アルゴリズムがかなり早い段階で他のすべてのソリューションよりもかなり優れているソリューションを見つけ、ルーレットホイールの選択により、アルゴリズムが非常に高い確率でそれを選択するため、コピーでいっぱいの人口にすぐに終わる可能性が高いことです。その。その時点で、盲目的に幸運な突然変異を除いて検索停止を検索します。そして、あなたの突然変異は非常に大きいので、残りの染色体を破壊することなく改善される動きを見つける可能性は非常に低いです。

バイナリトーナメントの選択と、より賢明な突然変異オペレーターを試してみました。突然変異に使用する通常のヒューリスティックな人々は、（平均して）各染色体の1つの「ビット」をひっくり返すことです。ただし、毎回決定論的な1文字の変更を必要としません。このようなもの：

for(i=0; i<chromosome.length(); ++i) {
    // random generates double in the range [0, 1)
    if(random() < 1.0/chromosome.length()) {
       chromosome[i] = pick_random_letter();
    }
}