遗传算法学习（解决寻路问题）
发表于2016-06-26
算法描述：
1、检查每个基因解决问题的能力，并量化此能力值
2、选出当前记忆库中的基因作为父代。选择原则是：解决能力越强的别选到的概率越大。
3、将选出的两者根据杂交率进行杂交，生成子代
4、根据变异率对子代进行变异
5、重复2、3、4，直到新的世代产生完毕 现在要使用这个算法来解决下列寻路问题：
有一个如图所示的随机生成的迷宫，在里面确定一个起点和一个重点，找到一条重起点到重点的通路。
类似的问题解决方法很多不再赘述，此处仅仅尝试使用遗传算法来解决。
基本思路就是把解决方案编码为基因，然后通过遗传算法的演进，找出一个解或者近似解。
解决问题：
编码方式如下：
在迷宫中的行动只有上下左右四种，用两位2进制编码恰好合适
1 | 00 → 01 ↑ 10 ← 11 ↓ |
接下来量化一种基因解决问题的能力，这里使用“到终点的格子距离”来度量，即：
1 2 | diffx = end_point.x - x diffy = end_point.y - y |
这里的x/y这么确定：
如果按照一种基因的前进序列走到死路（即撞墙了），那么就取当前的x/y，而基因的有效长度也就止于此。
我定义的基因类如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | --Genome.lua local Genome = {} function Genome:new(len) local o = {} o.bits = {} o.fitness = 0 --math.randomseed(os.time()) for i = 1,len do if math.random()>0.5 then table.insert(o.bits,1) else table.insert(o.bits,0) end end return o end return Genome |
初始化一个基因库，这是第一代，基因的内容随机，长度设定为合适的值，库的尺寸推荐为基因长度的2倍。
设定好了第一代，需要确定每个基因的能力值，我们使用下面这个值来表示：
1 | fitness = 1/(diffx+diffy+1) |
其中加1是为了防止分母为零。
然后开始选择父代进行繁衍，我们知道杂交和变异都不会决定整个种群的进化方向，决定方向的重大责任落在了选择这一个步骤（考虑自然界是一个道理）
这里为了满足所说的“解决能力越强的别选到的概率越大”原则，简单的采用赌轮选择法，就和赌轮一样，轮盘上面积越大的区域小球停在其中的概率就越大。
1 2 3 4 5 6 7 8 9 10 11 12 | --赌轮选择 function Test1:select() local piece = math.random()*self.total_fitness local temp = 0 for i=1,#self.genomes do temp = temp + self.genomes[i].fitness if temp>=piece then return self.genomes[i] end end end |
通过赌轮选择在种群中选出父辈，接下来进行杂交：
杂交就是，如果满足杂交条件（这里用杂交率来控制），随机选择一个杂交点，即在基因上随机确定一个点，把之前的所有片段交换，后面的片段保持不变。
如果是自交或者不满足杂交条件，就直接将父代送入子代。
1 | --杂交 --return two arrays function Test1:crossover(dad,mum) local child1 = {} local child2 = {} local rn = math.random() if rn |
1 | --变异 function Test1:mutate(bits) for i=1,#bits do if math.random() |
然后对整个种群都执行上述步骤，知道新的一代产生完毕。
这里是等待子代产生完毕才替换新一代的，我目前还不确定直接把新一代拿去替换当前世代中比较弱的一些个体会出现什么情况。
下面是演进代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | --演化 function Test1:step_in() self:detect_map() local all_chids_n = 0 while all_chids_n < self.gn do --测试地图 self:detect_map() local dad = self:select() local mum = self:select() --创建新的子代 local child1 = Genome:new(self.gl) local child2 = Genome:new(self.gl) --杂交 child1.bits, child2.bits = self:crossover(dad.bits, mum.bits); --变异 self:mutate(child1.bits); self:mutate(child2.bits); --插入到新的基因库，新的基因库满表明一个世代的变更 table.insert(self.new_genomes, child1) table.insert(self.new_genomes, child2) all_chids_n = all_chids_n + 2 end self.genomes = self.new_genomes self.new_genomes = { } --记录世代数 self.ig = self.ig + 1 end |
现在大家都在等待“下一代”的出现。
“下一代”的出现条件很简单：只要他成功的抵达了终点。
1 2 3 | if diffx+diffy<=2 then --中断演进输出当前基因 end |
然后，看看程序的运行结果：
我是用了20X20的地图尺寸，随机添加了一些障碍，程序下面的控制台显示整个尝试花费了42代的演进。
值得注意的是，这个算法本来就比较耗时，再加上我使用lua进行模拟，速度比c++慢了许多，所以一个这种20X20的地图找到一个解的时间往往是 相当长的，甚至有时候可能找不到解。为了不让整个程序无限制的等待下去，我限定整个种群只能演变200代，超过这个数量被视为此问题无解，如果使用的上传 的程序，可以点击鼠标中键来重启整个模拟。另外，如果运气不太好的话，找到一组解的时间往往会相当的长，整个程序看上去好像死机了一样，这个时候唯一做的 事情就是等待，如果程序恢复正常的响应通常情况下说明已经找到一组解了，这时候一个小僵尸会沿着这条路径从起点走到终点。
程序的所有参数可以在Test1.lua里面进行修改。
最后，为了防止随机的基因进行一些无意义的反向行动（也就是上一步向左走下一步向右走这种），我禁止并修正了这些行为：
1 2 3 4 5 6 7 8 9 10 11 12 13 | if bit1 == 0 and bit2 == 1 then if self.no_back then if bith1==1 and bith2 == 1 then y = y - 1 gs[i].bits[j] = 1 gs[i].bits[j+1] = 1 else y = y + 1 end else y = y + 1 end end |
看了上面的文章 热爱游戏创作的你是不是已经开始热血沸腾了呢？是不是迫不及待的想加入游戏团队成为里面的一员呢？
福利来啦~赶快加入腾讯GAD交流群，人满封群！每天分享游戏开发内部干货、教学视频、福利活动、和有相同梦想的人在一起，更有腾讯游戏专家手把手教你做游戏！
腾讯GAD游戏程序交流群：484290331