遗传算法（GA）作为一种启发式搜索方法，能够通过模拟自然选择过程找到高效解。本文介绍如何使用DEAP库实现遗传算法解决N皇后问题，采用适应度函数评估个体的解决方案，通过选择、交叉和突变操作逐代优化，直到找到可行解。实验表明，遗传算法能够在较少代数内找到可行解，并适应较大规模的N皇后问题。

遗传算法(enetic Algorithms，GA)已成功解决了许多复杂的设计和布局问题，部分原因是它采用了受控随机元素的搜索。这通常使得使用 GA 设计的系统能够超越我们的理解进行创新。在系列前文中，我们了解了N皇后问题的回溯法解决：N皇后问题（1）——N皇后问题概述和回溯法的两种实现与优化算法：N皇后问题（2）——回溯法的4种优化方法：对称优化、标记优化、可用优化和位运算优化。但不论如何优化，回溯法本质仍属于穷举搜索，虽经多重剪枝，但在规模进一步扩展时，解空间依然呈指数级爆炸。所以在本篇文章中，我们学习N皇后问题的遗传算法解决，探索启发式搜索在组合优化问题中的潜力与效果。

1 N 皇后问题

N皇后问题：使用大小为N的典型棋盘，经典的国际象棋棋盘大小为8(即 8x8)。我们的目标是在棋盘上放置 N 个皇后棋子，使得没有一个棋子可以在不移动的情况下俘获另一个棋子。

2 解的表示

在解决 N 皇后问题时，利用以下前提条件:每行恰好容纳一个皇后，同时没有两个皇后共享同一列。这意味着可以将候选解表示为有序的整数列表或索引列表，每个索引表示皇后之一占据当前行的列数。例如，在 4x4 棋盘上的四皇后问题中，具有以下索引列表：

(3, 2, 0, 1)

表示(索引从 0 开始计数):

（1）在第一行中，皇后放置在第四列中

（2）在第二行中，皇后放置在第三列中

（3）在第三行中，皇后放置在第一列中

（4）在第四行中，皇后放置在第二列中

3 遗传算法解决 N 皇后问题

（1）首先，导入所需库:

import random

import numpy as np



from deap import algorithms

from deap import base

from deap import creator

from deap import tools



import matplotlib.pyplot as plt

from matplotlib.pyplot import figure

（2）查看国际象棋棋盘上的皇后的初始位置。由于皇后棋子可以沿着任何方向和距离移动，因此这个游戏被限制在皇后的最大数量等于棋盘大小的情况下。在本节中，我们使用 8个棋子，接下来，绘制皇后的初始位置:

board_size = number_of_queens = 8



chessboard = np.zeros((board_size,board_size))

chessboard[1::2,0::2] = 1

chessboard[0::2,1::2] = 1



figure(figsize=(6, 6), dpi=80)

plt.imshow(chessboard, cmap='binary')



for _ in range(number_of_queens):

    i, j = np.random.randint(0, board_size, 2)

    plt.text(i, j, '♕', fontsize=30, ha='center', va='center', color='black' if (i - j) % 2 == 0 else 'white')

plt.show()

下图显示了渲染后的棋盘和皇后棋子的移动方式。可以看到，选定的棋子可以立即俘获其他几个棋子，我们的目标是将所有皇后放置在没有一个棋子可以俘获另一个棋子的位置。

（3）皇后游戏的适应度评估函数 eva1Noueens 通过采用一种简便方法来评估个体的适应度，而不是迭代运行每一种放置方式。该函数假设只能在一行或一列上放置一个皇后。因此，我们只需要评估皇后是否位于同一对角线，简化了适应度函数代码:

creator.create("FitnessMax", base.Fitness, weights=(-1.0,))

creator.create("Individual", list, fitness=creator.FitnessMax)



def evalNQueens(individual):

    size = len(individual)

    #Count the number of conflicts with other queens.

    #The conflicts can only be diagonal, count on each diagonal line

    left_diagonal = [ 0 ] * (2*size-1)

    right_diagonal = [ 0 ] * (2*size-1)

    

    #Sum the number of queens on each diagonal:

    for i in range(size):

        left_diagonal [ i+individual ] += 1

        right_diagonal [ size-1-i+individual ] += 1

    

    #Count the number of non-conflicts on each diagonal

    sum_ = 0

    for i in range(2*size-1):

        if left_diagonal > 1:

            sum_ += left_diagonal - 1

        if right_diagonal > 1:

            sum_ += right_diagonal - 1    

    return sum_,

