寻找更好的遗传算法评估方法

Question

我现在正在尝试用一种不寻常的方法解决reddit上的一个难题，叫做困难挑战 #151，这个方法是遗传算法。

简单来说，我需要把一个字符串分成辅音和元音，然后去掉空格，最后再把它们组合起来，但我不知道哪个字符应该先出现。

比如说hello world被分成了hllwrld和eoo，现在需要把它们重新组合起来。一个可能的组合是hlelworlod，但这并没有什么意义。虽然可以尝试所有可能的组合来找到答案，但对于较长的字符串，这种方法不太可行。

我已经有的东西

• 一个包含英语单词频率的数据库
• 一个算法，它使用齐夫定律构建相对的成本数据库，并且可以在没有空格的句子中稳定地分离出单词（这个方法是借鉴自这个问题/答案）
• 一个方法，把辅音和元音放进一个栈里，随机从其中一个取出一个字符，并用1和2来编码这个字符，实际上是把构造过程编码成一个基因。比如说，例子的正确基因是1211212111
• 一个方法，可以随机变更这个字符串，交换字符的位置

我尝试过的

我生成了500个随机序列，使用infer_spaces()方法来评估这些序列的适应度，计算所有单词的成本，然后选出最好的25%，从中变异出4个新序列。这个方法在小字符串上有效，但在较长的序列中经常陷入局部最优解。比如Hello World在第一代就找到了，而thisisnotworkingverygood（正确分离后成本为41.223）在第二代就收敛成了th iss n ti wo or king v rye good（成本为270）。

我需要的

显然，使用计算出的成本作为评估方法只适用于语法正确的句子的分离，而不适合这个遗传算法。你有没有更好的想法可以尝试？或者说，基因的表示方式是否也是问题的一部分？

Answer 1

适应度函数是遗传算法成功的关键（我觉得在这里是合适的）。

我同意@Simon的看法，元音和辅音的分离并不是那么重要。只需处理你的文本，把元音去掉就行。

在适应度中，重要的有：

1. 匹配的单词频率（常用的单词更好）
2. 语法 - 句子的结构（你可能需要用NLTK来获取相关信息）

别忘了更新最终结果哦^^

Answer 2

假设你有好几代的个体，然后你把每一代中最优秀的个体的成本画成图（我们考虑长句子）。这个图在经过2-3代后，会不会下降或者收敛到某个特定的值呢？比如让算法运行10代看看？你能不能多次运行你的算法，使用不同的初始条件（随机的序列），看看有时候能不能得到好的结果？

根据结果，你可以尝试以下几种方法（这个图是一个很好的工具，可以帮助你提高性能）：

1) 如果你的图总是上下波动得太厉害，说明你的变异太多了（比如每个基因的平均交换次数），可以尝试减少变异。

2) 如果你卡在了一个局部最小值（最优秀个体的成本在一段时间内变化不大），可以尝试增加变异，或者在算法开始时运行几个孤立的种群（比如3-4个），每个种群大约100个个体。然后选择最优秀的种群（也就是更接近全局最小值的那个），尽量通过变异来改进它。

另外，这个问题很有趣，我尝试过用交叉来改进算法，但还没找到好的方法。

Answer 3

我会把这个问题简化成两个部分：

1. 找到可以把字符串拆分成的候选单词（比如把 hllwrld 拆成 hll 和 wrld）
2. 然后如何通过添加元音来扩展这些单词。

首先，我会拿你的单词频率字典，处理一下，创建一个没有元音的单词列表，同时为每个被压缩的单词准备一个可能的元音列表（还有对应的频率）。其实你不一定需要用遗传算法来解决这个问题（我觉得不用会更简单），但既然你问了，我就提供两种解决方案：

不使用遗传算法：你可以用深度优先搜索来解决第一个问题，把单词的子串和字典里的单词匹配，剩下的部分也这样做，只接受那些能拆分成字典里单词（没有元音）的组合。然后你需要把元音填进去。根据你已有的第二个字典和拆分结果，这应该很简单。你还可以用元音列表来进一步限制拆分，因为有效的单词只能用输入的元音列表中的元音来完整化。从字符串的左边开始，逐个检查所有有效的拆分，应该能比较快地解决这个问题。

使用遗传算法：如果用遗传算法来解决这个问题，我会先创建一个没有元音的单词字典。然后用遗传算法，生成和输入的辅音字符串长度相同的二进制字符串（作为你的染色体），其中1表示在那个位置拆分单词，0表示不变。这些字符串的长度都是一样的。接着创建一个适应度函数，返回在用染色体进行拆分后，得到的有效无元音单词的比例，这些单词要根据字典来判断。再创建一个第二个适应度函数，计算所有有效无元音单词中缺失的元音与原始元音列表之间的重叠比例。把这两个适应度函数结合成一个，通过把第一个函数的值乘以十（假设第二个函数返回的值在0到1之间）。这样可以让算法先关注拆分问题，再关注元音插入问题，同时也会偏向那些缺失的元音和原始列表更接近的拆分结果。我还会在解决方案中加入交叉操作。由于所有的染色体长度相同，这应该很简单。一旦你得到一个在适应度函数上得分完美的解决方案，那么根据没有元音的单词字典重建原句就应该很简单（前提是你保持一个第二个字典，列出每个无元音单词可能缺失的元音集合——因为有些去掉元音的单词可能是一样的）。