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