遗传算法解迷宫

《遗传算法解迷宫》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一．实验要求:•一个迷宫，左边有一入口（红色方块），右边有一出口（红色方块），并有一些障碍物（黑色方块）散布在其中。然后在出发点放置一个虚拟人Bob，使用遗传算法编程实现路径寻找方案，使他能找到出口，并避免与所有障碍物相碰撞。•怎样来产生Bob的染色体的编码？•怎样进行适应度评价？•围绕染色体编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素进行文档说明•提交完整的软件系统和相关文档，包括源程序和可执行程序。（编程语言C，C++,Java任选其一）•要求程序执行时能显示当前个体的代数以及适应度函数值二．实验原理1．

2、遗传算法•遗传算法（GeneticAlgorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。•　　对于一个求函数最

3、大值的优化问题(求函数最小值也类同)，一般可以描述为下列数学规划模型:式中为决策变量，为目标函数式，式2-2、2-3为约束条件，U是基本空间，R是U的子集。满足约束条件的解X称为可行解，集合R表示所有满足约束条件的解所组成的集合，称为可行解集合。　　遗传算法的基本运算过程如下:　　a)初始化:设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。　　b)个体评价:计算群体P(t)中各个个体的适应度。　　c)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传

4、到下一代。选择操作是建立在群体中个体的适应度评估基础上的。　　d)交叉运算；将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。　　e)变异运算:将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t1)。　　f)终止条件判断:若tT,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。1．数据结构1）Jie类记录遗传编码及其相关操作用一个70位的int数组来表示一个基因组，

5、其中每2位表示一步（00上01下10左右11）。因为迷宫大小固定为15*8，所以35步肯定能找到结果了。该类包含了基本的get、set操作，其中有一个名为getquan的函数,调用它将返回这个基因所代表的走法离出口最近的时候的权值.2）jieji类代表一个由10个基因组成的种群,包含了交叉、变异、选择和GET、SET函数publicintxuanze()：：评价+选择函数。先扫描记录所有基因的权值，如果找到了一个解则直接打印。然后通过轮盘法选择后代。依次累加读入的权值，将其除以总权值得到一个百分数；产生一个随机数，通过判断它落在了哪个区间

6、选择后代。publicvoidjiaocha()：：交叉函数因为每代都是通过选择重新产生的，所有本函数中总是选择相邻的两个基因进行交叉操作；首先产生一个随机数，如果小于交叉率则进行交叉操作；随机选择5个位置（代表走一步的相邻2位）交换。publicvoidbianyi()：：变异函数首先判断判断产生的随机数是否小于变异率决定进行变异操作；然后在基因随机选择一位，取反。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,

7、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}};

8、打印时顺序扫描矩阵1表示墙，6为入口，9为出口，走过的路径为100；3）zhuhanshu类主函数调用其他类实现算法1．算法•怎样来产生Bob的染色体的编码？用一个70位int数组表示染色体，