用遗传算法解迷宫问题的实现与改进.doc

用遗传算法解迷宫问题的实现与改进 副标题： 作者：张超 文章来源：人工智能爱好者 点击数： 83 更新时间：2004-9-17 摘要：本文利用遗传算法的思想，对传统的二维迷宫问题，设计编码、适应值函数、遗传操作，并在演化过程中对基因进行“改良”，提高搜索的效率。关键字：遗传算法?二维迷宫?基因改良遗传算法作为一种随机的群体搜索算法，模拟生物进化的过程，对问题可能的解进行编码形成基因，从初始种群开始，使用评价函数决定个体的优胜劣汰，并通过个体间的杂交和变异，使种群不断演化，向着所求的更优良的解靠近。传统的二维迷宫问题，用一个max_y*max_x的矩阵来表示迷宫，矩阵每一点为0（可走的路）或者1（障碍物）。给定一个出发点，一个目的点，要求找到一条从出发点到目的点的路径，只能在可走的路径（0）上走，而且在每一点，只能向上下左右四个方向的相邻点运动。解决这个问题已经有了很多有效的方法，如深度优先搜索、启发式搜索等，其本质是要找到一个行动方向的序列，最终能到达目的地。因此我考虑使用遗传算法，通过遗传操作，“演化”出这样的路径。为了简化问题，在本文讨论的迷宫中，出发点为左上角（坐标（1，1）），目的点为右下角（坐标（max_x,max_y））。但有一点跟比较常见的用遗传算法解的问题有所不同，很多问题有最优解，但希望只是找到比较优的解，越优越好。然而在迷宫问题中，很有可能出现找不到解的情况，在这样的情况下讨论算法的效率就毫无意义了，因为它根本无效。这也是在做试验时要有所考虑的。一、 求解迷宫问题的遗传算法的具体实现：1、 染色体的编码：我参考了一些相关的资料，决定采用这种比较常规的编码方法。在迷宫每一点，都有四个方向可以选择，用0、1、2、3表示，右（0），下（1），左（2），上（3）。这样，由一组数码串就构成了一个走向序列，也就是一条染色体。染色体存在数组gene[][]中，比如gene[i][j]表示群体中第i条染色体第j位。假设迷宫的行数为max_y，迷宫列数为max_x，则对应的问题解的染色体长度为max_y*max_y，记为gene_len。当然在按照这样的序列“走”的时候，其中会产生不少“无效位”，即朝一个方向走到障碍物等，这时的处理方法是直接跳过看下一位。2、 适应值函数的计算：????用这样的方式来评价染色体的好坏：顺着染色体的走向序列走，即从（1，1）开始按染色体每位的方向位改变当前位置，扫过整条染色体，跳过无效位，对经过的每一个坐标，都计算该坐标点与目的点的距离，取其中最小的值为该条染色体的适应值，记入fun[]数组中。适应值越小，染色体越优。同时记录下取得适应值所对应得位，存在now_p[]数组中，这是为了后面的基因变异做准备。例如：在一个如下的4*4的迷宫中：0011100011000000染色体i为：1011120000211111它所对应的经过点的坐标为：（1，1）（2，1）（2，2）（3，2）（4，2）（3，2）（3，3）（3，4），其适应值为1（（3，4）点离（4，4）的距离为1）。显然，我们最终要找的是适应值为0的染色体。搜索过程中，当前获得的最优适应值记录在变量best_fit中，最优染色体记录在数组hero[]中。每迭代一次，检查best_fit的值，当等于0时搜索结束。3、 遗传操作：在算法中设置一个参数mutata_part表示父代中进行变异操作的比例。计算完适应值后将群体中的染色体按适应值从优到劣排序，比较优的那部分进行变异操作，余下的进行杂交。1）变异：在这种编码方式下，由于改变染色体中的某一位会很大程度改变整个序列的走向，因此在演化中，采取改变某一位（特别是有效位，但如果是无效也有意义的，因为可能在杂交的时候对后代产生影响）作为变异方式，能使种群变化很显著。具体的实现方式是这样的。变异位置存在两种选择，一是在刚刚记录的取得适应值的now_p[i]的后面随机产生，这样做的好处在于，不改变取得适应值前的各个位，使该染色体的适应值只可能变优。另外一种选择就是在now_p[i]前面随机确定，这样做使得一些走入“死角”的染色体及早改变走向。两种方式各分配一定比例，用参数mutate_rate确定。注意到，当fun[i]gene_len-now[p]时，也即当按照这条染色体的方向序列走到取得适应值的坐标后，无论之后的方向序列如何都不可能达到目的点，那也就只有选择第二种变异位置才有意义。设k位确定下的变异位置，则变异后gene[i][k]=(gene[i][k]+1)?mod?42）杂交：杂交的方式是相邻两条染色体交换所有偶数位，产生两个后代。如染色21013211进行杂交后生20003211