（4）在适应度评估函数之后，编写 easimple 函数，它是标准的 DEAp 中 algorithms.easimple 函数的副本，该函数与 OneMax 一节中使用的函数几平完全相同，可以自定义输出表现最佳的个体，并测试是否可以提前停止。在以下代码中，比较了个体适应度与最大适应度,如果达到了最大适应度，进化过程将会提前停止:

toolbox = base.Toolbox()

toolbox.register("permutation", random.sample, range(number_of_queens), number_of_queens)

toolbox.register("individual", tools.initIterate, creator.Individual, toolbox.permutation)

toolbox.register("population", tools.initRepeat, list, toolbox.individual)



toolbox.register("evaluate", evalNQueens)

toolbox.register("mate", tools.cxPartialyMatched)

toolbox.register("mutate", tools.mutShuffleIndexes, indpb=2.0/number_of_queens)

toolbox.register("select", tools.selTournament, tournsize=3)



def plot_board(individual):  

    plt.imshow(chessboard, cmap='binary')

    for i in range(number_of_queens):               

        plt.text(i, individual, '♕', fontsize=20, ha='center', va='center', color='black' if (i - individual) % 2 == 0 else 'white')

plt.show()



def eaSimple(population, toolbox, cxpb, mutpb, ngen, max, stats=None, halloffame=None, ):  

    logbook = tools.Logbook()

    logbook.header = [ 'gen', 'nevals' ] + (stats.fields if stats else [] )



    # Evaluate the individuals with an invalid fitness

    invalid_ind = [ ind for ind in population if not ind.fitness.valid ] 

    fitnesses = toolbox.map(toolbox.evaluate, invalid_ind)

    for ind, fit in zip(invalid_ind, fitnesses):

        ind.fitness.values = fit



    if halloffame is not None:

        halloffame.update(population)



    record = stats.compile(population) if stats else {}

    logbook.record(gen=0, nevals=len(invalid_ind), **record)    

    print(logbook.stream)

    done = False



    # Begin the generational process

    for gen in range(1, ngen + 1):

        if done: return

        # Select the next generation individuals

        offspring = toolbox.select(population, len(population))



        offspring = [toolbox.clone(ind) for ind in offspring] 



        # Apply crossover and mutation on the offspring

        for i in range(1, len(offspring), 2):

            if random.random() < cxpb:

                offspring [ i - 1 ] , offspring = toolbox.mate(offspring [ i - 1 ] ,

                                                              offspring)

                del offspring [ i - 1 ] .fitness.values, offspring.fitness.values



        for i in range(len(offspring)):

            if random.random() < mutpb:

                offspring, = toolbox.mutate(offspring)

                del offspring.fitness.values



        # Evaluate the individuals with an invalid fitness

        invalid_ind = [ ind for ind in offspring if not ind.fitness.valid ] 

        fitnesses = toolbox.map(toolbox.evaluate, invalid_ind)

        

        for ind, fit in zip(invalid_ind, fitnesses):

            ind.fitness.values = fit            

            if fit [ 0 ] >= max:

              print("Solved")

              done = True



        # Update the hall of fame with the generated individuals

        if halloffame is not None:

            halloffame.update(offspring)            

            plot_board(halloffame [ 0 ] )            



        # Replace the current population by the offspring

        population [ : ] = offspring



        # Append the current generation statistics to the logbook

        record = stats.compile(population) if stats else {}

        logbook.record(gen=gen, nevals=len(invalid_ind), **record)

        print(logbook.stream)

 （5）最后，执行种群的演化。首先创建种群和一个用于存储最佳个体的 Ha110fFame 容器。然后，注册各种统计数据，最后调用 easimple函数演化种群。在以下代码中，将 max= number_of_queens 作为输入来控制个体达到最大适应度时提前停止种群的进化：

pop = toolbox.population(n=100)

hof = tools.HallOfFame(1)

stats = tools.Statistics(lambda ind: ind.fitness.values)

