1

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

パズルを持っている場合（＃はブロック、0は空きスペース）

#000
00#0
#000

そして、このパズルの解決策の候補となる単語のコレクション。私のDNAは、単に1D配列としてのマトリックスです。

私の最初の個人のセットは、私の単語に含まれる文字のプールからランダムに生成されたDNAを持っています。

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

ここで、適応度関数：行列を水平方向と垂直方向の両方でトラバースします。単語が見つかった場合、FITNESS + = word.lengh +1

ある単語の一部である文字列を見つけた場合、FITNESS + = word.length /（puzzle_size * 4）。とにかく、0から1までの値を指定する必要があります。したがって、「tool」から「to」を検索し、XをFITNESSにアドバタイズし、「tool」から「too」を検出した直後に、FITNESSに別のYを追加します。

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

4

2 に答える 2

1

あなたの適応度関数は明確に定義されていないのではないかと思います。これを設定して、各行にバイナリの適応度レベルを設定します。行が適合しているか、適合していないかのどちらかです。（たとえば、行が単語であるか、単語ではない場合）ソリューションの全体的な適合性は、＃fit行/合計行（水平方向と垂直方向の両方）になります。また、DNAを変更しすぎている可能性があるので、その変数を作成して実験します。

于 2011-05-02T16:50:34.420 に答える
1

あなたの適応度関数は私には問題ないように見えますが、詳細がなければ、あなたがしていることの本当に良い画像を得るのは難しいです。

突然変異の確率は指定しませんが、突然変異を行うと、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();
    }
}
于 2011-05-02T21:26:53.097 に答える