4-EightQueens

The eight queens puzzle 八皇后问题

image-20260927133203679

  • Task: place 8 queens on an 8 by 8 chessboard

    任务：将 8 个皇后放置在一个 8×8 的国际象棋棋盘上。

  • Goal: no two queens attack each other

    目标：任意两个皇后都不能相互攻击。

  • Brute force: 64636261605958*57 = 178,462,987,637,760

    暴力搜索：64×63×62×61×60×59×58×57 = 178,462,987,637,760

    • 8765432*1 = 40,320

      利用每行/每列仅放一个皇后的限制：8×7×6×5×4×3×2×1 = 40,320

The eight queens puzzle: EA 八皇后问题

  • Represent the problem solution? phenotype? genotype?

    如何表示问题的解？ phenotype？genotype？

  • Evaluate fitness?

    评估fitness？

  • Recombination and mutation?

    Recombination 和 mutation?

The eight queens puzzle: representation 八皇后问题：表示方式

image-20260927133424499

  • Phenotype a board configuration

    表现型（Phenotype）：棋盘配置（棋盘上皇后的实际摆放布局）。

  • Genotype a permutation of the numbers 1 to 8

    基因型（Genotype）：数字 1 到 8 的一个排列（如 1 3 5 2 6 4 7 8，表示各行/各列皇后的位置编码）。

  • Representation is not just a way of storing a solution. It builds problem knowledge into the search

    表示方式不仅仅是存储解的一种方式，它还将问题领域的先验知识融入到了搜索过程中。

    The eight queens puzzle: fitness 八皇后问题：适应度

    • Penalty of a configuration: the number of attacking queen pairs

      一个配置的惩罚值：相互攻击的皇后对数量。

    • Penalty is to be minimized

      惩罚值需要被最小化。

    • Fitness of a configuration: to be maximized

      一个配置的Fitness：需要被最大化。

      • maximum possible number of non-attacking pairs — number of attacking pairs

        最大可能的不相互攻击皇后对数量 − 相互攻击的皇后对数量（即 28−攻击对数28 - \text{攻击对数}）。

      • or fitness = — penalty

        或者，适应度 = −惩罚值。

    Penalty和Fitness是对同一个候选解的两种表达方式

    进化算法通常采用“Fitness越大越好”的形式，因此可以把Penalty转换为Fitness：

    Fitness=−Penalty\text{Fitness}=-\text{Penalty}

    或者：

    Fitness=28−Penalty\text{Fitness}=28-\text{Penalty}

The eight queens puzzle: mutation 八皇后问题：变异

  • Operates on the genotype

    作用于genotype。

  • Small variation in one permutation

    对一个排列进行小幅变化。

    • swapping values of two randomly chosen positions

      交换两个随机选定位置上的值（如将 1 3 5 2 6 4 7 8 中选中的 5 和 7 互换，变为 1 3 7 2 6 4 5 8）。

    image-20260927133724171

The eight queens puzzle: recombination 八皇后问题：重组

  • Operates on the genotype

    作用于genotype。

  • Combine two permutations into two new ones

    将两个排列组合成两个新的排列

    • choose random crossover point

      随机选择一个交叉点

    • copy first parts into offspring

      将前半部分复制到offspring 中

    • create second part by inserting values from the other parent (in the original order, beginning after crossover point, skipping values already in the offspring)

      通过插入另一个父代的数值来构造后半部分（从交叉点之后开始，按原有顺序读取，跳过offspring中已经存在的数值）

    • “cut and crossfill”

      “切割与交叉填充”（保证生成的新子代仍然是 1 到 8 的合法无重复排列）

      crossover是 recombination的其中一种方法

image-20260927134231476

The eight queens puzzle: selection 八皇后问题：选择

  • Parent selection

    父代选择

    • Pick five parents and take the fittest two to undergo crossover and mutation

      选出 5 个父代候选个体，并从中挑选fittest 最高的 2 个进行交叉和变异。

  • Survivor selection

    幸存者选择

    • Insert new offspring into the population to replace existing members by

      将新产生的子代放回种群，用它们替换已有个体，具体方法是：

      • sort the individuals in the five contestants from best to worst

        将 5 个竞争个体按照从最好到最差排序；

      • then use the two offspring to replace the two worst contestants

        然后用两个子代替换其中最差的两个竞争个体。

The eight queens puzzle: summary 八皇后问题：总结
Representation Permutations 表示方式：排列编码（保证每行每列仅有一个皇后）
Recombination ‘Cut-and-crossfill’ crossover 重组方式：“切割与交叉填充”交叉算子
Recombination probability 100% 重组概率：100%
Mutation Swap 变异方式：对调/交换变异（Swap）
Mutation probability 80% 变异概率：80%
Parent selection Best 2 out of random 5 父代选择：从随机抽取的 5 个个体中选取最好的 2 个
Survival selection Replace worst 幸存者选择：替换最差的个体
Population size 100 种群规模：100
Number of offspring 2 生成的offspring数量：2
Initialisation Random 初始化方式：随机生成初始排列
Termination condition Solution or 10,000 fitness evaluations 终止条件：找到合法解，或完成 10,000 次fitness评估

Table 3.4. Description of the EA for the eight-queens problem（表 3.4：用于八皇后问题的进化算法说明）

EA design EA 设计（进化算法设计）

  • Representation - What properties should every candidate satisfy?

    表示方式——每个 candidate候选解应该满足哪些性质？

  • Mutation - How can we make a small change while remaining feasible?

    Mutation——如何在保持可行的同时进行小幅改变？

  • Recombination - How can we combine parents without violating feasibility?

    Recombination——如何组合父代而不违反可行性约束？

  • Fitness - How do we measure progress?

    Fitness——如何衡量搜索进展？

  • There is no single EA - Design an EA means making a series of choices that fit the problem

    不存在唯一的一种 EA——设计一个 EA 意味着做出一系列适合具体问题的选择

  • Each choice should be justified by the problem representation and the search behavior we want

    每个选择都应该根据问题的表示方式和我们希望得到的搜索行为来进行论证