stats.register("Avg", np.mean)

stats.register("Std", np.std)

stats.register("Min", np.min)

stats.register("Max", np.max)



eaSimple(pop, toolbox, cxpb=0.5, mutpb=0.2, ngen=100, max = number_of_queens,

         stats=stats ,halloffame=hof)

 最后，查看进化过程的输出，并查看算法演化解决方案的效果如何。从输出中可以看出，演化过程能够提前停止(在第 5代生成一个可行的解决方案)。重新查看解决方案，确认每个皇后无法互相攻击。可以增加棋盘大小和皇后数量(如增加到 16 或更大的值)，这可能需要同时增加种群大小和演化代数的数量。

 

可以通过完成以下问题进一步理解使用 DEAP 库实现遗传算法的流程：

 · 将要演化的种群大小更改为其他值，然后重新运行，观察较大的种群对演化的影响。

 · 更改交叉和突变率，然后重新运行，观察能否在更少的代数中解决问题。

 · 增加或减少锦标赛的大小，然后重新运行，观察锦标赛大小对演化的影响。

4 总结与探索

遗传算法提供了一种高效的方式来解决N皇后问题，尤其是在问题规模增大的情况下。通过模拟自然选择机制，遗传算法能够探索广泛的解空间，并通过适应度评估快速找到合适的解。相比传统的回溯法，遗传算法的优势在于能够处理复杂的组合优化问题，且具有较强的扩展性。在实际应用中，通过调整种群大小、交叉和突变率等参数，能够进一步提高解的质量和搜索效率。遗传算法展示了在组合优化领域中的巨大潜力，尤其适用于大规模问题的求解。

本系列到此暂时完结了，不过编者也很好奇，除了遗传算法，还有没有其他更好的方法可以解决N皇后问题？比如模拟退火、蚁群算法之类的，效果如何？另外，在解决大规模问题时，如何调整参数才能让算法更高效呢？欢迎大家分享。

 

---

本文改编转载自CSDN平台博主：盼小辉、

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

原文链接：使用遗传算法解决N皇后问题_algorithms.easimple-CSDN博客

遗传算法（GA）作为一种启发式搜索方法，能够通过模拟自然选择过程找到高效解。本文介绍如何使用DEAP库实现遗传算法解决N皇后问题，采用适应度函数评估个体的解决方案，通过选择、交叉和突变操作逐代优化，直到找到可行解。实验表明，遗传算法能够在较少代数内找到可行解，并适应较大规模的N皇后问题。

遗传算法(enetic Algorithms，GA)已成功解决了许多复杂的设计和布局问题，部分原因是它采用了受控随机元素的搜索。这通常使得使用 GA 设计的系统能够超越我们的理解进行创新。在系列前文中，我们了解了N皇后问题的回溯法解决：N皇后问题（1）——N皇后问题概述和回溯法的两种实现与优化算法：N皇后问题（2）——回溯法的4种优化方法：对称优化、标记优化、可用优化和位运算优化。但不论如何优化，回溯法本质仍属于穷举搜索，虽经多重剪枝，但在规模进一步扩展时，解空间依然呈指数级爆炸。所以在本篇文章中，我们学习N皇后问题的遗传算法解决，探索启发式搜索在组合优化问题中的潜力与效果。

1 N 皇后问题

N皇后问题：使用大小为N的典型棋盘，经典的国际象棋棋盘大小为8(即 8x8)。我们的目标是在棋盘上放置 N 个皇后棋子，使得没有一个棋子可以在不移动的情况下俘获另一个棋子。

2 解的表示

在解决 N 皇后问题时，利用以下前提条件:每行恰好容纳一个皇后，同时没有两个皇后共享同一列。这意味着可以将候选解表示为有序的整数列表或索引列表，每个索引表示皇后之一占据当前行的列数。例如，在 4x4 棋盘上的四皇后问题中，具有以下索引列表：

(3, 2, 0, 1)

表示(索引从 0 开始计数):

（1）在第一行中，皇后放置在第四列中

（2）在第二行中，皇后放置在第三列中

（3）在第三行中，皇后放置在第一列中

（4）在第四行中，皇后放置在第二列中

3 遗传算法解决 N 皇后问题

