介绍N皇后问题

了解八皇后问题

想象一下，你的朋友向你发起挑战：在标准棋盘上摆放八个皇后，使得它们彼此之间不会互相攻击。这个问题被称为N-queens，是一个典型的约束满足问题，类似于课程中介绍的“优化货物装载”问题。在N-queens问题中，目标是在一个棋盘上放置N个皇后，使得没有任何一个皇后能够威胁到另一个皇后。在国际象棋中，当一个棋子可以移动到某个格子并“吃掉”该位置的棋子时，就称其处于被威胁状态。皇后可以沿水平、垂直和对角线方向任意距离移动。由于皇后可以在水平和垂直方向上自由移动，因此在一个 N×N 的棋盘上放置 N 个互不冲突的皇后时，唯一的方式是每一行、每一列各放置一个皇后。

下图展示了一个在8×8棋盘上成功解决八皇后问题的方案：

N-queens是一个组合优化问题，而我们已经知道遗传算法非常适合解决这类问题。我们将尝试用遗传算法求解N-queens问题，以展示在算法中采用良好交叉策略的重要性。

创建初始的N-queens模型

我们首先在scripts文件夹中新建一个名为n_queens.exs的文件。在这个文件中，我们将编写N-queens问题的编码，并运行算法以获得解决方案。

在n_queens.exs中，定义模块并指定Problem行为，如下所示：

1defmodule NQueens 
2  @behaviour Problem 
3  alias Types.Chromosome
4  
5  # 其余内容在此处
6end

实现基因型

记住，为了正确实现Problem行为，我们需要定义三个函数。第一个是genotype/0，它返回算法将使用的基因型。一开始，你可能会想使用二进制基因型，其中每个索引表示该位置是否有皇后。但更聪明的做法是使用一个长度为8的排列来表示每个皇后的具体位置。例如，解[0, 2, 1, 3, 6, 4, 7, 5]表示棋盘上的如下布局：

为了创建一个排列型基因型，在NQueens模块中添加以下函数：

1@impl true
2def genotype do
3  genes = Enum.shuffle(0..7)
4  %Chromosome{genes: genes, size: 8} 
5end

Enum.shuffle/1函数会随机打乱给定的可枚举集合。在这里，我们传入范围0..7，表示一个长度为8的排列。

接下来，定义适应度函数。

实现适应度函数

记住，我们的目标是配置棋盘，使所有棋子之间没有冲突。目标是最小化这些冲突。因此，适应度函数应以某种方式衡量冲突的数量。

为此，需要检查每行和每条对角线上的情况。虽然我们的基因型已经确保皇后不会出现在同一列，但它们仍可能出现在同一行。

我们的适应度函数应如下所示：

1@impl true
2def fitness_function(chromosome) do
3  diag_clashes =
4    for i <- 0..7, j <- 0..7 do
5      if i != j do
6        dx = abs(i - j)
7        dy = abs(Enum.at(chromosome.genes, i) - Enum.at(chromosome.genes, j))
8        if dx == dy do
9          1
10        else
11          0
12        end
13      else
14        0
15      end
16    end
17  length(Enum.uniq(chromosome.genes)) - Enum.sum(diag_clashes)
18end

首先计算解中的对角线冲突数量。然后，过滤掉染色体中重复的值，因为这些重复代表了行冲突。最后，返回两者之差。适应度函数将返回非冲突的数量，即不与其他任何棋子冲突的棋子数量。

最后一步是定义终止条件。

定义终止条件并运行算法

由于适应度函数返回的是非冲突数量，当种群的最大适应度达到8时，算法即完成。换句话说，当棋盘上没有任何冲突时，算法结束。

你的终止条件如下：

1@impl true
2def terminate?(population, _generation), do:
3  Enum.max_by(population, &NQueens.fitness_function/1).fitness == 8

为了运行算法，在模块定义下方添加以下代码：

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

通过运行以下应用来测试完整代码：

目前我们仅在initialize和select函数中使用了opts参数，而在其他函数中未使用；因此出现了关于opts的警告。

为什么会这样？我们的解在达到最大可能适应度之前就停滞了。

问题出在交叉函数生成了无效的染色体。目前，我们的框架使用单点交叉，但这并不能保持排列结构的完整性。因此，我们需要实现一种适用于排列的交叉策略。