遗传算法的基本概念和实现(附 Java 实现案例)
  • 作者:
  • 发表时间:2019-05-13
  • 来源:未知

  如上图(左)所示,遗传算法当个体由多条染色体组成,每条染色体由多个基因组成。上图(右)展示了染色体分割和组合方式。

  自然选择的过程从选择群体中最适应环境的个体开始。后代继承了父母的特性,并且这些特性将添加到下一代中。如果父母具有更好的适应性,那么它们的后代将更易于存活。迭代地进行该自然选择的过程,最终,我们将得到由最适应环境的个体组成的一代。

  这一概念可以被应用于搜索问题中。我们考虑一个问题的诸多解决方案,并从中搜寻出最佳方案。

  个体以一组参数(变量)为特征,这些特征被称为基因,串联这些基因就可以组成染色体(问题的解)。

  在遗传算法中,单个个体的基因组以字符串的方式呈现,通常我们可以使用二进制(1和0的字符串)编码,即一个二进制串代表一条染色体串。因此可以说我们将基因串或候选解的特征编码在染色体中。

  个体评价利用适应度函数评估了该个体对环境的适应度(与其它个体竞争的能力)。每一个体都有适应度评分,个体被选中进行繁殖的可能性取决于其适应度评分。适应度函数值越大,解的质量就越高。适应度函数是遗传算法进化的驱动力,也是进行自然选择的唯一标准,它的设计应结合求解问题本身的要求而定。

  选择运算的目的是选出适应性最好的个体,并使它们将基因传到下一代中。基于其适应度评分,我们选择多对较优个体(父母)。适应度高的个体更易被选中繁殖,即将较优父母的基因传递到下一代。

  交叉运算是遗传算法中最重要的阶段。对每一对配对的父母,基因都存在随机选中的交叉点。

  在某些形成的新后代中,它们的某些基因可能受到低概率变异因子的作用。这意味着二进制位串中的某些位可能会翻转。

  在群体收敛的情况下(群体内不产生与前一代差异较大的后代)该算法终止。也就是说遗传算法提供了一组问题的解。

  种群的规模恒定。新一代形成时,适应度最差的个体凋亡,为后代留出空间。这些阶段的序列被不断重复,以产生优于先前的新一代。

  以下展示的是遗传算法在Java中的示例实现,我们可以随意调试和修改这些代码。给定一组五个基因,每一个基因可以保存一个二进制值0或1。这里的适应度是基因组中1的数量。如果基因组内共有五个1,则该个体适应度达到最大值。如果基因组内没有1,那么个体的适应度达到最小值。该遗传算法希望最大化适应度,并提供适应度达到最大的个体所组成的群体。注意:本例中,在交叉运算与突变运算之后,适应度最低的个体被新的,适应度最高的后代所替代。

  每日头条、业界资讯、热点资讯、八卦爆料,全天跟踪微博播报。各种爆料、内幕、花边、资讯一网打尽。百万互联网粉丝互动参与,TechWeb官方微博期待您的关注。