（1）首先，导入所需库:

import random

import numpy as np



from deap import algorithms

from deap import base

from deap import creator

from deap import tools



import matplotlib.pyplot as plt

from matplotlib.pyplot import figure

（2）查看国际象棋棋盘上的皇后的初始位置。由于皇后棋子可以沿着任何方向和距离移动，因此这个游戏被限制在皇后的最大数量等于棋盘大小的情况下。在本节中，我们使用 8个棋子，接下来，绘制皇后的初始位置:

board_size = number_of_queens = 8



chessboard = np.zeros((board_size,board_size))

chessboard[1::2,0::2] = 1

chessboard[0::2,1::2] = 1



figure(figsize=(6, 6), dpi=80)

plt.imshow(chessboard, cmap='binary')



for _ in range(number_of_queens):

    i, j = np.random.randint(0, board_size, 2)

    plt.text(i, j, '♕', fontsize=30, ha='center', va='center', color='black' if (i - j) % 2 == 0 else 'white')

plt.show()

下图显示了渲染后的棋盘和皇后棋子的移动方式。可以看到，选定的棋子可以立即俘获其他几个棋子，我们的目标是将所有皇后放置在没有一个棋子可以俘获另一个棋子的位置。

（3）皇后游戏的适应度评估函数 eva1Noueens 通过采用一种简便方法来评估个体的适应度，而不是迭代运行每一种放置方式。该函数假设只能在一行或一列上放置一个皇后。因此，我们只需要评估皇后是否位于同一对角线，简化了适应度函数代码:

creator.create("FitnessMax", base.Fitness, weights=(-1.0,))

creator.create("Individual", list, fitness=creator.FitnessMax)



def evalNQueens(individual):

    size = len(individual)

    #Count the number of conflicts with other queens.

    #The conflicts can only be diagonal, count on each diagonal line

    left_diagonal = [ 0 ] * (2*size-1)

    right_diagonal = [ 0 ] * (2*size-1)

    

    #Sum the number of queens on each diagonal:

    for i in range(size):

        left_diagonal [ i+individual ] += 1

        right_diagonal [ size-1-i+individual ] += 1

    

    #Count the number of non-conflicts on each diagonal

    sum_ = 0

    for i in range(2*size-1):

        if left_diagonal > 1:

            sum_ += left_diagonal - 1

        if right_diagonal > 1:

            sum_ += right_diagonal - 1    

    return sum_,

（4）在适应度评估函数之后，编写 easimple 函数，它是标准的 DEAp 中 algorithms.easimple 函数的副本，该函数与 OneMax 一节中使用的函数几平完全相同，可以自定义输出表现最佳的个体，并测试是否可以提前停止。在以下代码中，比较了个体适应度与最大适应度,如果达到了最大适应度，进化过程将会提前停止:

toolbox = base.Toolbox()

toolbox.register("permutation", random.sample, range(number_of_queens), number_of_queens)

toolbox.register("individual", tools.initIterate, creator.Individual, toolbox.permutation)

toolbox.register("population", tools.initRepeat, list, toolbox.individual)



toolbox.register("evaluate", evalNQueens)

toolbox.register("mate", tools.cxPartialyMatched)

toolbox.register("mutate", tools.mutShuffleIndexes, indpb=2.0/number_of_queens)

toolbox.register("select", tools.selTournament, tournsize=3)



def plot_board(individual):  

    plt.imshow(chessboard, cmap='binary')

    for i in range(number_of_queens):               

        plt.text(i, individual, '♕', fontsize=20, ha='center', va='center', color='black' if (i - individual) % 2 == 0 else 'white')

plt.show()



