开通VIP，畅享免费电子书等14项超值服
首页
好书
留言交流
下载APP
联系客服
2023.04.21北京
本节我们主要讲解如何使用遗传算法解决八皇后问题
八皇后是算法界一个非常常见的问题，也经常用于各种大厂的面试中，题目如下：
在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法：
比如，我们在第一个位置上，放好一个皇后，那么蓝色的位置就不能在放置了：
只能在空白的地方挑选一个位置来放，比如：
之后，蓝色区域继续扩大，第三个也只能继续去找白色区域摆放：
比如下面就是其中的一种经典解法：
根据维基百科的说法，这个谜题只有92个答案，而把那些相似的变种（比如镜像和旋转）删掉，就只有12个特定的解决方案。
根据排列组合的算法，理论上皇后摆放的位置，有64×63×62×62×61×60×59×58×57中可能……我就不去计算了，如果不进行收敛而采用遍历的话，那几乎是一个不可能完成的任务。
如果用遗传算法来解决，我们会发现，每一次选择，不仅仅是个别基因的问题，而是会带来相互之间的约束，特别是算法不知道基因彼此之间的关系，我们就必须设计好各种约束条件。
前面几节的内容，有一个特点，就是基因本身的选择就是解决方案本身，所以我们只需要把选择结果进行比较，或者就展现出来就可以了。
但是很多的分析没有这么简单，他们有各式各样的约束和表达，所以在比较高的层次上，把最初的基因编码称之为基因型，而把最终形式称之为表型。
基因型是对问题的各个部分进行编码的方式，以便可以通过遗传算法以及功能函数对其进行操作。比如在八皇后问题上，基因型的示例如下：
表型就是如何使用已编/解码的基因来解决问题。比如在上面的每个示例中，表型如下：
首先还是一样，定义我们的基因库，这里用8个整数：0-7来表达就行：
size=8geneSet=[iforiinrange(size)]然后定义一个棋盘类，用来模拟棋盘：这个类一共有三个方法，分别是
classBoard:def__init__(self,genes,size):board=[['.']*sizefor_inrange(size)]forindexinrange(0,len(genes),2):row=genes[index]column=genes[index+1]board[column][row]='Q'self._board=boarddefget(self,row,column):returnself._board[column][row]defprint(self):foriinreversed(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]运行结果如下:
defdisplay(candidate,startTime,size):timeDiff=datetime.datetime.now()-startTimeboard=Board(candidate.Genes,size)board.print()print("{0}\t-{1}\t{2}".format(''.join(map(str,candidate.Genes)),candidate.Fitness,str(timeDiff)))然后是老规矩的染色体类和进化变异函数：
从这里就可以看出遗传算法的鲁棒性来了，核心函数从来不用修改，在所有地方都适用
classChromosome:def__init__(self,genes,fitness):self.Genes=genesself.Fitness=fitnessdefmutate(parent):childGenes=parent.Genes[:]index=random.randrange(0,len(parent.Genes))newGene,alternate=random.sample(geneSet,2)childGenes[index]=alternateifnewGene==childGenes[index]elsenewGenefitness=get_fitness(childGenes,size)returnChromosome(childGenes,fitness)下面是最关键的健壮性验证方法，所有的遗传算法里面，这个方法都是最关键的，它用于评价你这次进化的效果好不好：
他的验证逻辑很简单：
可以看见，如果结果为0，则表示得到了正确的八皇后解。
defget_fitness(genes,size):board=Board(genes,size)rowsWithQueens=set()colsWithQueens=set()northEastDiagonalsWithQueens=set()southEastDiagonalsWithQueens=set()forrowinrange(size):forcolinrange(size):ifboard.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)returntotal下面就是执行函数了：
defget_best():random.seed()startTime=datetime.datetime.now()x=[random.randint(0,7)foriinrange(size*2)]bestParent=Chromosome(x,get_fitness(x,size))ifbestParent.Fitness<=0:returnbestParentnum=0whileTrue:num+=1child=mutate(bestParent)ifbestParent.Fitness 下面我们把这个过程执行100次，看看结果： 最多一次，一共用了6200多次进化才得到正确解，而最好一次仅用了106次就完成了，所以说，遗传算法这种随机优化的算法，完全就是拼人品的干活，就像0杀吃鸡这种事情： ——虾神语录 题外话，8x8的棋盘上，最多可以放入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...............................Q518817186123108711314190155392121615021419941166104711111713-00:00:01.335459总计发生了5204次进化，最终得到了这个20皇后的解，大家有兴趣的话，可以去尝试更多的方案。