【原】遗传算法Python实战 004.八皇后问题

godxiasad 2023-04-21 发布于北京

展开全文

遗传算法Python实战 004.八皇后问题

写在前面的话

本节我们主要讲解如何使用遗传算法解决八皇后问题

八皇后是算法界一个非常常见的问题，也经常用于各种大厂的面试中，题目如下：

在 8×8 格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法：

比如，我们在第一个位置上，放好一个皇后，那么蓝色的位置就不能在放置了：

只能在空白的地方挑选一个位置来放，比如：

之后，蓝色区域继续扩大，第三个也只能继续去找白色区域摆放：

比如下面就是其中的一种经典解法：

根据维基百科的说法，这个谜题只有92个答案，而把那些相似的变种（比如镜像和旋转）删掉，就只有12个特定的解决方案。

根据排列组合的算法，理论上皇后摆放的位置，有64×63×62×62×61×60×59×58×57中可能……我就不去计算了，如果不进行收敛而采用遍历的话，那几乎是一个不可能完成的任务。

如果用遗传算法来解决，我们会发现，每一次选择，不仅仅是个别基因的问题，而是会带来相互之间的约束，特别是算法不知道基因彼此之间的关系，我们就必须设计好各种约束条件。

前面几节的内容，有一个特点，就是基因本身的选择就是解决方案本身，所以我们只需要把选择结果进行比较，或者就展现出来就可以了。

但是很多的分析没有这么简单，他们有各式各样的约束和表达，所以在比较高的层次上，把最初的基因编码称之为基因型，而把最终形式称之为表型。

基因型

基因型是对问题的各个部分进行编码的方式，以便可以通过遗传算法以及功能函数对其进行操作。比如在八皇后问题上，基因型的示例如下：

首先设计一个64bit的变量，每个bit表示棋盘上的64个方格中的一个
其次是一个48bit的变量，其中每个王后位置为6 bit
然后是8个整型变量，范围为0到63或1到64
最后是16个整型变量，表示每个皇后的行和列位置

表型

表型就是如何使用已编/解码的基因来解决问题。比如在上面的每个示例中，表型如下：

板上8个皇后的位置。
适应度函数：即在要解决的问题中，评估表型以返回适应度对供功能函数的价值所用。

下面进入编码环节

首先还是一样，定义我们的基因库，这里用8个整数：0-7来表达就行：

size = 8
geneSet = [i for i in range(size)]

然后定义一个棋盘类，用来模拟棋盘：这个类一共有三个方法，分别是

初始化函数，功能是通过你传入的解（基因组成的染色体），来构造当前棋盘和皇后的位置。
get函数，通过输入行列号，来获取棋盘当前位置上是否有棋子。
print函数，用来输出当前棋盘上面的效果

class Board:
    def __init__(self, genes, size):
        board = [['.'] * size for _ in range(size)]
        for index in range(0, len(genes), 2):
            row = genes[index]
            column = genes[index + 1]
            board[column][row] = 'Q'
        self._board = board

    def get(self, row, column):
        return self._board[column][row]

    def print(self):
        for i in reversed(range(len(self._board))):
            print(' '.join(self._board[i]))

比如我构造这样一组基因组成的染色体：

x = [0,0,0,1,0,2,0,3,0,4,0,5,0,6,0,7]

单数的索引代表列，双数的索引，代表行，这组染色体就表示把8个皇后全部摆在第0列上，运行结果如下:

Q  .   .   .   .   .   .   .
Q  .   .   .   .   .   .   .
Q  .   .   .   .   .   .   .
Q  .   .   .   .   .   .   .
Q  .   .   .   .   .   .   .
Q  .   .   .   .   .   .   .
Q  .   .   .   .   .   .   .
Q  .   .   .   .   .   .   .

