视频源:

Microbial Genetic Algorithm

作者: UnityTutorial 编辑: UnityTutorial 2017-08-12

学习资料:

要点

如果对遗传算法有兴趣的朋友, 强烈推荐先看看我制作的动画短片 什么是遗传算法, 在动画里有了基础的了解, 在接下来的内容中, 你就如鱼得水啦.

说到遗传算法 (GA), 有一点不得不提的是如何有效保留好的父母 (Elitism), 让好的父母不会消失掉. 这也是永远都给自己留条后路的意思. Microbial GA (后面统称 MGA) 就是一个很好的保留 Elitism 的算法. 一句话来概括: 在袋子里抽两个球, 对比两个球, 把球大的放回袋子里, 把球小的变一下再放回袋子里, 这样在这次选着中, 大球不会被改变任何东西, 就被放回了袋子, 当作下一代的一部分.

Microbial Genetic Algorithm

算法

Microbial Genetic Algorithm

像最开始说的那样, 我们有一些 population, 每次在进化的时候, 我们会从这个 pop 中随机抽 2 个 DNA 出来, 然后对比一下他们的 fitness, 我们将 fitness 高的定义成 winner, 反之是 loser. 我们不会去动任何 winner 的 DNA, 要动手脚的只有这个 loser, 比如对 loser 进行 crossovermutate. 动完手脚后将 winnerloser 一同放回 pop 中.

通过这样的流程, 我们就不用担心有时候变异着变异着, 那些原本好的 pop 流失掉了, 有了这个 MGA 算法, winner 总是会被保留下来的. GA 中的 Elitism 问题通过这种方法巧妙解决了.

进化啦

这次我们还是通过之前那个找曲线中最大点的方式诠释 MGA 算法. class 中的结构框架基本没变, 只是少了 select 的功能. 因为我们会将 select 功能写在 evolve 中. 这样方便点.

class MGA:
    def crossover(self, loser_winner):

    def mutate(self, loser_winner):

    def evolve(self, n):

首先我们先说 evolve, 在这个功能中, 两只手进入袋子去抓两个 DNA 出来的动作要进行 n 次, 然后每一次评估一下这两个抓出来的 DNA 的 fitness 怎么样. 这样我们就能定义这两个中, 哪个是 winner, 哪个是 loser. 对于 loser, 我们将 winner 的一部分 DNA crossover 去 loser 那, 期望 loser 有了 winner 的这一部分基因能变好一点. 然后 loser 再通过一部分几率 mutate 一下. 所以在 evolve 中的算法就是这样写:

class MGA:
    def evolve(self, n):    # nature selection wrt pop's fitness
        for _ in range(n):  # random pick and compare n times
            sub_pop_idx = np.random.choice(np.arange(0, self.pop_size), size=2, replace=False)
            sub_pop = self.pop[sub_pop_idx]             # pick 2 from pop
            product = F(self.translateDNA(sub_pop))
            fitness = self.get_fitness(product)
            loser_winner_idx = np.argsort(fitness)
            loser_winner = sub_pop[loser_winner_idx]    # the first is loser and second is winner
            loser_winner = self.crossover(loser_winner)
            loser_winner = self.mutate(loser_winner)
            self.pop[sub_pop_idx] = loser_winner

crossovermutate 都是按上面的说法, 只在 winner_loser 中进行. 因为这里的 DNA 是用二进制编码的. 如果不明白这里发生了什么, 请看到这个教程里面的详细说明.

class MGA:
    def crossover(self, loser_winner):      # crossover for loser
        cross_idx = np.empty((self.DNA_size,)).astype(np.bool)
        for i in range(self.DNA_size):
            cross_idx[i] = True if np.random.rand() < self.cross_rate else False  # crossover index
        loser_winner[0, cross_idx] = loser_winner[1, cross_idx]  # assign winners genes to loser
        return loser_winner

    def mutate(self, loser_winner):         # mutation for loser
        mutation_idx = np.empty((self.DNA_size,)).astype(np.bool)
        for i in range(self.DNA_size):
            mutation_idx[i] = True if np.random.rand() < self.mutate_rate else False  # mutation index
        # flip values in mutation points
        loser_winner[0, mutation_idx] = ~loser_winner[0, mutation_idx].astype(np.bool)
        return loser_winner

如果觉得看整体代码可能方便理解的话, 请去往我的 github 中查看整套代码. 最后套上训练的循环, 就完事啦.

ga = MGA(...)

for generation in range(N_GENERATIONS):
    ga.evolve(n=5)

文章里面的代码都是简化版的, 如果要看到完整版和可视化的代码, 请去往我的 github.

分享到: Facebook 微博 微信 Twitter
如果你觉得这篇文章或视频对你的学习很有帮助, 请你也分享它, 让它能再次帮助到更多的需要学习的人. UnityTutorial没有正式的经济来源, 如果你也想支持 UnityTutorial 并看到更好的教学内容, 赞助他一点点, 作为鼓励他继续开源的动力.

支持 让教学变得更优秀