深入探究遗传算法

遗传算法结构

基于我们目前已掌握的知识，可以理解到每个遗传算法都遵循相同的基本步骤。尽管针对不同问题的算法可能采用不同的技术、概率或策略，但它们都共享相同的结构。作为程序员，我们应该充分利用这一点。

编程中的黄金法则之一是“不要重复自己”（DRY），其核心思想是避免重复编写不必要的代码。我们可以利用遗传算法之间的共性结构，避免在不同算法之间重复编写相同的部分。遗憾的是，我们必须从零开始。

那么，如何从头设计一个通用的框架呢？从基础开始。所有遗传算法都遵循相同的结构：它们都使用染色体和种群，并且都需要类似的输入。我们可以利用这一点，自底向上地进行设计。

染色体与种群

染色体代表问题的解。在 One-Max 问题中，我们的解由一系列 0 和 1 组成。然而，并非所有问题都是如此。有些问题使用实数值编码，有些使用排列编码，还有些使用字符编码。此外，某些问题需要使用列表以外的数据结构来表示解。

这意味着具体的编码方式因问题而异，各不相同。我们可以利用 Enumerable 协议，使框架尽可能通用，从而适用于各种编码方式。

在 Elixir 中，协议允许我们在库中实现多态性。任何实现了 Enumerable 协议的数据结构都可以传递给 Enum 库中的任意函数。这意味着我们可以使用任何实现了 Enumerable 的数据结构来编码染色体——包括我们自己构建的数据结构。

另一方面，种群只是染色体的集合。下图展示了染色体与种群之间的区别：

在大多数情况下，种群的编码方式不会改变。只要种群是由一系列染色体组成，具体使用哪种数据结构并不重要。为简化起见，本课程使用列表来存储染色体。

此外，种群的大小并不关键。较大的种群在变换时耗时更长，但可能更快收敛到最优解；较小的种群更容易处理，但可能需要更长时间才能收敛。

基于目前的理解，我们可以开始制定框架必须遵守的一些规则，例如：

• 为了实现多态性，应使用实现了 Enumerable 协议的数据结构来编码染色体。

• 因为种群以列表形式存储，所以可以使用 Enum 或 List 库中的任意函数来实现变换操作。

• 算法应能适用于任意大小的种群。

通过强制执行这些规则，我们将能够将框架扩展到多种不同类型的问题。

初始化种群

每个遗传算法的第一步是初始化种群。通常，初始种群是随机生成的——就像在搜索空间中随机撒点一样。其目的是从大量不同的解开始探索，逐步逼近最优解。

我们已经确定种群是一个列表，因此这一步骤所实现的函数必须返回一个染色体列表。但我们必须确保该函数适用于所有类型的问题，而不包含关于染色体编码的具体细节。为此，我们可以将一个生成染色体的函数作为输入参数。

Elixir 允许我们将函数作为参数传递给其他函数。我们可以确保其中一个参数是一个返回染色体的函数。我们不关心这个函数的具体实现方式，只关心它能返回一个染色体。

通过这一步，我们有两个主要目标：

• 初始化步骤必须生成一个初始种群，即一组可能的解。

• 用于初始化种群的函数应与染色体的具体编码方式无关。为此，我们可以接受一个返回染色体的函数作为参数。

评估种群

评估步骤负责根据某个适应度函数对每个染色体进行评估，并按适应度对种群进行排序。这使得提取最佳染色体变得容易，也便于在选择步骤中处理种群。

正如编码方式因问题而异，适应度函数也是如此。不同问题对“解的好坏”有不同的衡量标准。如果我们试图寻找两点之间的最短路径，就会根据路径长度来评估解；如果我们要优化一个股票投资组合，则会根据预期收益来评估组合。本质上，我们不关心适应度函数是如何实现的，也不关心它返回什么值——我们只需要一个能够比较各个染色体之间适应度的度量标准。

这为我们带来了评估步骤的以下目标或要求：

• 评估步骤必须以种群作为输入。

• 评估步骤必须返回按适应度排序后的种群。

• 用于评估种群的函数应接受一个参数，该参数是一个返回每个染色体适应度的函数。

• 适应度函数可以返回任意类型的值，只要这些值可以被排序即可。