1

我正在努力为学校做一个实验室。我正在尝试使用遗传算法解决填字游戏。问题是这不是很好（它仍然太随机）我将尝试简要说明我的程序现在是如何实现的：

如果我有拼图（# 是块，0 是空白）

#000
00#0
#000

以及作为该谜题解决方案候选词的集合。我的 DNA 只是作为一维阵列的矩阵。

我的第一组人从我的话包含的字母池中随机生成了 DNA。

我使用轮盘赌选择进行选择。有一些关于组合和突变机会的参数，但如果发生突变，那么我总是会改变 25% 的 DNA。我用我的字母池中的随机字母对其进行更改。（这可能会产生负面影响，因为突变会破坏已经形成的单词）

现在是适应度函数：我横向和纵向遍历矩阵：如果我找到一个单词然后 FITNESS += word.lengh +1

如果我发现一个字符串是某个单词的一部分，那么 FITNESS += word.length / (puzzle_size*4) 。无论如何，它应该给出一个介于 0 和 1 之间的值。因此它可以从“工具”中找到“到”并将 X 广告到 FITNESS，然后在它从“工具”中找到“太”并将另一个 Y 添加到 FITNESS 之后。

我的几代人实际上并没有随着时间的推移而改善。它们看起来是随机的。因此，即使在 400 代之后，池中的 1000-2000（这些数字并不重要），当解决方案应该有 6 个单词时，我也会得到一个包含 1-2 个单词（2 或 3 个字母）的解决方案。

4

2 回答 2

1

我认为您的适应度函数可能定义不明确。我会设置这个，所以每一行都有一个二进制适应度水平。一行要么合适，要么不合适。（例如，一个 Row 是一个单词或者它不是一个单词）那么解决方案的整体适应度将是#fit rows / total rows（水平和垂直）。另外，你可能改变了太多的 dna，我会改变这个变量并进行实验。

于 2011-05-02T16:50:34.420 回答
1

你的健身功能在我看来还不错，虽然没有更多细节很难真正了解你在做什么。

您没有指定突变概率，但是当您进行突变时，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-02T21:26:53.097 回答