基于 Python 遗传算法实现【100011490】

# 遗传算法实现 ## 实验目的 熟悉掌握遗传算法。 ## 实验内容 用遗传算法求解 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 文件存储初始种群以及迭代过程的各个个体的适应度。以及最终种群。   皇后互不打架：   皇后互不打架：   皇后互不打架：  皇后互不打架：  皇后   超过最大深度    皇后：第一代就成功了，记录一下  ### 其它想要补充说明的 本次实验主要是通过随机数实现的，包括种群的大小、淘汰率、交叉互换的个体数、位置等。通过递归迭代的方法，当皇后互不冲突的对数在为 n*(n-1)/2 或者当达到最大深度时中断迭代。输出：在控制台上输出棋盘以及最优秀的个体，；在 text 文件中输出每次迭代的每个个体的适应度。 ### 实验过程中遇到的问题 本来一开始淘汰、交叉互换分别在两个函数中，但是由于种群数目比较大，每次迭代占用的空间比较多，导致系统很容易就超过了最大深度，于是就将两个函数合并在一起了，在一定程度上降低了空间复杂度，节省了系统内存开销。 在淘汰过程中在 0.13~0.145 之间随机产生一个随机数，适应度小于该数的会被淘汰，后来发现这个范围不适用于所有的种群，种群小的淘汰的就少，种群大的淘汰就多，当种群比较大的时候会出现种群所有个体全被淘汰的情况。 最后在后面处理加一个田间判断当淘汰率大于 30% 时采取新的淘汰机制——所有的种群按适应度排序，适应度越低的 25% 将会被淘汰。也可以采用直接用这个随机数作为淘汰率，然后还是要排序进行淘汰。 ## 实验心得 此次实验还算比较简单，思路比较清晰，无论是淘汰还是交叉互换算法，实现都比较容易。就是还是要注重细节，有些细节地方要仔细推敲，有些逻辑出错的地方也不容易被发现，因为这个实验有一定的随机性，每次随机生成的数都不太一样，有些不一定有解，外加迭代次数比较多，变量比较多就比较复杂，又是不清楚是自己代码逻辑闻听还是它随机生成的这些种群不行。