def eaSimple(population, toolbox, cxpb, mutpb, ngen, max, stats=None, halloffame=None, ):  

    logbook = tools.Logbook()

    logbook.header = [ 'gen', 'nevals' ] + (stats.fields if stats else [] )



    # Evaluate the individuals with an invalid fitness

    invalid_ind = [ ind for ind in population if not ind.fitness.valid ] 

    fitnesses = toolbox.map(toolbox.evaluate, invalid_ind)

    for ind, fit in zip(invalid_ind, fitnesses):

        ind.fitness.values = fit



    if halloffame is not None:

        halloffame.update(population)



    record = stats.compile(population) if stats else {}

    logbook.record(gen=0, nevals=len(invalid_ind), **record)    

    print(logbook.stream)

    done = False



    # Begin the generational process

    for gen in range(1, ngen + 1):

        if done: return

        # Select the next generation individuals

        offspring = toolbox.select(population, len(population))



        offspring = [toolbox.clone(ind) for ind in offspring] 



        # Apply crossover and mutation on the offspring

        for i in range(1, len(offspring), 2):

            if random.random() < cxpb:

                offspring [ i - 1 ] , offspring = toolbox.mate(offspring [ i - 1 ] ,

                                                              offspring)

                del offspring [ i - 1 ] .fitness.values, offspring.fitness.values



        for i in range(len(offspring)):

            if random.random() < mutpb:

                offspring, = toolbox.mutate(offspring)

                del offspring.fitness.values



        # Evaluate the individuals with an invalid fitness

        invalid_ind = [ ind for ind in offspring if not ind.fitness.valid ] 

        fitnesses = toolbox.map(toolbox.evaluate, invalid_ind)

        

        for ind, fit in zip(invalid_ind, fitnesses):

            ind.fitness.values = fit            

            if fit [ 0 ] >= max:

              print("Solved")

              done = True



        # Update the hall of fame with the generated individuals

        if halloffame is not None:

            halloffame.update(offspring)            

            plot_board(halloffame [ 0 ] )            



        # Replace the current population by the offspring

        population [ : ] = offspring



        # Append the current generation statistics to the logbook

        record = stats.compile(population) if stats else {}

        logbook.record(gen=gen, nevals=len(invalid_ind), **record)

        print(logbook.stream)

 （5）最后，执行种群的演化。首先创建种群和一个用于存储最佳个体的 Ha110fFame 容器。然后，注册各种统计数据，最后调用 easimple函数演化种群。在以下代码中，将 max= number_of_queens 作为输入来控制个体达到最大适应度时提前停止种群的进化：

pop = toolbox.population(n=100)

hof = tools.HallOfFame(1)

stats = tools.Statistics(lambda ind: ind.fitness.values)

stats.register("Avg", np.mean)

stats.register("Std", np.std)

stats.register("Min", np.min)

stats.register("Max", np.max)



eaSimple(pop, toolbox, cxpb=0.5, mutpb=0.2, ngen=100, max = number_of_queens,

         stats=stats ,halloffame=hof)

 最后，查看进化过程的输出，并查看算法演化解决方案的效果如何。从输出中可以看出，演化过程能够提前停止(在第 5代生成一个可行的解决方案)。重新查看解决方案，确认每个皇后无法互相攻击。可以增加棋盘大小和皇后数量(如增加到 16 或更大的值)，这可能需要同时增加种群大小和演化代数的数量。

 

可以通过完成以下问题进一步理解使用 DEAP 库实现遗传算法的流程：

 · 将要演化的种群大小更改为其他值，然后重新运行，观察较大的种群对演化的影响。

 · 更改交叉和突变率，然后重新运行，观察能否在更少的代数中解决问题。

 · 增加或减少锦标赛的大小，然后重新运行，观察锦标赛大小对演化的影响。

4 总结与探索

遗传算法提供了一种高效的方式来解决N皇后问题，尤其是在问题规模增大的情况下。通过模拟自然选择机制，遗传算法能够探索广泛的解空间，并通过适应度评估快速找到合适的解。相比传统的回溯法，遗传算法的优势在于能够处理复杂的组合优化问题，且具有较强的扩展性。在实际应用中，通过调整种群大小、交叉和突变率等参数，能够进一步提高解的质量和搜索效率。遗传算法展示了在组合优化领域中的巨大潜力，尤其适用于大规模问题的求解。

本系列到此暂时完结了，不过编者也很好奇，除了遗传算法，还有没有其他更好的方法可以解决N皇后问题？比如模拟退火、蚁群算法之类的，效果如何？另外，在解决大规模问题时，如何调整参数才能让算法更高效呢？欢迎大家分享。

 

---

本文改编转载自CSDN平台博主：盼小辉、

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

原文链接：使用遗传算法解决N皇后问题_algorithms.easimple-CSDN博客