或者都摆在第0行上(注意，国际象棋和中国象棋一样，下面表示朝向你这边的面，为起始行）：

x = [0,0,1,0,2,0,3,0,4,0,5,0,6,0,7,0]

运行结果如下:

 .   .   .   .   .   .   .   .
 .   .   .   .   .   .   .   .
 .   .   .   .   .   .   .   .
 .   .   .   .   .   .   .   .
 .   .   .   .   .   .   .   .
 .   .   .   .   .   .   .   .
 .   .   .   .   .   .   .   .
 Q   Q   Q   Q   Q   Q   Q   Q

定义个显示当前进化情况的方法，主要是染色体、耗时和基因健壮性（或者叫适配性）

def display(candidate, startTime, size):
    timeDiff = datetime.datetime.now() - startTime
    board = Board(candidate.Genes, size)
    board.print()
    print("{0}\t- {1}\t{2}".format(
        ' '.join(map(str, candidate.Genes)),
        candidate.Fitness,
        str(timeDiff)))

然后是老规矩的染色体类和进化变异函数：

从这里就可以看出遗传算法的鲁棒性来了，核心函数从来不用修改，在所有地方都适用

class Chromosome:
    def __init__(self, genes, fitness):
        self.Genes = genes
        self.Fitness = fitness
        
def mutate(parent):
    childGenes = parent.Genes[:]
    index = random.randrange(0, len(parent.Genes))
    newGene, alternate = random.sample(geneSet, 2)
    childGenes[index] = alternate if newGene == childGenes[index] else newGene
    fitness = get_fitness(childGenes,size)
    return Chromosome(childGenes, fitness)

下面是最关键的健壮性验证方法，所有的遗传算法里面，这个方法都是最关键的，它用于评价你这次进化的效果好不好：

他的验证逻辑很简单：

首先定义四个Set，分别表行、列、左对角线和右对角线（Set的特点是不会出现重复值）。
然后开始从构建好的染色体里面去查看当前皇后的位置，每获得一个皇后，就把它能够攻击到的所有位置都加入到这些Set里面去。
计算当前棋盘上有多少个位置发生了重复。

可以看见，如果结果为0，则表示得到了正确的八皇后解。

def get_fitness(genes, size):
    board = Board(genes, size)
    rowsWithQueens = set()
    colsWithQueens = set()
    northEastDiagonalsWithQueens = set()
    southEastDiagonalsWithQueens = set()
    for row in range(size):
        for col in range(size):
            if board.get(row, col) == 'Q':
                rowsWithQueens.add(row)
                colsWithQueens.add(col)
                northEastDiagonalsWithQueens.add(row + col)
                southEastDiagonalsWithQueens.add(size - 1 - row + col)
    total = size - len(rowsWithQueens) \
            + size - len(colsWithQueens) \
            + size - len(northEastDiagonalsWithQueens) \
            + size - len(southEastDiagonalsWithQueens)
    return total

下面就是执行函数了：

def get_best():
    random.seed()
    startTime = datetime.datetime.now()
    x = [random.randint(0,7) for i in range(size*2)]
    bestParent = Chromosome(x,get_fitness(x,size))
    if bestParent.Fitness <= 0:
        return bestParent
    num = 0
    while True:
        num +=1
        child = mutate(bestParent)
        if bestParent.Fitness < child.Fitness:
            pass
        else:
            display(child,startTime,size)
            bestParent = child
            if child.Fitness <=0:
                return (child,num)

一次执行的结果如下：

 .   .   .   .   .   .   .   .
 .   .   .   .   .   .   .   .
 .   .   .   Q   .   .   .   .
 Q   .   .   Q   .   .   Q   .
 Q   .   .   .   .   .   .   Q
 Q   .   .   .   .   .   .   .
 .   .   .   .   .   .   .   .
 .   .   .   .   .   .   .   .
3 4 0 4 3 5 0 3 6 4 7 3 0 2 7 3	- 12	0:00:00.001025

……（中间输出略）

 .   Q   .   .   .   .   .   .
 .   .   .   .   .   Q   .   .
 Q   .   .   .   .   .   .   .
 .   .   .   .   .   .   Q   .
 .   .   .   Q   .   .   .   .
 .   .   .   .   .   .   .   Q
 .   .   Q   .   .   .   .   .
 .   .   .   .   Q   .   .   .
1 7 0 5 5 6 3 3 6 4 4 0 7 2 2 1	- 0	0:00:00.099732

可以看见，从初始化的时候，一共有12个位置发生重叠，到最后，当重叠收敛到0的时候，结束迭代，该次分析，用了0.09秒，一共进行了816次进化。

下面我们把这个过程执行100次，看看结果：

最多一次，一共用了6200多次进化才得到正确解，而最好一次仅用了106次就完成了，所以说，遗传算法这种随机优化的算法，完全就是拼人品的干活，就像0杀吃鸡这种事情：

最后大家有兴趣的话，可以稍微加几句代码，把维基百科上面所说的92种答案全部解出来，看看需要多少时间。

遗传算法就是暴力破解算法的一种……完全靠着强大的算力和足够的等待时间，外加一点点人品……但是也正如堂堂正正之师，从来不玩虚的，说碾死你就直接碾死你。
——虾神语录

题外话，8 x 8的棋盘上，最多可以放入8个皇后，那么NxN的棋盘上，放置N个皇后，又如何放置呢？

我们仅需要修改一下size，就可以了，比如我做一个20X20的棋盘，放置20个皇后：

 .   .   .   .   .   .   .   .   .   .   .   .   .   .   Q   .   .   .   .   .
 .   .   .   .   .   Q   .   .   .   .   .   .   .   .   .   .   .   .   .   .
 .   .   .   .   .   .   .   .   Q   .   .   .   .   .   .   .   .   .   .   .
 .   Q   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .
 .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   Q   .   .   .
 .   .   .   .   .   .   .   .   .   .   .   .   .   Q   .   .   .   .   .   .
 .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   Q   .   .
 .   .   Q   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .
 .   .   .   .   .   .   .   .   .   .   .   Q   .   .   .   .   .   .   .   .
 .   .   .   .   .   .   Q   .   .   .   .   .   .   .   .   .   .   .   .   .
 .   .   .   Q   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .
 .   .   .   .   .   .   .   .   .   .   Q   .   .   .   .   .   .   .   .   .
 .   .   .   .   Q   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .
 .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   Q   .
 .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   Q   .   .   .   .
 .   .   .   .   .   .   .   .   .   Q   .   .   .   .   .   .   .   .   .   .
 .   .   .   .   .   .   .   .   .   .   .   .   Q   .   .   .   .   .   .   .
 Q   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .
 .   .   .   .   .   .   .   Q   .   .   .   .   .   .   .   .   .   .   .   .
 .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   Q
5 18 8 17 18 6 12 3 10 8 7 1 13 14 19 0 15 5 3 9 2 12 16 15 0 2 14 19 9 4 1 16 6 10 4 7 11 11 17 13	- 0	0:00:01.335459