python - 寻找更好的遗传算法评价方法

Question

我目前正在尝试解决 hard Challenge #151在 reddit 上用一种不寻常的方法，一种遗传算法。

简而言之，在将字符串分隔为 consonants 和 vowels 并删除 spaces 之后，我需要在不知道哪个字符先出现的情况下将它们放在一起.

hello world 分离为hllwrld 和eoo 需要重新组合。例如，一种解决方案是 hlelworlod，但这没有多大意义。采用所有可能解决方案的详尽方法可行，但对于较长的问题集不可行。

我已经拥有的

• 英语单词出现频率数据库
• 一种算法，它使用 Zipf 定律构建相对成本 数据库，并且可以一致地将单词与句子分开而没有空格(借用自 this question/answer
• 一种将辅音字母和元音字母放入堆栈并随机从其中一个字符中取出一个字符并将其编码为由 1 和 2 组成的字符串的方法，有效地编码基因中的构造。该示例的正确 gene 为 1211212111
• 一种改变这样的字符串的方法，随机交换字符

我尝试了什么

生成 500 个随机序列，使用 infer_spaces() 方法并用所有单词的成本评估适应度，从中取最好的 25% 并变异 4 个新的，适用于小字符串，但经常陷入局部极小值，特别是对于较长的序列。 Hello World 已经在第一代中被发现，thisisnotworkingverygood(正确分离且成本为 41.223)收敛到 th iss n ti wo or king v rye good (270 cost) 已经在二代了。

我需要什么

很明显，使用计算成本作为评估方法只对语法正确的句子的分离有效，对这种遗传算法无效。你有更好的想法我可以试试吗？或者是解决方案的另一部分，例如 gene 的表示，问题是什么？

Answer 1

我会将问题简化为两部分，

1. 寻找将字符串拆分成的候选词 (so hllwrld => hll wrld)
2. 然后如何通过添加元音来扩展这些单词。

我会首先获取您的词频词典，然后对其进行处理以创建第二个不含元音的词列表，以及每个折叠词(以及相关频率)的可能元音列表列表。从技术上讲，您不需要 GA 来解决这个问题(我认为没有 GA 会更容易解决)，但正如您所问，我将提供 2 个答案:

没有 GA:您应该能够使用深度优先搜索解决第一个问题，将单词的子字符串与该词典进行匹配，然后对剩余的单词部分进行匹配，只接受分区将单词转换为单词(没有元音)，其中所有单词都在第二本词典中。然后你必须替换元音。鉴于第二个字典和您已有的分区，这应该很容易。您还可以使用元音列表来进一步限制分区，因为分区中的有效单词只能使用输入到算法中的元音列表中的元音来组成。从字符串的左侧开始并以深度优先的方式遍历所有有效分区应该相对快速地解决这个问题。

使用 GA:为了使用 GA 解决这个问题，我会创建没有元音的单词词典。然后使用 GA，创建与输入的辅音字符串长度相同的二进制字符串(作为你的染色体)，其中 1 = 在该位置拆分单词，0 = 保持不变。这些字符串的长度都相同。然后创建一个适应度函数，根据该词典，返回使用染色体进行拆分后获得的单词中没有元音的有效单词的比例。创建第二个适应度函数，它采用有效的非元音单词，并计算所有这些有效的非元音单词中缺失的元音与原始元音列表之间的重叠比例。通过将第一个函数的值乘以十(假设第二个函数返回 0 和 1 之间的值)，将两个适应度函数合并为一个函数。这将迫使算法首先关注分割问题，其次是元音插入问题，并且还将支持质量相同的分割，但更喜欢那些缺失元音与原始列表更接近的分割。我还将在解决方案中包括交叉。由于所有染色体的长度都相同，因此这应该是微不足道的。一旦你有一个在适应度函数上得分完美的解决方案，那么在给定没有元音的单词字典的情况下重新创建原始句子应该是微不足道的(前提是你维护第二个字典，列出每个非元音单词可能缺失的元音集- 每个单词可能有多个，因为一些无元音的单词在删除元音后将是相同的。