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

南京理工大学人工智能大论文题目：遗传算法实现八皇后问题姓名：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摘要众所周知的八皇后问题是一个非常古老的问题，具体描述如下：在8*8的国际象棋棋盘上放置了八个皇后，要求没有一个皇后能吃掉另一个皇后，即任意两个皇后都不处于棋盘的同一行、同一列或同一对角线上。本实验要求设计并实现解决八皇后问题的遗传算法。能够给定任意一个初始状态，使用遗传算法搜索最优解，程序能显示优化的计算过程。独立运行20次以上，统计遗传算法的寻优指标（包括是否找到最优解、平均迭代次数等）。本次设计旨在学习各种算法，训练对基础知识和基本方法的综合运用及变通能力，增强对算法的理解能力，提高软件设计能力，在实践中培养独立分析问题和解决问题的作风和能力。通过本实验的设计与编程实现让学生掌握基于状态空间知识表示的局部搜索策略，对遗传算法中的编码方法以及选择、复制、交叉、变异等基本算子有深入的理解，熟练运用C++，编写一个遗传算法解决八皇后问题的应用程序。关键词：八皇后；遗传算法；C++一、实验背景1.1N皇后问题描述N皇后问题描述如下：在nn´格棋盘上放置彼此不受攻击的N个皇后。按国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。N皇后问题等价于在以下三个约束条件：任何2个皇后不放在同一行；任何2个皇后不放在同一列；任何2个皇后不放在同斜线。我们把nn´的棋盘看作二维方阵，其行号从上到下列号从左到右依次编号为0，1，…，7。设任意两个皇后，皇后1和皇后2的坐标分别是（i，j）和（k，l），则如果这两个皇后在从棋盘左上角到右下角的主对角线及其平行线（斜率为-1的线）上，有ijkl-=-；如果这两个皇后在斜率为＋1的每一斜线上，有++ijkl=；以上两个方程分别等价于ikjl-=-和iklj-=-因此任两皇后的在同一斜线上的充要条件是||||ikjl-=-。满足两个皇后不在同一斜线上的条件表示为：||||ikjl-?两皇后不在同一行用式表示为：ik¹两皇后不在同一列用式表示为：jl¹1.2遗传算法遗传算法（GeneticAlgorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（geneticoperators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。二、实验目的N皇后问题是经典的益智游戏，通过本实验的设计与编程实现让学生掌握基于状态空间知识表示的局部搜索策略，对遗传算法中的编码方法以及选择、复制、交叉、变异等基本算子有深入的理解。本次设计旨在学习各种算法，训练对基础知识和基本方法的综合运用及变通能力，增强对算法的理解能力，提高软件设计能力，在实践中培养独立分析问题和解决问题的作风和能力。熟练运用C++语言，独立编程，实现一个遗传算法解决八皇后问题的应用程序。三、实验内容本实验要求设计并实现解决八皇后问题的遗传算法。能够给定任意一个初始状态，使用遗传算法搜索最优解，程序能显示优化的计算过程。独立运行20次以上，统计遗传算法的寻优指标（包括是否找到最优解、平均迭代次数等）。因为我的学号末尾为0，按照老师要求，则应该实现8n=，即八皇后问题。四、实验步骤现在我们把任意n个皇后的任意一种放置办法当作一个个体（染色体），把其中的任意一个皇后当作一个基因，用遗传算法来解决该问题。4.1编码方案对于此问题有三种编码方案：排列编码、二进制编码、矩阵编码，在这里，采用第一重编码方案，即排列编码，具体描述如下：用一维n元数组[0,1...,1]xn-来表示一个个体，其中[]{0,1...,1}xin?，[]xi表示皇后i放在棋盘的第i行第[]xi列，即第i行第[]xi列放置一个皇后。例如，[0]0x=表示棋盘的第0行第0列放一个皇后。数组第i个元素表示第i行的放置情况，可以看作一个基因。这种编码可以自然的解决了某一行只能放一个皇后的约束，如果数组的每一个元素[]xi都不重复，可以看成0—n-1的一种排列，就自然保证每一列只能放一个皇后。因此在交叉变异和产生个体时必须注意[]xi的唯一性。4.2初始化种群初始化种群的主要工作为：确定种群的大小及产生初始种群.种群的大小能够对遗传算法的收敛性产生很大的影响，种群较小算法收敛速度较快