遗传算法与深度学习实战(7)——使用遗传算法解决N皇后问题

2024-08-21 09:12

本文主要是介绍遗传算法与深度学习实战(7)——使用遗传算法解决N皇后问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

遗传算法与深度学习实战(7)——使用遗传算法解决N皇后问题

    • 0. 前言
    • 1. N 皇后问题
    • 2. 解的表示
    • 3. 遗传算法解决 N 皇后问题
    • 小结
    • 系列链接

0. 前言

进化算法 (Evolutionary Algorithm, EA) 和遗传算法 (Genetic Algorithms, GA) 已成功解决了许多复杂的设计和布局问题,部分原因是它们采用了受控随机元素的搜索。这通常使得使用 EAGA 设计的系统能够超越我们的理解进行创新。在本节中,我们将解决一个经典的设计和布局问题:N 皇后问题,这个问题使用大小为 N 的典型棋盘,经典的国际象棋棋盘大小为 8 (即 8×8 )。我们的目标是在棋盘上放置 N 个皇后棋子,使得没有一个棋子可以在不移动的情况下俘获另一个棋子。

1. N 皇后问题

在国际象棋中,皇后棋子是最强大的,可以沿着任何方向和距离移动。通常,每个玩家只有一个皇后棋子,但有一条特殊规则,允许玩家在将兵移动到对手的底线时加冕更多的皇后,皇后游戏的前提是玩家已经加冕了多个皇后(虽然这种情况在真实的比赛中可能永远不会发生,因为当玩家的国王棋子被俘获时,比赛就将结束)。
经典的 N 皇后问题最初被称为八皇后拼图,起源于国际象棋。任务是将八名皇后放置在棋盘上,而且他们中的任何两个都不互相构成威胁。换句话说,没有两个皇后可以在同一行、同一列或同一对角线。概括而言,N 皇后问题使用 N × N 的棋盘和 N (其中 N>3 )个皇后。对于原始的八皇后情形,有 92 个解,消除对称解,则有 12 个唯一解。
使用排列组合,将 8 个皇后放置在 8 × 8 棋盘上的所有可能方式有 4,426,165,368 种。但是,如果通过确保不会在同一行或同一列上放置两个皇后的方式创建候选解决方案,则可能的组合数量将减少到 8 ! = 40320 8!=40320 8!=40320 个。

2. 解的表示

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

(3, 2, 0, 1)

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

  1. 在第一行中,皇后放置在第四列中
  2. 在第二行中,皇后放置在第三列中
  3. 在第三行中,皇后放置在第一列中
  4. 在第四行中,皇后放置在第二列中

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

(1) 首先,导入所需库:

import random
import numpy as npfrom deap import algorithms
from deap import base
from deap import creator
from deap import toolsimport matplotlib.pyplot as plt
from matplotlib.pyplot import figure

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

board_size = number_of_queens = 8chessboard = np.zeros((board_size,board_size))
chessboard[1::2,0::2] = 1
chessboard[0::2,1::2] = 1figure(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) 皇后游戏的适应度评估函数 evalNQueens 通过采用一种简便方法来评估个体的适应度,而不是迭代运行每一种放置方式。该函数假设只能在一行或一列上放置一个皇后。因此,我们只需要评估皇后是否位于同一对角线,简化了适应度函数代码:

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 lineleft_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[i]] += 1right_diagonal[size-1-i+individual[i]] += 1#Count the number of non-conflicts on each diagonalsum_ = 0for i in range(2*size-1):if left_diagonal[i] > 1:sum_ += left_diagonal[i] - 1if right_diagonal[i] > 1:sum_ += right_diagonal[i] - 1    return sum_,

(4) 在适应度评估函数之后,编写 eaSimple 函数,它是标准的 DEAPalgorithms.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[i], '♕', fontsize=20, ha='center', va='center', color='black' if (i - individual[i]) % 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 fitnessinvalid_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 = fitif 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 processfor gen in range(1, ngen + 1):if done: return# Select the next generation individualsoffspring = toolbox.select(population, len(population))offspring = [toolbox.clone(ind) for ind in offspring]# Apply crossover and mutation on the offspringfor i in range(1, len(offspring), 2):if random.random() < cxpb:offspring[i - 1], offspring[i] = toolbox.mate(offspring[i - 1],offspring[i])del offspring[i - 1].fitness.values, offspring[i].fitness.valuesfor i in range(len(offspring)):if random.random() < mutpb:offspring[i], = toolbox.mutate(offspring[i])del offspring[i].fitness.values# Evaluate the individuals with an invalid fitnessinvalid_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 individualsif halloffame is not None:halloffame.update(offspring)            plot_board(halloffame[0])            # Replace the current population by the offspringpopulation[:] = offspring# Append the current generation statistics to the logbookrecord = stats.compile(population) if stats else {}logbook.record(gen=gen, nevals=len(invalid_ind), **record)print(logbook.stream)

