人工智能论文-遗传算法实现八皇后问题

《人工智能论文-遗传算法实现八皇后问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、南京理工大学人工智能大论文题目：遗传算法实现八皇后问题姓名：xxxx学号：xxxxxxxxxxxxxx专业：xxxxxxxxxx院系：xxxxxxxxxxxxxxxx老师：xxxxxx日期：2015年12月20日目录摘要3一、实验背景41.1N皇后问题描述41.2遗传算法4二、实验目的5三、实验内容5四、实验步骤54.1编码方案54.2初始化种群64.3适应度的计算74.4遗传算子84.4.1选择算子84.4.2交叉方法84.4.3变异方法84.5局部搜索104.6终止策略104.7实现描述10五、实验结果和分析11六、总结与思考12摘要众所周知的八皇后问题是

2、一个非常古老的问题，具体描述如下：在8*8的国际象棋棋盘上放置了八个皇后，要求没有一个皇后能吃掉另一个皇后，即任意两个皇后都不处于棋盘的同一行、同一列或同一对角线上。本实验要求设计并实现解决八皇后问题的遗传算法。能够给定任意一个初始状态，使用遗传算法搜索最优解，程序能显示优化的计算过程。独立运行20次以上，统计遗传算法的寻优指标（包括是否找到最优解、平均迭代次数等）。本次设计旨在学习各种算法，训练对基础知识和基本方法的综合运用及变通能力，增强对算法的理解能力，提高软件设计能力，在实践中培养独立分析问题和解决问题的作风和能力。通过本实验的设计与编程实现让学生掌握

3、基于状态空间知识表示的局部搜索策略，对遗传算法中的编码方法以及选择、复制、交叉、变异等基本算子有深入的理解，熟练运用C++，编写一个遗传算法解决八皇后问题的应用程序。关键词：八皇后；遗传算法；C++一、实验背景1.1N皇后问题描述N皇后问题描述如下：在格棋盘上放置彼此不受攻击的N个皇后。按国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。N皇后问题等价于在以下三个约束条件：任何2个皇后不放在同一行；任何2个皇后不放在同一列；任何2个皇后不放在同斜线。我们把的棋盘看作二维方阵，其行号从上到下列号从左到右依次编号为0，1，…，7。设任意两个皇后

4、，皇后1和皇后2的坐标分别是（i，j）和（k，l），则如果这两个皇后在从棋盘左上角到右下角的主对角线及其平行线（斜率为-1的线）上，有；如果这两个皇后在斜率为＋1的每一斜线上，有；以上两个方程分别等价于和因此任两皇后的在同一斜线上的充要条件是。满足两个皇后不在同一斜线上的条件表示为：两皇后不在同一行用式表示为：两皇后不在同一列用式表示为：1.2遗传算法遗传算法（GeneticAlgorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法是从代表问题可能潜在的解集的一个种群（popu

5、lation）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，

6、在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（geneticoperators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。二、实验目的N皇后问题是经典的益智游戏，通过本实验的设计与编程实现让学生掌握基于状态空间知识表示的局部搜索策略，对遗传算法中的编码方法以及选择、复制、交叉、变异等基本算子有深入的理解。本

7、次设计旨在学习各种算法，训练对基础知识和基本方法的综合运用及变通能力，增强对算法的理解能力，提高软件设计能力，在实践中培养独立分析问题和解决问题的作风和能力。熟练运用C++语言，独立编程，实现一个遗传算法解决八皇后问题的应用程序。三、实验内容本实验要求设计并实现解决八皇后问题的遗传算法。能够给定任意一个初始状态，使用遗传算法搜索最优解，程序能显示优化的计算过程。独立运行20次以上，统计遗传算法的寻优指标（包括是否找到最优解、平均迭代次数等）。因为我的学号末尾为0，按照老师要求，则应该实现，即八皇后问题。四、实验步骤现在我们把任意n个皇后的任意一种放置办法当作一

8、个个体（染色体），把其中的任意一个皇后