解决与遗传算法，健身，突变纵横字谜

我努力做一个实验室的学校。我正在尝试使用遗传算法解决纵横字谜。问题是，这不是很好（它仍然是过于随机）我会尝试给我现在如何执行我的程序的简短说明：解决与遗传算法，健身，突变纵横字谜

如果我有困惑（＃是块，0是空的空间）

#000 
00#0 
#000

以及这个拼图的解决方案的候选词的集合。我的DNA只是作为一维数组的矩阵。

我的第一套个人从我的单词包含的字母池中随机生成DNA。

我使用轮盘赌选择做选择。关于组合和突变的几率有一些参数，但如果突变会发生，那么我将总是改变25％的DNA。我从我的信池中随机字母改变它（这可能有负面影响，因为突变可以破坏已经形成的话）

现在的适应度函数：我都horizontaly和verticaly遍历矩阵：如果我找到一个词，然后健身+ = word.lengh +1

如果我找到一个字符串是一个字的一部分，然后健身+ = word.length /（puzzle_size * 4）。无论如何，它应该给出一个介于0和1之间的值。因此，它可以从“tool”和广告X中找到“FITNESS”，然后在“tool”中找到“too”并将另一个Y添加到FITNESS。

我的这代人实际上并没有随着时间而改善。他们显得随机。所以即使经过400代1000-2000的池（这些数字并不重要），当解决方案应该有6个单词时，我会得到1-2个字（2或3个字母）的解决方案。

来源

2011-05-02 Blitzkr1eg

我认为你的健身功能可能不明确。我会设置这个，所以每一行都有一个二进制适应度。一行是合适的，否则它不合适。（例如，行是一个单词，或者它不是一个单词）那么解决方案的整体适应性将会是#fit rows/total rows（横向和纵向）。此外，你可能会改变太多的DNA，我会做出这个变量，并试验。

来源

2011-05-02 16:50:34

一行可能包含多于1个单词，如：＃tool＃pink – Blitzkr1eg 2011-05-02 17:47:35

然后，健身可能是＃行中正确的单词/每行可能的单词数量。我认为字长是无关紧要的 – 2011-05-02 18:02:34

您的健身功能对我来说看起来还不错，尽管没有更多的细节，但很难获得您所做的事情的真实情况。

你没有指定变异概率，但是当你变异时，25％是非常高的变异。此外，轮盘选择适用批次的选择压力。你经常看到的是，算法很早就发现了一个比所有其他算法好得多的解决方案，轮盘选择导致算法选择它的可能性很高，以致于你很快就会得到一个完整的副本那个。在那一点上，除了偶尔偶然的幸运突变之外，搜索暂停，并且由于你的突变非常大，所以你不可能发现一个改进的移动而不破坏染色体的其余部分。

我会尝试二元比赛的选择，和一个更明智的变异算子。通常启发式的人用于突变是（平均）翻转每个染色体的一个“位”。但是，您不希望每次都确定一个字母更改。例如：

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-02 21:26:53 deong

解决与遗传算法，健身，突变纵横字谜

回答

相关问题