遗传算法实现

实验目的

熟悉掌握遗传算法。

实验内容

用遗传算法求解 n 皇后问题。n*n 的棋盘上摆放 n 个皇后，两个皇后如果在同一直线或者同一对角线就会互相攻击。 找一种摆法，使得任意两个皇后之间都不会互相攻击。

问题描述：遗传算法举例：8 皇后问题

个体：长为 8 的序列，每一列的值代表对 应列的皇后所在的行。 右图状态：83742516

适应度函数= 28-互相攻击的皇后对 的数目 (不互相攻击的皇后对的数目)

好的状态对应较大的适应度函数值 (min = 0, max = 8 × 7/2 = 28。

注意事项：

种群大小（每代的个体数量）设置：可尝试 20，50，100。

迭代终止条件：对于八皇后问题，适应度函数达到 28（找到最优解）就可 以终止。也有可能你的算法写的有问题，导致适应度函数值永远无法到达 28，所以最好还是设一个最大迭代步数,或者当适应度函数值不发生变化 时终止迭代。

交叉率：0.5~1，不能太小 。

变异率：0.01~0.2，只允许少数个体变异，不能太大。

每一代最好将上一代中适应度函数值高的一些个体保留到下一代，这样就 确保下一代的结果不会比上一代差。

最后的结果画个简单的 8 皇后摆放的图。这样才能看出是否有冲突。相当 于显示一个 8*8 的矩阵，例如有皇后的地方显示数字 8，其他地方显示数字 0。

如果能解决 8 皇后问题，也可以尝试 N 皇后问题（例如 N=32）。

算法流程图或伪代码

流程图如下：

实验设置、实验运行过程和实验结果等

实验设置:

初始化种群：手动输入皇后的个数 n，初始化种群的大小为随机数，范围在 7n~13n 之间，根据皇后个数不一样种群的大小范围不一样，皇后数越多种群的越大。

适应度函数：适应度函数= n*（n-1)/2-互相攻击的皇后对的数目 (不互相攻击的皇后对的数目)。由于题目的原因在因为每列仅仅一个数字，所以列不冲突；所以只需要检查行和斜线上是否冲突。对于行上面，统计种群中每个个体重复出现的次数，在斜线上判断某个位置上的横坐标只差是否与纵坐标的之差的绝对值是否相等。

淘汰：适应度低的终将被淘汰。在 0.13~0.145 之间随机产生一个数，适应度小于该数的会被淘汰，后来发现这个范围不适用于所有的种群，种群小的淘汰的就少，种群大的淘汰就多，有时会出现种群所有个体全被淘汰的情况。 最后在后面处理加一个田间判断当淘汰率大于 30% 时采取新的淘汰机制——所有的种群按适应度排序，适应度越低的 25% 将会被淘汰。为了保证种群的大小与原来相同，在没有被淘汰的种群中随机挑选与淘汰掉的数目相同的个体进行复制，然后打乱顺序。

交叉互换：将适应度高的个体保留以保证子代的结果不会比父代差，比例为 5%；将所有个体与其对应的适应度以匹配起来，按照适应度进行排序，将排在前 5% 的保留到下一代并从父代中删除，将父代顺序打乱。随机生成父代种群大小的一半个数，表示父代相邻个体两两交叉互换的位置。

变异：在 0.01~0.04 之间随机产生一个数作为变异率，便可以得到变异的个体数目 Mutation_num，随机产生变异的 Mutation_num 个个体的变异位置 Mutationindexs，随机产生 Mutation_num 个突变成的数字,将子代中的每个在 Mutationindexs 中位置发生突变

实验运行过程及结果如下：

皇后互不打架：并用 text 文件存储初始种群以及迭代过程的各个个体的适应度。以及最终种群。

皇后互不打架：

皇后互不打架：

皇后互不打架：

皇后互不打架：

皇后

超过最大深度

皇后：第一代就成功了，记录一下