遗传算法学习（解决寻路问题）

浏览数：14 / 时间：2015年06月08日

算法描述：

检查每个基因解决问题的能力，并量化此能力值

选出当前记忆库中的基因作为父代。选择原则是：解决能力越强的别选到的概率越大。

将选出的两者根据杂交率进行杂交，生成子代

根据变异率对子代进行变异

重复2、3、4，直到新的世代产生完毕

现在要使用这个算法来解决下列寻路问题：

有一个如图所示的随机生成的迷宫，在里面确定一个起点和一个重点，找到一条重起点到重点的通路。

技术分享

类似的问题解决方法很多不再赘述，此处仅仅尝试使用遗传算法来解决。

基本思路就是把解决方案编码为基因，然后通过遗传算法的演进，找出一个解或者近似解。

解决问题：

编码方式如下：

在迷宫中的行动只有上下左右四种，用两位2进制编码恰好合适

00	→
01	↑
10	←
11	↓

接下来量化一种基因解决问题的能力，这里使用“到终点的格子距离”来度量，即：

diffx = end_point.x - x
diffy = end_point.y - y

这里的x/y这么确定：

如果按照一种基因的前进序列走到死路（即撞墙了），那么就取当前的x/y，而基因的有效长度也就止于此。

我定义的基因类如下：

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倍。

设定好了第一代，需要确定每个基因的能力值，我们使用下面这个值来表示：

fitness = 1/(diffx+diffy+1)

其中加1是为了防止分母为零。

然后开始选择父代进行繁衍，我们知道杂交和变异都不会决定整个种群的进化方向，决定方向的重大责任落在了选择这一个步骤（考虑自然界是一个道理）

这里为了满足所说的“解决能力越强的别选到的概率越大”原则，简单的采用赌轮选择法，就和赌轮一样，轮盘上面积越大的区域小球停在其中的概率就越大。

--赌轮选择
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

通过赌轮选择在种群中选出父辈，接下来进行杂交：

杂交就是，如果满足杂交条件（这里用杂交率来控制），随机选择一个杂交点，即在基因上随机确定一个点，把之前的所有片段交换，后面的片段保持不变。

如果是自交或者不满足杂交条件，就直接将父代送入子代。

--杂交
--return two arrays
function Test1:crossover(dad,mum)
    local child1 = {}
    local child2 = {}
    local rn = math.random()
    if rn<self.crossover_rate then
        local pt = math.random(#dad)
        for i=1,pt-1 do
            child1[i] = dad[i]
            child2[i] = mum[i]
        end
        for i=pt,#dad do
            child1[i] = mum[i]
            child2[i] = dad[i]
        end
    else
        child1 = dad
        child2 = mum
        
    end
    return child1,child2
end

接着对产生的子代进行变异，变异率是预先设定的，只有满足变异率的子代基因片段才会变异，变异方式采取直接翻转片段

--变异
function Test1:mutate(bits)
    for i=1,#bits do
        if math.random()<self.mutation_rate then
            if bits[i]==1 then 
                bits[i] = 0
            else
                bits[i] = 1
            end
        end
    end
end

然后对整个种群都执行上述步骤，知道新的一代产生完毕。

这里是等待子代产生完毕才替换新一代的，我目前还不确定直接把新一代拿去替换当前世代中比较弱的一些个体会出现什么情况。

下面是演进代码：

--演化
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

现在大家都在等待“君王”的出现。

“君王”的出现条件很简单：只要他成功的抵达了终点。

 if diffx+diffy<=2 then
     --中断演进输出当前基因
 end

然后，看看程序的运行结果：

我是用了20X20的地图尺寸，随机添加了一些障碍，程序下面的控制台显示整个尝试花费了42代的演进。

技术分享

值得注意的是，这个算法本来就比较耗时，再加上我使用lua进行模拟，速度比c++慢了许多，所以一个这种20X20的地图找到一个解的时间往往是相当长的，甚至有时候可能找不到解。为了不让整个程序无限制的等待下去，我限定整个种群只能演变200代，超过这个数量被视为此问题无解，如果使用的上传的程序，可以点击鼠标中键来重启整个模拟。另外，如果运气不太好的话，找到一组解的时间往往会相当的长，整个程序看上去好像死机了一样，这个时候唯一做的事情就是等待，如果程序恢复正常的响应通常情况下说明已经找到一组解了，这时候一个小僵尸会沿着这条路径从起点走到终点。

程序的所有参数可以在Test1.lua里面进行修改。

最后，为了防止随机的基因进行一些无意义的反向行动（也就是上一步向左走下一步向右走这种），我禁止并修正了这些行为：

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