遗传算法解迷宫.doc

一 实验要求: 一个迷宫，左边有一入口（红色方块），右边有一出口（红色方块），并有一些障碍物（黑色方块）散布在其中。然后在出发点放置一个虚拟人Bob，使用遗传算法编程实现路径寻找方案，使他能找到出口，并避免与所有障碍物相碰撞。 怎样来产生Bob的染色体的编码 ？ 怎样进行适应度评价？ 围绕染色体编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素进行文档说明 提交完整的软件系统和相关文档，包括源程序和可执行程序。（编程语言C，C+, Java任选其一） 要求程序执行时能显示当前个体的代数以及适应度函数值二 实验原理1 遗传算法 遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。 对于一个求函数最大值的优化问题(求函数最小值也类同)，一般可以描述为下列数学规划模型: 式中为决策变量，为目标函数式，式2-2、2-3为约束条件，U是基本空间，R是U的子集。满足约束条件的解X称为可行解，集合R表示所有满足约束条件的解所组成的集合，称为可行解集合。 遗传算法的基本运算过程如下: a)初始化:设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。 b)个体评价:计算群体P(t)中各个个体的适应度。 c)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。 d)交叉运算；将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。 e)变异运算:将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t 1)。 f)终止条件判断:若tT,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。2 数据结构1） Jie类 记录遗传编码及其相关操作用一个70位的int数组来表示一个基因组，其中每2位表示一步（00上01下10左右11）。因为迷宫大小固定为15*8，所以35步肯定能找到结果了。该类包含了基本的get、set操作，其中有一个名为getquan的函数,调用它将返回这个基因所代表的走法离出口最近的时候的权值.2） jieji类 代表一个由10个基因组成的种群,包含了交叉、变异、选择和GET、SET函数 public int xuanze()：评价+选择函数。先扫描记录所有基因的权值，如果找到了一个解则直接打印。然后通过轮盘法选择后代。依次累加读入的权值，将其除以总权值得到一个百分数；产生一个随机数，通过判断它落在了哪个区间选择后代。 public void jiaocha()：交叉函数 因为每代都是通过选择重新产生的，所有本函数中总是选择相邻的两个基因进行交叉操作；首先产生一个随机数，如果小于交叉率则进行交叉操作；随机选择5个位置（代表走一步的相邻2位）交换。 public void bianyi()：变异函数 首先判断判断产生的随机数是否小于变异率决定进行变异操作；然后在基因随机选择一位，取反。3） migong类 表示一个迷宫，并包含它的基本操作本次实验中的迷宫是固定的1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 6,0,1,0,0,0,0,0,1,1,1,0,0,0,1, 1,0,0,0,0,0,0,0,1,1,1,0,0,0,1, 1,0,0,0,1,1,1,0,0,1,0,0,0,0,1, 1,0,0,0,1,1,1,0,0,0,0,0,1,0,1, 1,1,0,0,1,1,1,0,0,0,0,0,1,0,1, 1,0,0,0,0,1,0,0,0,0,1,1,1,0,1, 1,0,1,1,0,0,0,1,0,0,0,0,0,0,1, 1,0,1,1,0,0,0,1,0,0,0,0,0,0,9, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1 ; 打印时顺序扫描矩阵1表示墙，6为入口，9为出口，走过的路径为100；4） zhuhanshu类 主函数 调用其他类实现算法3 算法 怎样来产生Bob的染色体的编码 ？用一个70位int数组表示染色体，初始化时随机把每一位赋值为1或0；相邻2位表示一步（00上01下10左11右） 怎样进行适应度评价？因为起点在矩阵的左上角，终点在右下角，所有越接近终点，横纵坐标平方和越大，可以用它来作为适应度。 围绕染色体编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素进行文档说明染色体编码：染色体有70位，相邻2位表示一步（00上01下10左11右），一共35步。因为迷宫为15*8固定，所有35步足够找到解。初始群体的设定：整个种群有10个染色体，初始时每个染色体都是随机产生的。适应度函数的设计：根据染色体编码所表示的走法，从起点开始模拟走一次。每走一步，计算一下起横纵坐标的平方和作为权值，若撞墙则忽略这一步。取权值的最大值作为这个染色体的适应度。遗传操作设计：不断循环产生新的子代，知道找到解。每一代执行一下操作1 评估，扫描每个染色体的适应度，如果找到解则直接调用打印函数2 选择，用轮盘法选择10次，作为子代替换群体3 交叉，调用交叉函数，每相邻2个染色体有一定概率交叉5个随机位置上的基因4 变异，调用变异函数，每个染色体都有一定概率在一个随机位置上发生反转三 实验内容代码详见程序1 生成原始种群2 不断循环，直到找到解1） 评估2） 交叉3） 变异4） 选择3 打印出这个解四 实验结果五、实验总结 1本实验原理虽然并不太难，但如果对遗传算法的精神理解不够透彻，就不容易保证算法的效率。我在这次实验中很快就完成了基本的代码编写和调试，也能得到正确的运行结果，但是效率却非常低下，往往要上万代的操作才能得到结果，耗时十多秒。然后我就投入了大量的