使用遗传算法破解密码

什么是过早收敛？

前两章专注于从现有种群中生成更优种群的过程。选择最优解一章重点讨论了为繁殖选择具有最佳机会提升整体种群适应度的解决方案。生成新解一章则专门聚焦于创建新解的过程。

在种群中正确应用选择和交叉操作，对遗传算法的成功至关重要。仅使用选择和交叉已足以构成一个完整的遗传算法；如果我们不希望改变种群，就不需要额外步骤。然而，仅依赖选择和交叉可能导致一个常见陷阱：过早收敛。

过早收敛指的是由于种群中缺乏遗传多样性而导致算法进展停滞的现象。正如我们在探索选择一课中所见，随着时间推移，种群往往会趋向于相似的遗传模式。为了理解这为何是个问题，请看下图所示的一个二进制染色体样本种群：

注意每个染色体的第一个基因。如果目标是最大化每个序列中的1的数量，那么仅靠交叉将无法达到最优解。因为每个染色体的第一个基因都是 0，而没有任何方式能将其变为 1。在实际中，我们会称这种情况为收敛等位基因。

回想一下理解并创建染色体一课的内容，一个等位基因只是某个特定基因的取值。而收敛等位基因是指种群中大多数个体共享相同值的等位基因。

虽然现实中使用大小为5、种群规模为5的情况并不实际，但这并不意味着这种现象不会在实践中发生。

当我们实现带有和不带变异的遗传算法时，将真正看到过早收敛的影响。

种群多样性与过早收敛

普遍认为，变异有助于防止过早收敛，因为它有助于维持种群多样性。人们普遍理解，种群多样性的下降与过早收敛之间存在直接关联。然而，目前尚无正式定义或量化种群多样性的标准方法。因此，尽管我们可能直观地判断算法停止改进是因为种群多样性不足，但并没有明确的标准来界定何时种群被认为已经收敛。

使用遗传算法破解密码

假设你被委以保护公司数据完整性的任务。某天，一名黑客入侵了你的系统，并加密了所有数据，随后要求支付赎金才能解密。

幸运的是，黑客选择使用一种基础的XOR密码，且密钥长度似乎为64位。这意味着，只要你能确定这个密钥，就能轻松反向应用该密码恢复所有数据。

XOR密码是一种可逆密码，其原理是对字符串中的每个字符进行按位异或运算，再与密钥结合。Unicode字符用16位表示。给定一个密钥和一段字符串，可以通过将密钥与每个字符进行异或来加密字符串。下图展示了这一过程：

要解密XOR密码，若已知密钥，则只需以相反流程再次应用相同操作。由于XOR运算是自身的逆运算，因此对加密文本使用相同的密钥再次执行密码操作即可得到原始明文。下图说明了这一点：

由于黑客选择了基础的XOR密码，你所需要做的就是找出他们用于加密数据的64位密钥。不幸的是，遍历全部 $2^{64}$ 种可能密钥在实际中不可行。因此，采用遗传算法是一个合理的选择。

问题建模

首先，创建一个新文件 scripts/codebreaker.exs。接着，构建 Problem 的基本框架：

1defmodule Codebreaker do 
2  @behaviour Problem 
3  alias Types.Chromosome 
4  use Bitwise
5  def genotype, do: # 基因型
6
7  def fitness_function(chromosome), do: # 适应度函数
8
9  def terminate?(population, generation), do: # 终止条件
10end

注意模块开头添加了 use Bitwise。我们将用它来实现适应度函数。

现在需要实现具体问题相关的函数。

我们要找的是黑客用来加密信息的64位密钥。自然地，应将染色体表示为一个64位的位串：

1def genotype do
2  genes = for _ <- 1..64, do: Enum.random(0..1) 
3  %Chromosome{genes: genes, size: 64}
4end

这里我们生成长度为64的随机二进制基因型，并返回一个新的 Chromosome 结构体。

评估与终止

接下来，我们需要一种方法来衡量离找到正确密钥还有多远。幸运的是，我们记得桌面上某个文件的名字是 ILoveGeneticAlgorithms。现在它的名字变成了 LIjs`B\`k\`qlfDibjwlqmhv。既然我们有加密后的字符串，也知道其正确的明文版本，就可以尝试一个密钥，并将其应用于加密字符串，观察结果与目标明文的接近程度。

实现适应度函数如下：

1def fitness_function(chromosome) do
2  target = 'ILoveGeneticAlgorithms'
3  encrypted = 'LIjs`B`k`qlfDibjwlqmhv'
4  cipher = fn word, key -> Enum.map(word, & rem(bxor(&1, key), 32768)) end
5  key =
6    chromosome.genes
7    |> Enum.map(& Integer.to_string(&1))
8    |> Enum.join("")
9    |> String.to_integer(2)
10
11  guess = List.to_string(cipher.(encrypted, key))
12  String.jaro_distance(List.to_string(target), guess)
13end

函数开始处声明 target（第2行），即其中一个加密文件名的正确解密版本，作为字符列表。同时在第3行定义 encrypted。第4行定义了一个基础的XOR密码函数，它遍历所提供字符串中的每个字符，执行异或运算后，对结果取模32768，以确保猜测的密文字符编码点在Elixir字符串可用范围内。

下一步是从提供的染色体生成整数密钥。染色体是由1和0组成的列表。为了将这个列表转换为十进制整数，在第7至8行，先将列表转为字符串，再以二进制基数解析为整数。

定义好 key 后，第11行用该密钥生成一个 guess，即尝试用当前染色体代表的密钥解密 encrypted 字符串。最后，第13行使用 String.jaro_distance/2 将 guess 与 target 进行比较。String.jaro_distance/2 是衡量两个字符串相似度的指标，返回值介于0到1之间，1表示两字符串完全相同。

由于只有当两个字符串完全相同时，适应度函数才返回1，因此可以安全地认为，当某个染色体的适应度为1时，我们就找到了正确的密钥。

因此，我们的终止条件如下：

1def terminate?(population, _generation), do:
2  Enum.max_by(population, &Codebreaker.fitness_function/1).fitness == 1

运行算法

在模块定义下方添加以下代码：

1soln = Genetic.run(Codebreaker, crossover_type: &Toolbox.Crossover.single_point/2)
2
3{key, ""} =
4  soln.genes
5  |> Enum.map(& Integer.to_string(&1))
6  |> Enum.join("")
7  |> Integer.parse(2)
8
9IO.write "\nThe Key is #{key}\n"

算法完成后，即可运行。不过，我们先尝试在不使用变异的情况下运行几代，可通过运行以下程序进行测试：

警告出现的原因是我们尚未在指定函数中使用 opts 参数。这将在接下来的几章中完成。

验证密钥

为了确认此密钥确实是正确的，可以用它来解密加密字符串。为此，打开下方终端，启动 iex 交互环境，依次输入以下命令：

1use Bitwise
2key = keyNumber # 通过运行上述带变异的应用程序获得
3cipher = fn word, key -> Enum.map(word, & rem(bxor(&1, key), 32768)) end
4List.to_string(cipher.('LIjs`B`k`qlfDibjwlqmhv', key))

注意：上述 keyNumber 是运行带变异功能的应用程序后得到的密钥。

如果最终输出为 "ILoveGeneticAlgorithms"，恭喜你，成功破解了密码！