遗传算法系列之一:遗传算法简介

      最近博主在写毕业论文,没时间看资料,只能炒一些冷饭了——拿本科接触的东西写博客了。因此开始写遗传算法系列,这篇博客作为开端介绍遗传算法的基本知识。遗传算法的数学基础和变种将在后面介绍。

      遗传算法 ( GA , Genetic Algorithm ) ,也称进化算法 。 遗传算法是受达尔文的进化论的启发,借鉴生物进化过程而提出的一种启发式搜索算法。为了介绍遗传算法,我们先介绍一些基本概念。

           1. 基因 ( Gene ) :一个遗传因子。

           2. 染色体 ( Chromosome ) :一组的基因。

           3. 个体 ( individual ):单个生物。在遗传算法中,个体一般只包含一条染色体。

           4. 种群 ( Population ):由个体组成的群体。生物的进化以种群的形式进化。

           5. 适者生存 ( The survival of the fittest ):对环境适应度高的个体参与繁殖的机会比较多,后代就会越来越多。适应度低的个体参与繁殖的机会比较少,后代就会越来越少。

      简单说来说,繁殖过程会发生基因交叉 ( Crossover ) 和基因突变 ( Mutation ) 。适应度 ( Fitness ) 低的个体会被逐步淘汰,而适应度高的个体会越来越多。那么经过N代的自然选择后,保存下来的个体都是适应度很高的。

      遗传算法将问题的解编码成个体的染色体,并用一些个体组成种群。个体包含的解越好,则个体的适应度越好。种群中适应度高的个体获得较高概率的繁殖机会,繁殖过程中会以一定概率出现基因交叉和基因突变。经过繁殖过程,新的种群(即新的一组解)产生。上述繁殖过程重复多次,直到达到收敛条件。历史上适应度最高个体所包含的解,作为遗传算法的输出。下图是遗传算法的流程图。

                                Snip20160104_2

      根据上面的流程图,遗传算法包含三个基本操作:选择、交叉和变异。

      选择,也就是流程图中”根据适应度进行串赋值”。如下图所示,当一个种群三个个体进行自然选择时,适应度越大则被选择的概率就越大。
                                    QQ截图20160104200433

      交叉,两条染色体相互交换基因片段。遗传算法交叉比人体内染色体交叉要简单许多。遗传算法的染色体是单倍体,而人体内的真正的染色体是双倍体。下图是遗传算法中两条染色体在中间进行交叉的示意图。
                                    QQ截图20160104195436

      变异,某个基因位发生变化。下图是遗传算法中一条染色体在第二位发生基因变异的示意图。
                                    QQ截图20160104195741

      上述的选择、交叉和变异是最简单的类型,而且并不是所有问题的解决方案都可以编码成0-1向量的形式。实际上,应用遗传算法的主要工作是设计编码方案、交叉过程、变异过程和选择过程。我们将在后续博客中介绍不同问题的遗传算法。

      遗传算法是 John Henry Holland 1992年在突破性著作《Adaptation in Natural and Artificial Systems》中引入的。也就是说,遗传算法问世其实不到25年,稍微比SVM老一些。之前我一直以为遗传算法的年龄应该和神经网络差不多。John Henry Holland在去年8月9号去世。

                                    Snip20160104_6

遗传算法系列系列文章

此条目发表在算法荟萃, 遗传算法分类目录,贴了标签。将固定链接加入收藏夹。

遗传算法系列之一:遗传算法简介》有 8 条评论

  1. nick0x02说:

    《Adaptation in Natural and Artificial Systems》出版于1975年

  2. Pingback引用通告: 遗传算法系列之一:遗传算法简介 – ReidHolmes

  3. Pingback引用通告: 遗传算法系列之二:“欺骗”深度学习的遗传算法 – ReidHolmes

  4. Pingback引用通告: 遗传算法系列之三:数学摆摆手,“很惭愧,只做了一点微小的工作” – ReidHolmes

  5. Pingback引用通告: 遗传算法系列之四:遗传算法的变种 – ReidHolmes

  6. Pingback引用通告: 遗传算法系列之五:多目标遗传算法和遗传编程 – ReidHolmes

  7. Pingback引用通告: 遗传算法系列之五:多目标遗传算法和遗传编程(转) – ReidHolmes

  8. Pingback引用通告: 遗传算法系列之二:“欺骗”深度学习的遗传算法(转) – ReidHolmes

发表评论

电子邮件地址不会被公开。