1

免责声明

首先，这是为了作业，所以不要问为什么这么做作，就是这样，也只能这样。（我得到很多“如果你改变一些东西怎么样”），对不起......我不能。

另外我必须使用进化算法，这意味着父母有孩子，他们可以变异/重组，形成新的世代并最终导致解决方案。

/免责声明

我有n*2长度为 n 的单词。我必须制作一个n^2包含所有这些单词的矩阵。这些词可能是胡言乱语，但它们必须能够适应这个矩阵（这是用户的要求）。

因此AGE,AGO,BEG,CAB,CAD,DOG会给我这个结果（至少有 2 个可能）：

C A B
A G E
D O G

我必须使用进化算法。因此，我需要找到一种方法将我的信息编码到染色体中。

我确实想出了：

每个单词都必须出现，在矩阵中具有起始位置和方向（左右或上下）。因此我有[Word][Orientation][StartPosition]哪里开始位置是[0][0]/ [0][1]/ [1][0]etc（左列和顶行）。但它有限制，我需要验证方向是否适合起始位置。

问题：

染色体必须是可能的解决方案，而这只是解决方案的一部分。

因为我的解决方案必须是一个包含所有单词的矩阵，以“适合”染色体也必须以某种方式代表整个矩阵。但这会遇到几个问题。我只能从一个方向的一个起始位置有一个单词（除了前两个单词，它们在不同方向共享相同的起始位置）。我看不出这是尝试进化算法的有效方式。我只是看不到任何阶段的工作，尤其是突变/重组。

我认为它完全错误吗？如果是这样……为什么？以及我如何尝试以这样一种方式对我的数据进行编码，以便让我经历所有阶段（繁殖、突变/重组、自然选择……能够计算适应度并开始新一代）而无需大量垃圾数据（一个单词出现两次，丢失一个单词，与它的起始位置相比，一个单词的方向错误）？

编辑

我将使用这种表示来实现许多其他受自然启发的算法，因此我需要一个“好的”数据表示。没有什么临时的东西会在以后伤害我。

不过老实说，我想不出什么好办法。因为我有很多限制（也许我一直在思考这个问题太久了，我无法超越它们，而且它们可能并不真的存在）。我真的很想要一个二进制表示，但这似乎是不可能的。

4

2 回答 2

1

一些选项：

只需将字母矩阵作为您的表示。因此，您从示例中获得的最佳解决方案是：

CABAGEDOG

然后，为了您的健康，只需为解决方案中实际出现的每个请求的单词加分。

或者让表示由三个单词组成，每行一个单词。

   CAB
   AGE
   DOG

然后，您的健康会奖励列中正确的单词。突变将一个词换成另一个词。

于 2013-05-16T15:12:29.050 回答
1

您似乎对 Winston Ewert 的回答有疑问。由于长度和格式的原因，我将其作为单独的答案，但温斯顿建议的是一种合理的方法。

您询问“字符数组”以及您的父母和后代是什么，您将如何进行交叉，突变等。我想您可能对字符数组感到困惑。不要把它想象成一个字符数组——它是一个单词数组。这很重要，因为您不想在单词边界之间进行交叉或通过突变更改单词内的字母。你想改变周围的单词。因此，我们不处理单词，而是采用稍微不同（但等效）的方法。

让我们将你的 2n 个单词中的每一个从 1 编号到 2n。为了生成候选解决方案，我们只需选择 1 到 2n 之间的 n 个随机数（无需替换）。随机选择的单词成为矩阵的行。因此，如果单词是AGE,AGO,BEG,CAB,CAD,DOG，我们随机选择三个并以例如 2、3 和 5（给出 的染色体235）或. 结尾AGO,BEG,CAD。

这产生了一个矩阵

AGO
BEG
CAD

现在我们计算 2n 个输入单词中有多少出现在矩阵中。在这种情况下，它只有三个，因为没有一列是有效的词。您对输入的适应度为2353。但输入416有效 - 它的适应度为 6。

要生成总体，您只需生成 1 到 2n 之间的 N 个由三个数字组成的随机集合（不重复）。人口规模为 4 时，您可能会得到

142
354
624
241

这些为您提供了四种不同的潜在解决方案：

142 = AGE
      CAB
      AGO

354 = BEG
      CAD
      CAB

624 = DOG
      AGO
      CAB

241 = AGO
      CAB
      AGE

要进行交叉，您需要设计一种方法来避免后代中出现重复数字。我过去曾采用为排列设计的循环交叉方法来处理与此类似的情况，但您可以设计任何看起来合理的方法。例如，您可以进行简单的统一交叉，然后通过将其中一个更改为其他值来修复任何重复的值。

变异只是将一个数字更改为另一个数字或交换两个数字在编码中的位置。

你说你必须使用 GA，所以你可以在这里停下来尝试类似的东西。由于几个原因，它不太可能工作得非常好。首先，适应度函数会有很多平台期。几乎所有可能的答案都同样是错误的，因此 GA 没有太多可遵循的梯度。这是大海捞针搜索问题中的一根针。您可以尝试修改对适应度值进行评分的方式，以在一定程度上缓解这种情况。例如，我知道在您的示例集中只有一个单词以开头，因此第一行中的D任何解决方案都会自动出错。DOG我可以给给出更多“合理”错误答案的解决方案打分。然而，总的来说，这对于 GA 来说将是一个难以有效解决的问题。

其次，无论您如何构建 GA，都可以通过专门的技术更有效地解决此类约束满足问题。您可以通过回溯轻松解决此问题。

于 2013-05-16T16:09:51.960 回答