遗传算法和替代密码

Question

我想写一个遗传算法，解码用替代密码编码的字符串。输入将是从a到z和空格字符的小写字符串，不会被编码。例如，

uyd zjglk brsmh osc tjewn spdr uyd xqia fsv

是

the quick brown fox jumps over the lazy dog

通知的有效编码的空格字符不会被编码。

基因将是一对一的随机字符映射。

为了确定基因（或映射）的适应度，将要解码的字符串应用于该映射，并且计算结果中识别的英语单词的数量。

当输入字符串中的所有单词都是有效的英文单词时，该算法终止。

我不想使用其他技术，如频率分析。

这项工作？关于表演可以说些什么？

Answer 1

通过计算有效词汇的数量可以得出非常“高原-y”的健身情况。

在您的示例字符串中，每个人都将被分配一个介于0和9之间的整数适应值，其中绝大多数在该范围的低端。这意味着如果你生成一个初始种群，那么它们很可能都具有零适应性。这意味着你不能有有意义的选择压力，整个事情看起来很像随机游走。偶尔你会偶然发现一些说得对的话，那时候，人口会转向那个人。给定足够的时间（并且假设你的单词足够短，有足够的希望随时随地找一个单词），你最终会找到字符串。具有合理的（即遍历的）操作符的遗传算法总是会找到最优解，如果你让它们在超指数时间内运行足够远。但是，遗传算法很可能不是解决问题的好方法。

Answer 2

对于遗传算法，您需要一种获取下一代的方法。要么你发明了某种方式将两种排列变成第三种排列，或者你只是对最成功的排列进行随机修改。后者给你基本上是基于随机游走的本地搜索算法，这在时间上并不是太高效，但是可能会收敛于。
前者根本不会做任何好事。对于不同的排列，即使它们不共享单个正确的字母对，也可能得到非零字数。简而言之，替换密码是非常非线性的，所以你的算法会变成一系列随机猜测，比如bogosort。您可能不会评估多个词，但可以评估字母链的“可能性”，但它几乎是一种频率分析。

Answer 3

遗传算法通常具有“重组”和“突变”以创建前一代的新一代。您可能需要考虑这一点 - 如果您的代中有两种特定的替代密码，并且在您查看其中创建英文单词的部分时，可能会合并两个创建英语的密码的非冲突部分词，并且创造一个密码，这个密码创造出比你“配对”的两个原始密码更多的英文单词。如果你不这样做，那么遗传算法可能需要更长的时间。

此外，您可能希望将“健身”功能的选择更改为更复杂的内容，而不仅仅是密码所使用的英语单词的数量。直观地说，如果有一个相当长的加密单词（比如说5个或更多的字母）并且有一些重复的字母，那么如果你成功地将它翻译成英文单词，通常可以证明这部分密码是正确的，而不是如果你有两个或三个不同的双字母翻译成英文。对于“它会工作/表现如何”，我同意你的遗传算法基本上是一种随机猜测的结构化方法，并且最初通常很难确保你的人口总数适合的人有一些个人正朝着正确的解决方案取得良好的进展，仅仅因为可能有许多密码给出错误的英文单词，例如如果你有很多3个字母的单词和3个不同的字母。所以你要么需要一个庞大的人口规模（至少在开始的时候），要么你必须重新启动算法，如果你确定你的人口没有得到任何更合适的人（因为他们都被困在当地最优惠的地方，英语单词的数量，但它们完全偏离正确的解决方案）。