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

南京理工大学人工智能大论文题目：遗传算法实现八皇后问题姓名：xxxx学号：xxxxxxxxxxxxxx专业：xxxxxxxxxx院系：xxxxxxxxxxxxxxxx老师：xxxxxx日期：2015年12月20日目录TOC\o"1-5"\h\z\o"CurrentDocument"摘要3一、实验背景4\o"CurrentDocument"1.1N皇后问题描述4\o"CurrentDocument"1.2遗传算法4\o"CurrentDocument"二、实验目的5\o"CurrentDocument"三、实验内容5\o"CurrentDocument"四、实验步骤5\o"CurrentDocument"4.1编码方案5\o"CurrentDocument"4.2初始化种群6\o"CurrentDocument"4.3适应度的计算7\o"CurrentDocument"4.4遗传算子84.4.1选择算子84.4.2交叉方法84.4.3变异方法8\o"CurrentDocument"4.5局部搜索10\o"CurrentDocument"4.6终止策略10\o"CurrentDocument"4.7实现描述10\o"CurrentDocument"五、实验结果和分析11\o"CurrentDocument"六、总结与思考12摘要众所周知的八皇后问题是一个非常古老的问题，具体描述如下：在8*8的国际象棋棋盘上放置了八个皇后，要求没有一个皇后能吃掉另一个皇后，即任意两个皇后都不处于棋盘的同一行、同一列或同一对角线上。本实验要求设计并实现解决八皇后问题的遗传算法。能够给定任意一个初始状态，使用遗传算法搜索最优解，程序能显示优化的计算过程。独立运行20次以上，统计遗传算法的寻优指标（包括是否找到最优解、平均迭代次数等）。本次设计旨在学习各种算法，训练对基础知识和基本方法的综合运用及变通能力，增强对算法的理解能力，提高软件设计能力，在实践中培养独立分析问题和解决问题的作风和能力。通过本实验的设计与编程实现让学生掌握基于状态空间知识表示的局部搜索策略，对遗传算法中的编码方法以及选择、复制、交叉、变异等基本算子有深入的理解，熟练运用C++，编写一个遗传算法解决八皇后问题的应用程序。关键词：八皇后；遗传算法；C++1.1N皇后问题描述N皇后问题描述如下：在nXn格棋盘上放置彼此不受攻击的N个皇后。按国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。N皇后问题等价于在以下三个约束条件：任何2个皇后不放在同一行；任何2个皇后不放在同一列；任何2个皇后不放在同斜线。我们把nXn的棋盘看作二维方阵，其行号从上到下列号从左到右依次编号为0，1，…，7。设任意两个皇后，皇后1和皇后2的坐标分别是（i，j）和（k，1），则如果这两个皇后在从棋盘左上角到右下角的主对角线及其平行线（斜率为-1的线）上，有i—j=k—l；如果这两个皇后在斜率为+1的每一斜线上，有i+j=k+1；以上两个方程分别等价于i—k=j—l和i—k=l—j因此任两皇后的在同一斜线上的充要条件是'「—k|=V_，|。满足两个皇后不在同一斜线上的条件表示为：li—kUj•—I'两皇后不在同一行用式表示为：Jk两皇后不在同一列用式表示为：j』1.2遗传算法遗传算法（GeneticAlgorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体（individual）组成。每个个体实际上是染色体（chromosome）带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（geneticoperators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。二、实验目的N皇后问题是经典的益智游戏，通过本实验的设计与编程实现让学生掌握基于状态空间知识表示的局部搜索策略，对遗传算法中的编码方法以及选择、复制、交叉、变异等基本算子有深入的理解。本次设计旨在学习各种算法，训练对基础知识和基本方法的综合运用及变通能力，增强对算法的理解能力，提高软件设计能力，在实践中培养独立分析问题和解决问题的作风和能力。熟练运用C++语言，独立编程，实现一个遗传算法解决八皇后问题的应用程序。三、实验内容本实验要求设计并实现解决八皇后问题的遗传算法。能够给定任意一个初始状态，使用遗传算法搜索最优解，程序能显示优化的计算过程。独立运行20次以上，统计遗传算法的寻优指标（包括是否找到最优解、平均迭代次数等）。因为我的学号末尾为0，按照老师要求，则应该实现n=8，即八皇后问题。四、实验步骤现在我们把任意n个皇后的任意一种放置办法当作一个个体（染色体），把其中的任意一个皇后当作一个基因，用遗传算法来解决该问题。4.1编码方案对于此问题有三种编码方案：排列编码、二进制编码、矩阵编码，在这里，采用第一重编码方案，即排列编码，具体描述如下：用一维n元数组M0,1...,n-1]来表示一个个体，其中x[i]e{0,1...,n-1},x[i]表示皇后i放在棋盘的第i行第x[i]列，即第i行第x[i]列放置一个皇后。例如，x[0]=0表示棋盘的第0行第0列放一个皇后。数组第i个元素表示第i行的放置情况，可以看作一个基因。这种编码可以自然的解决了某一行只能放一个皇后的约束，如果数组的每一个元素x[i]都不重复，可以看成0—n-1的一种排列，就自然保证每一列只能放一个皇后。因此在交叉变异和产生个体时必须注意x[i]的唯一性。4.2初始化种群初始化种群的主要工作为：确定种群的大小及产生初始种群.种群的大小能够对遗传算法的收敛性产生很大的影响，种群较小算法收敛速度较快，但它的搜索面不够广，容易导致局部收敛；而种群较大算法收敛全局最优的概率也大，但是算法的收敛速度较慢。因此根据N皇后问题的特点，本文将种群大小设为N(皇后数)。初始化种群的方法为：首先为每个体的染色体的基因位从1到N，然后随机交换两个基因位的值，对每个个体共交换N/2次，对种群中所有个体做上述操作。双亲遗传时候的初始化种群实现如下：voidCreateMultiStartPopulation(){intloop,i,j;inttmp[MAX_QUEENS];for(loop=0;loop<m_size;loop++){for(i=0;i<n;i++)tmp[i]=i;for(i=0;i<n;i++){j=rand()%(n-i);m_population[loop].queen[i]=tmp[j];tmp[j]=tmp[n-i-1];}UpdateFitnessScore(&m_population[loop]);4.3适应度的计算11‘和/攻击设七表示皇后i和皇后j之间的相互攻击，即：a广.讦和不攻击皇后i和j的攻击度:11Ix[i]-X[j]l=i-皇后i和j的攻击度:ij0other第i个皇后的攻击度a表示皇后i在除自身外其余n-1个皇后中与皇后i相冲突的i数目，即有几个皇后与皇后i相攻击。如果皇后i和所有皇后都冲突则攻击度为n-1，与所有的皇后都不冲突攻击度为0。因此，得到气=方:%+丈%。j=1j=i+1同理，皇后i的非攻击度表示和皇后i没有冲突的皇后数目，设々表示i的非攻击度，则b=n_1一气。我们根据非攻击度计算：用/表示基因i的适应度，即第i个皇后的非攻击度，则ifi=bi。如果某一个皇后i和所有其余的n-1个皇后都互不攻击，则L=n—L个体的适应度是指所有皇后的非攻击度之和，适应度函数可表示如下：f=^fi。i=1对于一个合法的放置方案每一个基因的适应度都是n-1，此时染色体的适应度是乃X(n—1)。//更新p的适应度voidUpdateFitnessScore(Population*p){inti,j;p->unitFitness=0;for(i=0;i<n;i++){p->eachFitness[i]=0;for(j=0;j<n;j++)p->eachFitness[i]+=Aggressive(p,i,j);p->unitFitness+=p->eachFitness[i];//个体的适应度为所有的基因的适应度的总和4.4遗传算子4.4.1选择算子目前常用的选择算子有二种：轮盘赌选择算子和二进制锦标赛选择算子。轮盘赌选择算子的缺点在于容易产生出超级个体，易导致算法局部收敛。但为了实现简单，我选择轮盘赌选择算子，即被选到的概率与适应度呈正比(越是优越的个体基因越容易被保留下来)，具体试下如下：intRouletteWheelSelection(){intselection=0;inti;doubleslice=(double)rand()/RAND_MAX;doubleaddFitness=0;for(i=0;i<m_size;i++){addFitness+=(double)m_population[i].unitFitness/m_totFitness;if(addFitness>slice){selection=i;break;}}returnselection;}4.4.2交叉方法交叉方法可用的交叉方法有以下几种。设p1，p2是要交叉的两个父染色体，c1，c2是子代，是交叉的结果，n是编码长度。单点交叉：先随机生成交叉位置m(0<m<n-1)，把p1[0:m]与p2[0:m]部分互换分别得到c1，c2。4.4.3变异方法采用随机变异方法。随机生成变异数目m，随机选择m个皇后把它去掉，然后再随机选择m个位置放上皇后。单亲遗传：通过随机交换适应度最低的基因与其他基因的位置，产生新的子代。具体性实现如下：//单亲遗传父代变异函数voidSimpleMutate(){inti,j,swap;intworst;Populationbaby;worst=0;for(i=0;i<n;i++)if(s_population.eachFitness[i]<s_population.eachFitness[worst])worst=i;do{j=rand()%n;}while(worst==j);baby=s_population;swap=baby.queen[worst];baby.queen[worst]=baby.queen[j];baby.queen[j]=swap;UpdateFitnessScore(&baby);//如果子代的适应度更高的话，则子代保存下来//当概率小于某临界值的时候子代不管是否更优都保留if(baby.unitFitness>s_population.unitFitnessII(double)rand()/RAND_MAX<Critical)s_population=baby;}双亲遗传中的变异算子，对种群中的最优两个个体保留，并局部变异看是否可以达到结果，具体代码如下：//单亲遗传父代变异函数voidMultiMutate(Population*p){inti,j,swap;intworst;Populationbaby;worst=0;for(i=0;i<n;i++)if(p->eachFitness[i]<p->eachFitness[worst])worst=i;baby=*p;for(i=0;i<n/4;i++){j=rand()%n;swap=baby.queen[worst];baby.queen[worst]=baby.queen[j];baby.queen[j]=swap;UpdateFitnessScore(&baby);if(baby.unitFitness>p->unitFitness||(double)rand()/RAND_MAX<M_Critical){*p=baby;break;}}}4.5局部搜索在实验中，发现遗传算法在求解N皇后问题时，前期算法收敛非常快，而到了算法运行的后期算法收敛就比较慢，特别是当适应度为1时.就是因为遗传算法的全局搜索能力较强，而局部搜索却较弱。局部搜索算法的基本思想为：依次交换染色体的基因位，当发现得到的新个体的适应值小于交换前的个体的适应值时，停止局部搜索.该局部搜索算法实际上改良了当前代的最优个体的染色体。由于局部搜索的时间耗费较多，为了提高算法的效率，我们只对当前种群中的最好的个体的进行局部搜索操作.4.6终止策略本文采用的终止策略为：当群体中的最优个体的适应值为0时，即表示算法搜索到了一个有效解。4.7实现描述人、双亲遗传算法。产生初始种群。从当前种群中选择两个个体。

把选中的两个父个体杂交生成中间个体。重复2和3的（选择和杂交）操作直至中间个体生成完毕。对杂交后的中间个体根据变异概率进行变异，生成新种群。检验停止准则，如果有解则停止，否则转到2重复执行。B、单亲遗传算法。产生初始种群。对当前种群根据变异概率进行变异，生成新种群。检验停止准则，如果有解则停止，否则转到2重复执行。五、实验结果和分析选择8个皇后作为测试用例。实验使用内存为512M的PC机进行测试，操作系统为WINDOWS7，开发软件为VC++6.0，开发语言为C++。程序经过执行后，输入8,则得到一个优化解，如下图:「堕：MonDec2115：11：042015吉聆MonDftc211?；：11：04231S逊小为80-000秒-由结果可得：程序的开始时间与结束时间，因而得出运算所用时间，这里运算时间非常小，因而为0秒。还可以看到八皇后的一个优化解，与本次迭代的次数。222秒cc*1□□□□□□■□BEes;匚□口匚■匚□口onon80.士-口口■口口口口口HM为！^・_Jr~nnn=小"—□□□□□■□□:-八耳□□□□□□□■一M策拉中匚■□匚匚匚口口一廿是」.苴一口□□■□□□口继续输入8,又可以得到八皇后的一个解与相应的迭代的次数，连续输入20次，则得到的迭代次数为：91,1317，165,233,359,30,11,40,216,127,195,639,13,200,90,177,