创建课程表

引言

选择、交叉和变异这三个步骤都会接收一组染色体，并以某种方式对这组染色体进行变换，从而生成新的一组染色体。此时，我们可以将种群划分为三类：父代、子代和剩余个体。

我们有三组染色体可供选择，需要以某种方式将它们组合起来，使得新种群既能保留旧染色体的优势，又能融合新染色体的优点。理想情况下，优秀的选择、交叉和变异策略能够有效捕捉到前几代中的最强特征，并将其结合以产生更强大的后代；然而，将这些步骤的产物整合成新种群的过程，对于进化的成功至关重要。

将选择、交叉和变异的产物合并为新种群的过程被称为重插入或替换。这两个术语基本含义相同；不过，我们将在本章后续部分学习其中的一些细微差别。

在本章剩余部分，我们将通过一个实际问题来探索多种重插入与替换方法：为下个学期制定最佳课程表。

设置你的课程表

想象一下，你正在决定秋季学期要注册哪些课程。以下课程可供注册：算法、人工智能、微积分、化学、数据结构、离散数学、历史、文学、物理和排球。但你每次最多只能修读18个学分。为了帮助决策，我们使用1到10的评分标准，公平地评估每门课程的难度、对你个人的实用性以及你对它的兴趣。目标是根据这些标准制定出最优的课程安排，同时满足学分限制。我们已经根据下表为每门课程分配了权重：

这是一个具有多个目标的约束优化问题，因此非常适合用遗传算法来解决。

首先，在 scripts 目录中创建一个新文件 schedule.exs。接着，在 schedule.exs 中定义一个基本的 Problem 实现，如下所示：

1defmodule Schedule do 
2  @behaviour Problem 
3  alias Types.Chromosome
4
5  @impl true
6  def genotype, do: # ...
7
8  @impl true
9  def fitness_function(chromosome), do: # ...
10
11  @impl true
12  def terminate?(population, generation), do: # ...
13end

现在，剩下的工作就是实现这三个函数并运行算法。

表示课程表

表示课程表最简单的方式是使用二进制基因型。二进制基因型可以确保染色体的长度固定，即使课程数量发生变化也保持不变。

在这种情况下，每个索引代表一门特定的课程。该索引处的值（1 或 0）表示是否选修这门课程。例如，课程表 [1, 1, 0, 0, 0, 1, 0, 0, 1, 1] 表示选修了算法、人工智能、离散数学、物理和排球。

我们将在构建应用程序框架时实现 genotype/0 函数，如下所示：

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

这与我们在“One-Max问题”中学过的方法类似。我们使用 for 推导式创建一个长度为 10 的二进制基因型。

评估课程表

评估课程表有些复杂。首先，我们需要对所有标准——难度、实用性与兴趣——进行同等加权。其次，显然我们希望最大化兴趣和实用性，同时最小化难度。第三，构造课程表时必须考虑18学分的限制。

每个标准的权重相等，因此难度、实用性和兴趣各占一门课程最终评分的33%。我们可以利用这些权重，将每门课程的加权标准得分相加，得到整个课程表的适应度。此外，还需要为未满足学分要求的课程表引入惩罚机制。由于课程表可能得分为负数，因此我们的惩罚值应是一个非常大的负数，比如 -99999。

实现 fitness_function/1 如下：

1def fitness_function(chromosome) do
2  schedule = chromosome.genes
3  fitness =
4    [schedule, difficulties(), usefulness(), interest()]
5    |> Enum.zip()
6    |> Enum.map(
7        fn {class, diff, use, int} ->
8          class * (0.3*use + 0.3*int - 0.3*diff)
9        end
10      )
11    |> Enum.sum()
12  credit =
13    schedule
14    |> Enum.zip(credit_hours())
15    |> Enum.map(fn {class, credits} -> class * credits end)
16    |> Enum.sum()
17
18  if credit > 18.0, do: -99999, else: fitness
19end
20
21defp credit_hours, do: [3.0, 3.0, 3.0, 4.5, 3.0, 3.0, 3.0, 3.0, 4.5, 1.5]
22defp difficulties, do: [8.0, 9.0, 4.0, 3.0, 5.0, 2.0, 4.0, 2.0, 6.0, 1.0]
23defp usefulness, do: [8.0, 9.0, 6.0, 2.0, 8.0, 9.0, 1.0, 2.0, 5.0, 1.0]
24defp interest, do: [8.0, 8.0, 5.0, 9.0, 7.0, 2.0, 8.0, 2.0, 7.0, 10.0]

这里发生了不少事情。首先，在函数外部定义了各项指标的数值，以提高代码可读性（第21至24行）。然后在第5行使用 Enum.zip/1 将所有数据合并为元组。接着在第6至10行使用 Enum.map/2 根据各项指标和课程是否被选修来计算每门课程的得分。最后在第12至18行计算课程表的总学分数，若超过限制，则返回 -99999；否则返回 fitness 值。

接下来只需定义一些终止条件并运行算法即可。

终止与运行

由于我们不知道最优课程表的确切适应度值，因此将基于代数来终止。1000代已足够，但我们也可以尝试运行更多或更少的代数。实现 terminate?/2 如下：

1def terminate?(_population, generation), do: generation == 1000

接下来，我们需要运行算法。在 schedule.exs 文件中 Schedule 模块下方添加以下内容（第41至44行）：

1soln = Genetic.run(Schedule)
2
3IO.write("\n") 
4IO.inspect(soln.genes)

现在运行算法并测试应用：

当前唯一出现的警告信息来自 opts 参数，它在 evaluate 函数中尚未使用。

现在，尝试不同的重插入策略，观察它们对进化过程的影响。