南 京 理 工 大 学

人工智能大论文

题    目： 遗传算法实现八皇后问题       

姓    名： xxxx                       

学    号： xxxxxxxxxxxxxx             

专    业： xxxxxxxxxx                 

院    系：xxxxxxxxxxxxxxxx           

老    师：xxxxxx                     

日    期：2015年12月20日           

目录

摘要... 3

一、实验背景... 4

1.1 N皇后问题描述... 4

1.2 遗传算法... 4

二、实验目的... 5

三、实验内容... 5

四、实验步骤... 5

4.1编码方案... 5

4.2初始化种群... 6

4.3适应度的计算... 7

4.4遗传算子... 8

4.4.1选择算子... 8

4.4.2交叉方法... 8

4.4.3变异方法... 8

4.5局部搜索... 10

4.6终止策略... 10

4.7实现描述... 10

五、实验结果和分析... 11

六、总结与思考... 12

摘要

 众所周知的八皇后问题是一个非常古老的问题，具体描述如下：在8*8的国际象棋棋盘上放置了八个皇后，要求没有一个皇后能吃掉另一个皇后，即任意两个皇后都不处于棋盘的同一行、同一列或同一对角线上。本实验要求设计并实现解决八皇后问题的遗传算法。能够给定任意一个初始状态，使用遗传算法搜索最优解，程序能显示优化的计算过程。独立运行20次以上，统计遗传算法的寻优指标（包括是否找到最优解、平均迭代次数等）。

本次设计旨在学习各种算法，训练对基础知识和基本方法的综合运用及变通能力，增强对算法的理解能力，提高软件设计能力，在实践中培养独立分析问题和解决问题的作风和能力。通过本实验的设计与编程实现让学生掌握基于状态空间知识表示的局部搜索策略，对遗传算法中的编码方法以及选择、复制、交叉、变异等基本算子有深入的理解，熟练运用C++，编写一个遗传算法解决八皇后问题的应用程序。

关键词：八皇后；遗传算法 ；C++

一、实验背景

1.1 N皇后问题描述

       N皇后问题描述如下：在格棋盘上放置彼此不受攻击的N个皇后。按国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。N皇后问题等价于在以下三个约束条件：任何2个皇后不放在同一行；任何2个皇后不放在同一列；任何2个皇后不放在同斜线。

       我们把的棋盘看作二维方阵，其行号从上到下列号从左到右依次编号为0，1，…，7。设任意两个皇后，皇后1和皇后2的坐标分别是（i，j）和（k，l），则如果这两个皇后在从棋盘左上角到右下角的主对角线及其平行线（斜率为-1的线）上，有；如果这两个皇后在斜率为＋1的每一斜线上，有；以上两个方程分别等价于和因此任两皇后的在同一斜线上的充要条件是。

满足两个皇后不在同一斜线上的条件表示为：                         

两皇后不在同一行用式表示为：                                            

两皇后不在同一列用式表示为：                                            

1.2 遗传算法

遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。

二、实验目的

N皇后问题是经典的益智游戏，通过本实验的设计与编程实现让学生掌握基于状态空间知识表示的局部搜索策略，对遗传算法中的编码方法以及选择、复制、交叉、变异等基本算子有深入的理解。

本次设计旨在学习各种算法，训练对基础知识和基本方法的综合运用及变通能力，增强对算法的理解能力，提高软件设计能力，在实践中培养独立分析问题和解决问题的作风和能力。熟练运用C++语言，独立编程，实现一个遗传算法解决八皇后问题的应用程序。

三、实验内容

本实验要求设计并实现解决八皇后问题的遗传算法。能够给定任意一个初始状态，使用遗传算法搜索最优解，程序能显示优化的计算过程。独立运行20次以上，统计遗传算法的寻优指标（包括是否找到最优解、平均迭代次数等）。

因为我的学号末尾为0，按照老师要求，则应该实现，即八皇后问题。

四、实验步骤

现在我们把任意n个皇后的任意一种放置办法当作一个个体（染色体），把其中的任意一个皇后当作一个基因，用遗传算法来解决该问题。

4.1编码方案

对于此问题有三种编码方案：排列编码、二进制编码、矩阵编码，在这里，采用第一重编码方案，即排列编码，具体描述如下：

用一维n元数组来表示一个个体，其中，表示皇后放在棋盘的第行第列，即第行第列放置一个皇后。例如，表示棋盘的第0行第0列放一个皇后。数组第i个元素表示第i行的放置情况，可以看作一个基因。这种编码可以自然的解决了某一行只能放一个皇后的约束，如果数组的每一个元素都不重复，可以看成0—n-1的一种排列，就自然保证每一列只能放一个皇后。因此在交叉变异和产生个体时必须注意的唯一性。

4.2初始化种群

初始化种群的主要工作为：确定种群的大小及产生初始种群.种群的大小能够对遗传算法的收敛性产生很大的影响，种群较小算法收敛速度较快，但它的搜索面不够广，容易导致局部收敛；而种群较大算法收敛全局最优的概率也大，但是算法的收敛速度较慢。因此根据N皇后问题的特点，本文将种群大小设为N(皇后数)。初始化种群的方法为：首先为每个体的染色体的基因位从1到N，然后随机交换两个基因位的值，对每个个体共交换N/2次，对种群中所有个体做上述操作。双亲遗传时候的初始化种群实现如下：

void CreateMultiStartPopulation ()

