优化货物装载

种群评估概述

每个问题都有一个目标。优化的目标是最大化或最小化某个值，而搜索的目标是找到通往目标的路径。优化与搜索之间的共同点在于它们都围绕着一个明确的目标。

我们的目标就是最终目的地——遗传算法的最终目标。有时我们可能并不确切知道最终目标的样子，但仍需要一种方式来判断自己是否朝着正确的方向前进。如果你玩过“热或冷”这个游戏，就会明白这种感觉。作为规则的回顾：你寻找一个物体，有人会通过告诉你“热”（接近物体）或“冷”（远离物体）来给出线索。“热”和“冷”是对当前位置的基本评估，它们帮助你持续朝正确方向移动，而无需真正知道最终要去哪里。

在遗传算法中，适应度函数告诉我们当前处于“热”还是“冷”的状态。我们用它们作为衡量进度的标尺，以判断离最优解有多近。

因此，在遗传算法的每一代开始时，都需要对当前种群进行评估。评估步骤对于确保算法朝着最佳解前进至关重要。在课程《理解超参数》中，我们定义了 lib/genetic.ex 中的 evolve/3 函数。回顾该函数：

1def evolve(population, problem, opts \\ []) do
2  population = evaluate(population, &problem.fitness_function/1, opts) 
3  best = hd(population)
4  IO.write("\rCurrent best: #{best.fitness}")
5  if problem.terminate?(population) do
6    best
7  else
8    population
9    |> select(opts)
10    |> crossover(opts)
11    |> mutation(opts)
12    |> evolve(problem, opts)
13  end 
14end

在这段代码中，种群被评估了两次。第一次出现在函数体的第一行，形式如下：

1population = evaluate(population, &problem.fitness_function/1, opts)

这行代码立即通过调用 evaluate/2 函数，将传入 run/2 函数的 population 变量转换为基于特定问题适应度函数的评估结果。

第二次评估则稍显隐蔽。注意 if 条件，它决定了何时停止进化并返回最佳解。该条件调用了 problem.terminate?/1，根据某些特定于问题的参数评估种群，并决定是否继续演化。

适应度函数和终止条件是遗传算法中评估解决方案的两种手段。适应度函数告诉我们一个解的好坏程度，而终止条件则告诉我们何时停止算法并返回结果。通常情况下，我们的终止条件与种群中的最高适应度值相关联。适应度函数和终止条件在构建有效的遗传算法以解决实际问题时同等重要。

在本章中，我们将从一个新的问题类型入手，展示设计良好适应度函数的重要性，并学习如何针对不同问题使用常见技术来构建适应度函数。此外，我们还将学习如何定义终止条件，使算法在找到最佳解后停止搜索。

货物装载示例

假设你供职于一家航运公司，公司要求你确定如何合理装载不同种类的货物，以实现利润最大化，同时不超过指定的重量限制。你有十种产品，分别标记为“A”到“J”，对应的重量为：[10, 6, 8, 7, 10, 9, 7, 11, 6, 8]。每种产品的利润边际分别为：[6, 5, 8, 9, 6, 7, 3, 1, 2, 6]，货物总重量限制为 40。

下图展示了各货物及其对应的重量和利润。你需要确定应装载哪些产品，以在不超出重量限制的前提下实现最大利润。

这个问题是“背包问题”的一种变体。背包问题属于一类称为约束满足问题（Constraint Satisfaction Problems, CSPs）的优化问题。这类问题要求我们在一组约束条件下优化某个目标值。约束条件是对解施加的限制。例如，在上述问题中，你的利润受到卡车所能承载货物总量的限制。

货物装载实现

为了开始解决这个问题，请创建一个新文件 cargo.exs，并在其中添加一个新的 Problem 实现：

1defmodule Cargo 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), do: # ...
13
14end

首先，确定如何表示解。你有10类货物可以装载上船。每类货物只有两种选择：装载或不装载。你可以用长度为10的二进制基因型来表示配置。例如，解 "1011000010" 表示你装载了“产品A”、“产品C”、“产品D”和“产品I”。

按如下方式实现基因型：

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

接下来，实现适应度函数。你的目标是最大化利润，因此适应度函数必须与盈利能力相关。你需要考虑重量因素，但可以稍后再处理。

你的适应度函数应计算所提议货物配置带来的总利润。实现如下：

1def fitness_function(chromosome) do 
2  profits = [6, 5, 8, 9, 6, 7, 3, 1, 2, 6] 
3  profits
4  |> Enum.zip(chromosome.genes)
5  |> Enum.map(fn {p, g} -> p * g end)
6  |> Enum.sum()
7end

这里，你将每种产品的潜在利润乘以1或0，取决于该产品是否包含在货物配置中。然后对列表求和，得到总利润。

最后一步是实现终止条件。如果你能将所有货物装上卡车，理论上能达到的最大总利润是53。目前，你的终止条件如下：

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

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

1soln = Genetic.run(Cargo, population_size: 50)
2
3IO.write("\n")
4IO.inspect(soln)
5
6weight =
7  soln.genes
8  |> Enum.zip([10, 6, 8, 7, 10, 9, 7, 11, 6, 8])
9  |> Enum.map(fn {g, w} -> w*g end)
10  |> Enum.sum()
11
12IO.write("\nWeight is: #{weight}\n")

在此片段中，你以50人的种群规模运行算法，获得一个解。接着，检查该解以查看最佳配置是什么。最后，计算该配置的总重量，并将结果输出到控制台。

测试你的应用程序

接下来，运行以下程序以查看问题的结果：

我们的结果包括最佳适应度值，本例中为53。随后是匹配该适应度值的染色体，其基因由一系列1和0组成，表示可装载以最大化利润且不超出总重量限制的产品。在本例中，所有从A到J的产品都可以装载（基因列表全为1），因为当前的适应度函数只计算总利润，全部装载时利润达到最高（此时总重量为82，已超过40的重量限制，只是尚未被惩罚）。

然而，虽然你的利润很高，但重量也严重超标。你的解决方案未能正确处理给定的约束条件。本质上，你只是重新实现了“One-Max”问题。你需要采用另一种技术来处理约束：惩罚函数。