理解与创建染色体

使用结构体表示染色体

在课程《构建遗传算法框架》中，我们设计了一个编写遗传算法的框架。该框架概括了所有遗传算法共有的步骤。本练习的目的在于更深入地理解遗传算法和优化问题的结构，并使我们未来编写遗传算法更加便捷。

我们在前几章创建的染色体是可枚举的对象，代表问题的解决方案。从最基本层面来看，这是正确的。然而，在实际应用中，这种实现方式并不可行。

考虑这样一个问题：染色体的年龄决定了其适应度。我们这样做的一个原因是确保代际之间有足够的差异性。理想情况下，我们希望在一定条件下保留较老的染色体，直到它们达到某个年龄后才被淘汰。通过这种方式，我们可以保证种群中既有老的也有年轻的染色体，从而自然产生变异。

仅使用 Enum 类型来表示染色体会导致不必要的复杂性。通常情况下，我们需要一种更强大的数据结构来同时跟踪多个指标。在 Elixir 中，我们可以使用结构体（struct）来实现这一目标。

结构体是一种带有若干附加特性的映射（map）。结构体允许我们定义默认值和必填字段，且在创建后不能添加额外字段。结构体提供的这些保障使其成为定义自定义类型的理想选择，而无需担心程序出错。借助结构体，我们可以确保染色体类型在初始化时拥有预设的一组基因，从而不会破坏我们的遗传算法。

使用结构体表示染色体带来了许多便利，而如果仅用 Enum 或其他数据类型则无法实现。例如，若要计算种群的平均适应度，我们必须先重新计算每个染色体的适应度，这可能是一项计算成本较高的任务。但通过结构体，我们可以只计算一次适应度，并将其作为键值对存储在结构体内，从而节省时间。

理解染色体

在创建用于建模染色体的结构体之前，我们首先需要理解染色体的本质及其特征。

从最基本的角度看，染色体是问题的一个单一解。它由一系列基因组成，这些基因包含称为等位基因的值。基因可以代表任何事物。例如，在前一章《编写你的第一个遗传算法》中提到的运输问题里，每个基因代表城市中的一个停靠点。整个染色体则表示一条遍历所有定义城市的完整路径。

基因通常以列表或其他可枚举数据类型（如树、集合、数组）表示。在 Elixir 中，Enum 模块提供了大量用于操作实现了 Enumerable 协议的数据类型的实用函数。事实上，我们在前一章编写的框架完全依赖于 Enum 模块的函数。因此，我们能够使用任何实现了 Enumerable 协议的数据类型来表示基因——即使这些类型不属于 Elixir 标准库。

虽然基因是染色体最基本的组成部分，但我们还可以追踪一些额外的特性，以提升便利性和功能性。一个基础的染色体结构体可以包含适应度、大小和年龄，除了基因之外。为简化起见，本课程中的染色体结构体将仅包含这些特性。在后续章节中，我们将看到追踪这些特性的便利之处。

我们可以添加到染色体结构体中的特性没有限制。某些问题可能需要本章未提及的额外功能。幸运的是，结构体的美妙之处就在于其灵活性。采用这种表示方式，我们可以快速调整以满足每个问题的需求。

创建染色体结构体

打开终端，进入 genetic/lib 目录。在此目录下创建一个名为 types 的新文件夹，以及一个名为 chromosome.ex 的新文件，如下所示：

1mkdir types
2touch types/chromosome.ex

在 types/chromosome.ex 文件中创建染色体结构体。打开该文件并添加以下代码：

1defmodule Types.Chromosome do
2  defstruct [:genes, :size, :fitness, :age]
3end

这段代码定义了一个模块 Types.Chromosome，其中包含一个由 :genes、:size、:fitness 和 :age 四个键组成的结构体。记住，defstruct 用于定义新的结构体。紧跟其后的原子即为结构体所包含的字段。我们可以使用 %Types.Chromosome 语法创建新的染色体结构体。

当前版本的染色体结构体虽然可用，但功能略显不足。目前所有字段都没有默认值，也没有强制要求的键。这意味着新创建的染色体结构体可能包含全部为 nil 的字段。

我们可以通过为 :size、:fitness 和 :age 添加默认值来改进这一点，如下所示：

1defstruct [:genes, size: 0, fitness: 0, age: 0]

现在，每个新创建的染色体都将具有默认大小、适应度和年龄值 0。我们也可以根据需求设置任意默认值。

最后，所有染色体都必须包含基因。如果没有基因，那就不算是真正的染色体。为了确保染色体必须包含基因，请在 defstruct 之前添加以下代码：

1@enforce_keys :genes

最终的模块应如下所示：

1defmodule Types.Chromosome do
2  @enforce_keys :genes
3  defstruct [:genes, size: 0, fitness: 0, age: 0]
4end

现在，我们可以创建能追踪染色体种群中基因、大小、适应度和年龄的染色体结构体。

创建染色体类型

Elixir 是一种动态类型语言；然而，为自定义数据类型创建类型规范（typespec）通常非常有用。类型规范有助于文档编写，并支持使用 dialyzer 等工具进行静态代码分析。本课程不会讲解 dialyzer 的使用，但我们会将在本课中创建的类型用于后续章节。

类型规范使用 @type 属性定义，后接类型名称和定义。Elixir 支持复合类型，也支持使用结构体创建自定义类型。

在 types/chromosome.ex 文件中创建你的染色体类型。打开该文件，并在上一节定义的结构体之前添加以下代码：

1@type t :: %__MODULE__{
2  genes: Enum.t,
3  size: integer(),
4  fitness: number(),
5  age: integer()
6}

这段代码定义了一个自定义类型 t，它是 Types.Chromosome 结构体的一个实例。__MODULE__ 是一个宏，会被替换为定义它的模块名称。使用 t 作为类型名称是 Elixir 中定义模块类型的标准做法。

该染色体类型还为染色体的各个字段声明了具体类型。如前所述，基因必须是 Enum 类型。大小和年龄均为整数。适应度是 number 类型，这是 Elixir 内置类型，表示浮点数或整数。

最终的 Chromosome 模块如下所示：

1defmodule Types.Chromosome do
2
3  @type t :: %__MODULE__{
4    genes: Enum.t,
5    size: integer(),
6    fitness: number(),
7    age: integer()
8  }
9
10  @enforce_keys :genes
11  defstruct [:genes, size: 0, fitness: 0, age: 0]
12end

练习

让我们通过一个小测验来检验你对本课所讲概念的理解：