{    

       int loop, i, j ;

       int tmp[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适应度的计算

设表示皇后i和皇后j之间的相互攻击，即：

皇后i和j的攻击度：     

第i个皇后的攻击度表示皇后i在除自身外其余n-1个皇后中与皇后i相冲突的数目，即有几个皇后与皇后i相攻击。如果皇后i和所有皇后都冲突则攻击度为n-1，与所有的皇后都不冲突攻击度为0。因此，得到。

同理，皇后i的非攻击度表示和皇后i没有冲突的皇后数目，设表示i的非攻击度，则。

我们根据非攻击度计算：用表示基因i的适应度，即第i个皇后的非攻击度，则。如果某一个皇后i和所有其余的n-1个皇后都互不攻击，则。

个体的适应度是指所有皇后的非攻击度之和，适应度函数可表示如下：。对于一个合法的放置方案每一个基因的适应度都是n-1，此时染色体的适应度是。

// 更新 p 的适应度

void UpdateFitnessScore (Population *p)

{

       int i, 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选择算子

       目前常用的选择算子有二种：轮盘赌选择算子和二进制锦标赛选择算子。轮盘赌

选择算子的缺点在于容易产生出超级个体，易导致算法局部收敛。但为了实现简单，我选择轮盘赌选择算子，即被选到的概率与适应度呈正比 （越是优越的个体基因越容易被保留下来），具体试下如下：

int RouletteWheelSelection()

{

       int selection = 0;

       int i ;

       double slice = (double)rand() / RAND_MAX;

       double addFitness = 0;

       for(i = 0; i < m_size ; i++)

       {

              addFitness +=  (double)m_population[i].unitFitness / m_totFitness ;

              if(addFitness > slice)

              {

                     selection = i;

                     break;

              }

       }

       return selection;

}

4.4.2交叉方法

       交叉方法可用的交叉方法有以下几种。设p1，p2是要交叉的两个父染色体，c1，c2是子代，是交叉的结果，n是编码长度。

单点交叉：先随机生成交叉位置，把p1[0:m]与p2[0:m]部分互换分别得到c1，c2。

4.4.3变异方法

采用随机变异方法。随机生成变异数目m，随机选择m个皇后把它去掉，然后再随机选择m个位置放上皇后。

单亲遗传：通过随机交换适应度最低的基因与其他基因的位置，产生新的子代。具体性实现如下：

// 单亲遗传 父代变异函数

void SimpleMutate ()

{

       int i, j, swap ;

       int worst ;

       Population baby ;

       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.unitFitness

                     || (double)rand() / RAND_MAX < Critical)

                     s_population = baby ;

}

双亲遗传中的变异算子，对种群中的最优两个个体保留，并局部变异看是否可以达到结果，具体代码如下：

// 单亲遗传 父代变异函数

void MultiMutate (Population* p)

{

       int i, j, swap ;

       int worst ;

       Population baby ;

       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实现描述

A、双亲遗传算法。

1.        产生初始种群。

2.        从当前种群中选择两个个体。

3.        把选中的两个父个体杂交生成中间个体。

4.        重复2和3的（选择和杂交）操作直至中间个体生成完毕。

5.        对杂交后的中间个体根据变异概率进行变异，生成新种群。

6.        检验停止准则，如果有解则停止，否则转到2重复执行。

B、单亲遗传算法。

1.        产生初始种群。

2.        对当前种群根据变异概率进行变异，生成新种群。

3.        检验停止准则，如果有解则停止，否则转到2重复执行。

五、实验结果和分析

选择8个皇后作为测试用例。实验使用内存为512M的PC机进行测试，操作系统为WINDOWS 7，开发软件为VC++6.0，开发语言为C++。

程序经过执行后，输入8，则得到一个优化解，如下图：

    由结果可得：程序的开始时间与结束时间，因而得出运算所用时间，这里运算时间非常小，因而为0秒。还可以看到八皇后的一个优化解，与本次迭代的次数。

    继续输入8，又可以得到八皇后的一个解与相应的迭代的次数，连续输入20次，则得到的迭代次数为：91,1317，165,233,359,30,11,40,216,127,195,639,13,200,

90,177,219,274,1072,2691。算得平均迭代次数为：408次。

六、总结与思考

就编写的程序而言，虽然能达到预期的结果，但总体结构还不够简洁，不太容易去理解。许多问题还需要继续研究，许多技术还需要更多的改进。去图书馆借了不少书，也去网上看了些资料，只是对大概的知识有了点了解，但还是很难着手于写代码，后来就按照老师说的，先搞清楚原理，再考虑如何去实现！后来又去上网查看相关资料，又到图书馆借了很多书看，总算有头绪了。但在调试过程中，还是遇到了很多困难，后来通过了室友的帮助才把问题解决了。

在编写代码时，我希望能随机选择一数 X(1～92)后，能输出该种情况所对应的八个皇后的摆放方式和每个皇后所在的位置，但想了好久，就是无法实现。而且，当92种情况都输出时，前面的几十种情况无法看到，要想让摆放皇后的图形和所在具体的位置一起输出，就得修改程序让使她们一个一个地输出，这样显然比较麻烦。

针对八皇后这个课题，也许表层只局限于对八个皇后的摆放，但还可以对更多的情况进行探讨分析，比如九皇后，十皇后等等。但也许随着皇后个数的增多，程序运行的时间将变得长，考虑能否将运行的时间继续缩短。

总之，通过这次的程序设计，我从中得到了许多。从这个八皇后问题设计以及分析中，本人从中理解到了算法与数据结构对于计算机软件设计的重要性。它的使用，可以改变一个软件的运行周期，也可以将软件的思路从繁化简，并且都能够通过数据结构的相关引导，将本身以前编程思想进行扩充。在这个阶段，我也明白了，好的思想，不能提留于字面上的认知，还需要的是平时多练多写一些相关的程序，并且通过修改，加入新的算法去尝试改变自己的一些编程思想。只有多练多做，才能拥有新思维、新想法，只有多练多做，才能写出效率高的程序。