遗传算法学习及其在迷宫问题的应用代码实现

目录 第一部分 遗传算法介绍第一部分 遗传算法介绍 2 1 1 遗传算法的产生和发展 2 1 2 遗传算法的基本求解步骤 3 第二部分 遗传算法解决迷宫问题 代码在文件夹代码中 可执行第二部分 遗传算法解决迷宫问题 代码在文件夹代码中 可执行 程序在文件夹程序中 程序在文件夹程序中 4 2 1 问题概述 构建迷宫 问题概述 构建迷宫 4 2 2 为染色体编码为染色体编码 6 2 3Epoch 时代时代 方法方法 10 2 42 4 参数值选择参数值选择 13 2 52 5 算子函数算子函数 14 2 62 6 运行迷宫程序运行迷宫程序 16 参考文献参考文献 17 遗传算法学习及其在迷宫问题的应用遗传算法学习及其在迷宫问题的应用 第一部分 遗传算法介绍第一部分 遗传算法介绍 遗传算法 genetic algorithms GA 是一种模拟自然选择和遗传机制的寻优 方法 它是建立在达尔文的生物进化论和孟德尔的遗传学说基础上的算法 基 因杂交和基因突变可能产生对环境适应性强的后代 通过优胜劣汰的自然选择 适应值高的基因结构就保存下来 遗传算法就是模仿了生物的遗传 进化原理 并引用了随机统计原理而形成的 1 1 遗传算法的产生和发展 50 年代末 60 年代初 生物学家 Fraser 试图通过计算的方法来模拟生物界 遗 传与选择 的进化过程 这便是 GA 的雏形 受此启发 Holland 教授认识到自 然遗传可以转化为人工遗传算法 1967 年 Bagley 在其博士论文中首次提出了 遗传算法 这一术语 1975 年 Holland 出版了 自然与人工系统中的适应性行为 该书系统地阐述了遗传算 法的基本理论和方法 提出了遗传算法的基本定理 模式定理 从而奠定了遗传 算法的理论基础 20 世纪 80 年代初 Holland 教授实现了第一个基于遗传算法的机器学习系统 分类器系统 Classifier System 简称 CS 开创了基于遗传算法的机器学习的新概念 l992 年 John R Koza 出版了专著 遗传编程 提出了遗传编程的概念 并 成功地把遗传编程的方法应用于人工智能 机器学习 符号处理等方面 随着 遗传算法的不断发展 关于遗传算法的国际学术活动越来越多 遗传算法已成 为一个多学科 多领域的重要研究方向 1 2 遗传算法的基本求解步骤 1 2 1 编码 确定用何种码制 然后将问题参数编码形成基因码链 每一个码链 代表一个个体 表示优化问题的一个解 1 2 2 初始化 随机产生一个规模为 P 的初始种群 其中每个个体为一定长度的 码链 该群体代表优化问题的一些可能解的集合 1 2 3 估计适应度 计算种群中每个个体的适应度 适应度为群体进化时的选择 提供了依据 一般来说适应度越高 解的素质越好 适应度函数可以根据目标 函数而定 1 2 4 再生 选择 根据每个个体的相对适应度 计算每个个体的再生次数 并进 行再生操作 产生新的个体加人下一代群体中 一般再生的概率与其适应度成正 比 1 2 5 交叉 从种群中随机选择两个染色体 按一定的概率进行基因交换 交换位 置的选取是随机的 1 2 6 变异 从种群中随机地选择一个染色体 按一定的变异概率 P 进行基因变 异 GA 的搜索能力主要是由选择与交叉赋于的 变异算子则保证了算法能搜索到 问题空间的每一点 从而使算法具有全局最优性 它进一步增强了 GA 的能力 1 2 7 重复 若发现最优解 则算法停止 否则转 3 对产生的新一代群体进行重 新评价 选择 交叉 变异操作 如此循环往复 使群体中最优个体的适应度和 平均适应度不断提高 其流程图如下 第二部分 遗传算法解决迷宫问题 代码在文件夹代码中 可执行第二部分 遗传算法解决迷宫问题 代码在文件夹代码中 可执行 程序在文件夹程序中 程序在文件夹程序中 2 1 问题概述 构建迷宫 问题概述 构建迷宫 寻找路径问题是游戏人工智能的一块 神圣基石 下面就来创建一个遗传 算法用在一个非常简单的场景中解决寻找路径问题 首先创建一个迷宫 他的 左边有一个路口 右边有一个出口 并且有一些障碍物布在其中 在出发点放 置一个虚拟的人鲍勃 然后要为他解决如何寻找路径的问题 使他能找到出口 并且避免与所有的障碍物相碰撞 下面讲述如何产生鲍勃的染色体的编码 但 首先要解释如何来表示迷宫 迷宫是一个二维整数数组 用 0 来表示开放的空间 1 来表示墙壁或者障碍 物 5 为起始点 8 为出口 因此 假设迷宫的二维数组如下 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 1 0 0 0 1 8 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 5 1 0 1 1 0 0 0 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 在屏幕中的显示效果如图 1 所示 图 1 迷宫实际显示效果图 这种地图的设计方法被封装在一个被称为 CBobsMap 的类中 并定义为 class CBobsMap private 保存地图用的存储器 一个二维整数数组 static const intmap MAP HEIGHT MAP WIDTH static const intm iMapWidth 地图宽读 static const intm iMapHeight 地图高度 起始点在数组中的下标 static const intm iStartX static const intm iStartY 终点的数组下标 static const intm iEndX static const int m iEndY public 如果需要 可以利用这一数组作为 Bob 走过的路程的存储器 int memory MAP HEIGHT MAP WIDTH CBobsMap ResetMemory 利用一个字符串来记录 Bob 行进的方向 其中每个字符代表 Bob 所走 的一步 检查 Bob 离出口还有多远 返回一个与到达出口距离成正比的适应性 分数 double TestRoute const vector Render 函数利用 windows GDI 在一个给定的作图表面上显示地图 void Render const int cxClient const int cyClient HDC surface 画出能够存放于存储器中的任意路径 void MemoryRender const int cxClient const int cyClient HDC surface void ResetMemory 由上可知 只需要以常量的形式来保存地图数组以及起点与重点就行了 这些数据在文件 CBobsMap cpp 中定义的 除了存储迷宫 这个 Map 类也用来 记录 Bob 在迷宫中行走的路程 memory 这对遗传算法本身而言不是本质的 但是为了显示目的 看清 Bob 怎样在迷宫中漫游 设置一个记录是必须的 2 2 为染色体编码为染色体编码 每个染色体必须把 Bob 的每一步行动都编入代码中 Bob 的行动权限为四 个方向 向东 向南 向西 向北 故编码后的染色体应该是代表这四个方向 信息的一个字符串 传统的编码方法就是把方向变换成二进制的代码 4 个方 向只有两位就够了 例如下表所示的那样 二进制代码十进制译码代表的方向 000向北 011向南 102向东 113向西 这样如果得到了一个随机的二进制字符串 就能根据它译出 Bob 行动时所 遵循的一系列方向 例如染色体 111110011011101110010101 代表的基因就是 11 11 10 01 10 11 10 11 10 01 01 01 当把二进制代码转化为十进制时 就成为 3 3 2 1 2 3 2 3 2 1 1 1 再把这些放进一个表格中 到此 所要做的全部就是将 Bob 置于迷宫的起点 然后告诉他根据这张表 中的方向一步步的走 如果一个方向使得 Bob 碰到了墙壁或者障碍物 则只需 二进制代 码 十进制译 码 代表的方 向 113向西 113向西 102向东 011向南 102向东 113向西 102向东 113向西 102向东 011向南 011向南 011向南 要忽略该指令并继续按下一条指令去走就行了 这样不断下去 直到用完所有 方向或 Bob 到达出口为止 假如有几百个这样随机的染色体 它们中的某些就 可能为 Bob 译码出到达出口的一套方法 问题的一个解 但是它们当中大多数 是失败的 遗传算法以随机的二进制串 染色体 作为初始群体 测试它们每 一个能让 Bob 走到离出口有多么近 然后让其中最好的那些来孵化后代 期待 它们的子孙 中能有比 Bob 走的离出口更近一点 这样继续下去 直到找出一 个解 或直到 Bob 绝望地在一个角落里被困住不动为止 因此 必须来定义一种结构 其中包含一个二进制位串 染色体 以及一 个与该染色体想联系的适应性分数 这个结构称为 SGenome 结构 它的定义如 struct SGenome vector vecBits doubledFitness SGenome dFitness 0 SGenome const int num bits dFitness 0 创造随机的二进制串 for int i 0 i num bits i vecBits push back RandInt 0 1 如果在创建 SGenome 对象时把一个整型数作为参数传递给构造函数 则它 就会自动创建一个以此整数为长度的随机二进制位串 并将其适应性分数初始 化为零 完成对该基因组的设置 SGenome 结构不具备如何为染色体 vecBits 进行译码的知识 这是需要由遗 传算法类自己来完成的一项任务 下面简单介绍这个类的定义 这里将其称为 CgaBob 类 class CgaBob private vectorm vecGenomes 基因组群体 Int m iPopSize 群体的大小 Double m dCrossoverRate Double m dMutationRate Int m iChromoLength 每个染色体含有多少 bit Int m iGeneLength 每个基因有多少 bits Int m iFittestGenome Double m dBestFitnessScore Double m dTotalFitnessScore Int m iGeneration 为 map 类创建一个实例 CBobsMapm BobsMap 另一个 CbobsMap 对象 用来保存每一代的最佳路径的一个记录 这是被访问小格的一个数组 它仅为了显示目的而使用 CBobsMapm BobsBrain 检测运行是否仍在进行中 boolm bBusy void Mutate vector void Crossover const vector SGenome 用新的适应性分数来更新基因组原有的适应性分数 并计算群体的最高适应性分数和适应性分数最高的那个成员 void UpdateFitnessScores 把一个位向量译成为一个方向的 整数 向量 vectorDecode const vector 把一个位向量变换为十进制数 用于译码 int BinToInt const vector 创建一个随机的二进制伉串的初始群体 void CreateStartPopulation public CgaBob double cross rat double mut rat int pop size int num bits int gene len m dCrossoverRate cross rat m dMutationRate mut rat m iPopSize pop size m iChromoLength num bits m dTotalFitnessScore 0 0 m iGeneration 0 m iGeneLength gene len m bBusy false CreateStartPopulation voidRun HWND hwnd voidRender int cxClient int cyClient HDC surface voidEpoch 访问用的方法 intGeneration return m iGeneration intGetFittest return m iFittestGenome bool Started return m bBusy voidStop m bBusy false 由上述内容可知 当这个类的一个实例被创建时 构造函数初始化所有的 变量 并调用 CreateStartPopulation 这一短小函数创建了所需数量的基因组 群体 每个基因一开始包含的是一个由随机二进制位串组成的染色体 其适应 性分数则被设置为零 2 3Epoch 时代时代 方法方法 遗传算法类中最为实际的内容就是 Epoch 方法 这也是之前提到的遗传算 法的那个循环 它是这个类中执行工作的部门 这一方法与所有工作或多或少 都联系在一起 下面就对它进行详细讲述 void CgaBob epoch UpdateFitnessScores 在每一个 epoch 循环内所要做的第一件事情 就是测试染色体群中每一个 成员的适应性分数 UpdateFitnessScores 是用来对每个基因组的二进制染色体 编码进行译码的函数 而由它再把译码所得到的一系列结果 也就是由代表东 南 西 北 4 个方向的整数 发送给 CBobsMap TestRout 后者检查 Bob 在地 图中游走了多远 并根据 Bob 离开出口 l 的最终距离 返回一个相应的适应性 分数 计算 Bob 的适应性分数程序如下 int DiffX abs posX m iEndX int DiffY abs posY m iEndY 这里 DiffX 和 DiffY 就是 Bob 所在格子的位置相对于迷宫出口的水平和垂直 偏离值 观察图 2 灰色小格代表 Bob 通过迷宫的路程 上面写着 B 的小格是 他最终所到达的地方 在这一位置上 Diffx 3 DiffY 0 return 1 double DiffX DiffY 1 上面的一行程序就是计算 Bob 的适应性分数 它把 DiffX 与 DiffY 这两个数 字加起来然后求倒数 DiffX 与 DiffY 的和数中还加了一个 1 这是为了确保除法 不会出现分母为零的错误 如果 Bob 到达出口 Diffx DiffY 0 UpdateFitnessScores 也保持对每一代中适应性分数最高的基因组以及与所 有基因组相关的适应性分数的跟踪 这些数值在执行赌轮选择时要使用 B 图 2 Bob 尝试寻找迷宫出口 重新讨论 Epoch 函数 由于在每一个 Epoch 中将会创建一个新的基因组群 因此 当它们在创建出来时 每次 2 个基因组 需要寻找一些地方来保存它们 现在创建一个新的群体 int NewBabies 0 为婴儿基因组创建存储器 vectorvecBabyGenomes 现在继续讨论遗传算法循环中所处理的事务 while NewBabies m iPopsize 用赌轮法选择两个上辈 parents SGenome mum RouletteWheelSelection SGenome dad RouletteWheelSelection 在每次迭代过程中 需要选择两个基因组来作为两个新生婴儿的染色体的父辈 分别称为 dad 父亲 和 mum 母亲 一个基因组的适应性愈强 则由赌轮方 法选择作为父母的几率也越大 杂交操作 SGenome baby1 baby2 Crossover num vecBitsdad vecBits baby1 vecBits baby2 vecBits 以上 2 行程序的工作是 创建两个空白基因组 这就是两个婴儿 它们与所选 的父辈一起传递给杂交函数 Crossover 这一函数执行了杂交 需依靠 m dCrossoverRate 变量来进行 并把新的染色体的二进制位串存放到 baby1 和 baby2 中 变异操作 Mutate baby1 vecBits Mutate baby2 vecBits 以上这两步是对婴儿实行突变 这听起来可怕 但这对他们是有利的 1 个婴儿的位的突变概率依赖于 m dMutationRate 变景 把两个新生婴儿加入新群体 veaBabyGenomes push back baby1 vecBabyGenomes push back baby2 NewBabies 2 这两个新生后代最终要加入到新的群体中 这样就完成了一次 Loop 的迭代 过程 这一过程需要不断重复 直到创建出来的后代总量和初始群体的大小相 同 把所有婴儿复制到初始群体 m vecGenome5 vecBabyGenome 代的数量加 1 m iGeneration 这里 原有的那个群体由新生一代所组成的群体来代替 并把代的数量加 1 以跟踪当前的代 这一 Epoch 函数将无止境地重复 直到染色体收敛到了一个解 或用户要 求停止时为止 在此首先讲述如何确定使用参数的值 2 42 4 参数值选择参数值选择 程序所用的所有参数存放在文件 defines h 中 这些参数中大多数是目了然的 但有几个需要说明一下 即 define CROSSOVER RATE 0 7 define MUTATION RATE 0 001 define POP SIZE 140 define CHROMO LENGTH 70 如何确定这些变量的初值 而这是价值百万美元的问题 但至今还没有快 速而有效的规则 有的只是一些原则性的指导 而且 选择这些值最终还应归 结为每个用户对遗传算法的体验 用户只能通过自己的编程实践 用各种不同 的参数值进行调试 看结果会发生什么 并从中选取适合的值 不同的问题需 要不同的值 但是通常来说 如果在使用二进制编码的染色体 则应把杂交率 定在 0 7 变异率定在 0 001 这将是很好的初始默认值 而确定群体大小的一 条有用规则是将基因组的数目取为染色体长度的 2 倍 因 70 表示 Bob 的 35 步 的最大可能移动数目 所以这里选择 70 作为染色体长度 它比 Bob 为穿越地图 到达出口所需的步数还要大一些 2 52 5 算子函数算子函数 重新阐述一下遗传算法的各种操作 或称算子 函数 选择 杂交 变异 的代码 2 5 1 赌轮选择 首先讲述赌轮选择算法 这一个函数的功能是从群体中选择一个基因组 选中的几率正比于基因组的适应性分数 SGenome 在从零到整个适应性分数范围内随机选取了一实数 fSlice 可以将此数看 作整个适应性分数饼图中的一块 如图 3 所示 double cfTotal 0 int SelectedGenome 0 for int i 0 ifslice SelectedGenome i break return m vecGenomes SelectedGenome 现在 程序通过循环来考察各个基因组 把它们相应的适应性分数一个一 个累加起来 直到这一部分累加和大于 fSlice 的值时 即返回该基因组 2 5 2 杂交算子 这一函数要求两个染色体在同一随机位置上断裂开来 然后将它们在断开 点以后的部分进行互换 以形成两个新的染色体 子代 void CgaBab Crossover const vector baby2 dad return 程序的作用为 首先进行检测 决定 mum 和 dad 两个上辈是否需要进行杂交 杂交发生的概率是由参数 m dCrossoverRate 确定的 如果不发生杂交 则两 个父辈染