(5) 最后,执行种群的演化。首先创建种群和一个用于存储最佳个体的 HallOfFame 容器。然后,注册各种统计数据,最后调用 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 库实现遗传算法的流程:

  • 将要演化的种群大小更改为其他值,然后重新运行,观察较大的种群对演化的影响
  • 更改交叉和突变率,然后重新运行,观察能否在更少的代数中解决问题
  • 增加或减少锦标赛的大小,然后重新运行,观察锦标赛大小对演化的影响

小结

N 皇后问题是一个经典的组合问题,要求在一个( N x N )的棋盘上放置 N 个皇后,使得它们互相不能攻击到对方。遗传算法是解决 N 皇后问题的一种有效方法,本节中,我们使用 DEAP 库实现遗传算法解决了 N 皇后问题。

系列链接

遗传算法与深度学习实战(1)——进化深度学习
遗传算法与深度学习实战(2)——生命模拟及其应用
遗传算法与深度学习实战(3)——生命模拟与进化论
遗传算法与深度学习实战(4)——遗传算法详解与实现
遗传算法与深度学习实战(5)——遗传算法框架DEAP
遗传算法与深度学习实战(6)——DEAP框架初体验

这篇关于遗传算法与深度学习实战(7)——使用遗传算法解决N皇后问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1092732

相关文章

使用Python实现图像LBP特征提取的操作方法

《使用Python实现图像LBP特征提取的操作方法》LBP特征叫做局部二值模式,常用于纹理特征提取,并在纹理分类中具有较强的区分能力,本文给大家介绍了如何使用Python实现图像LBP特征提取的操作方... 目录一、LBP特征介绍二、LBP特征描述三、一些改进版本的LBP1.圆形LBP算子2.旋转不变的LB

Maven的使用和配置国内源的保姆级教程

《Maven的使用和配置国内源的保姆级教程》Maven是⼀个项目管理工具,基于POM(ProjectObjectModel,项目对象模型)的概念,Maven可以通过一小段描述信息来管理项目的构建,报告... 目录1. 什么是Maven?2.创建⼀个Maven项目3.Maven 核心功能4.使用Maven H

Python中__init__方法使用的深度解析

《Python中__init__方法使用的深度解析》在Python的面向对象编程(OOP)体系中,__init__方法如同建造房屋时的奠基仪式——它定义了对象诞生时的初始状态,下面我们就来深入了解下_... 目录一、__init__的基因图谱二、初始化过程的魔法时刻继承链中的初始化顺序self参数的奥秘默认

SpringBoot内嵌Tomcat临时目录问题及解决

《SpringBoot内嵌Tomcat临时目录问题及解决》:本文主要介绍SpringBoot内嵌Tomcat临时目录问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录SprinjavascriptgBoot内嵌Tomcat临时目录问题1.背景2.方案3.代码中配置t

SpringBoot使用GZIP压缩反回数据问题

《SpringBoot使用GZIP压缩反回数据问题》:本文主要介绍SpringBoot使用GZIP压缩反回数据问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot使用GZIP压缩反回数据1、初识gzip2、gzip是什么,可以干什么?3、Spr

Spring Boot 集成 Quartz并使用Cron 表达式实现定时任务

《SpringBoot集成Quartz并使用Cron表达式实现定时任务》本篇文章介绍了如何在SpringBoot中集成Quartz进行定时任务调度,并通过Cron表达式控制任务... 目录前言1. 添加 Quartz 依赖2. 创建 Quartz 任务3. 配置 Quartz 任务调度4. 启动 Sprin

Linux下如何使用C++获取硬件信息

《Linux下如何使用C++获取硬件信息》这篇文章主要为大家详细介绍了如何使用C++实现获取CPU,主板,磁盘,BIOS信息等硬件信息,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录方法获取CPU信息:读取"/proc/cpuinfo"文件获取磁盘信息:读取"/proc/diskstats"文

Java使用SLF4J记录不同级别日志的示例详解

《Java使用SLF4J记录不同级别日志的示例详解》SLF4J是一个简单的日志门面,它允许在运行时选择不同的日志实现,这篇文章主要为大家详细介绍了如何使用SLF4J记录不同级别日志,感兴趣的可以了解下... 目录一、SLF4J简介二、添加依赖三、配置Logback四、记录不同级别的日志五、总结一、SLF4J

使用Python实现一个优雅的异步定时器

《使用Python实现一个优雅的异步定时器》在Python中实现定时器功能是一个常见需求,尤其是在需要周期性执行任务的场景下,本文给大家介绍了基于asyncio和threading模块,可扩展的异步定... 目录需求背景代码1. 单例事件循环的实现2. 事件循环的运行与关闭3. 定时器核心逻辑4. 启动与停

如何使用Nginx配置将80端口重定向到443端口

《如何使用Nginx配置将80端口重定向到443端口》这篇文章主要为大家详细介绍了如何将Nginx配置为将HTTP(80端口)请求重定向到HTTPS(443端口),文中的示例代码讲解详细,有需要的小伙... 目录1. 创建或编辑Nginx配置文件2. 配置HTTP重定向到HTTPS3. 配置HTTPS服务器