题遗传算法(遗传算法的基本概念和实现)

遗传算法(遗传算法的基本概念和实现)遗传算法是受达尔文自然进化理论启发的启发式搜索算法。算法体现了自然选择的过程,即选择最优秀的人进行繁殖,产生下一代。本文简要介绍了遗传算法的基本概念和实现,希望能向读者展示启发式搜索的魅力。

遗传算法(遗传算法的基本概念和实现)

遗传算法的概念

自然选择的过程从选择最适合环境的个体开始。后代继承了父母的特点,这些特点会加到下一代身上。如果父母适应能力更好,后代更容易存活。自然选择过程是迭代进行的,最终我们会得到一个由最适合环境的个体组成的世代。

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

遗传算法包括以下五个步骤:

初始化

个人评价(适应度函数计算)

选取操作

交叉操作

变异操作

初始化

过程从种群中的一组个体开始,每个个体都是待解决问题的候选解。

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

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

遗传算法的基本概念及实现(附Java实现案例)

群体、染色体和基因

个人评价(适应度函数计算)

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

选取操作

选择操作的目的是选择适应性最好的个体,使其将基因传递给下一代。基于他们的适应度得分,我们选择多对优秀个体(父母)。适应性强的个体更容易被选择进行繁殖,也就是把更好的父母的基因传给下一代。

交叉操作

交叉操作是遗传算法中最重要的阶段。每对父母,都有随机选择的基因交集。

例如,下图的交点为3:

父母在交集之前交换基因,从而产生后代。遗传算法的基本概念及实现(附Java实现案例)

父母交换基因,然后新的后代加入种群。

遗传算法的基本概念及实现(附Java实现案例)

变异操作

在一些新的后代中,一些基因可能会受到低概率变异因素的影响。这意味着二进制位串中的一些位可能翻转。

变异操作前后的变异操作可以用来保持种群内的多样性,防止早熟收敛。

结束

当种群收敛时算法终止(种群中没有与上一代差异很大的后代)。也就是说,遗传算法为一组问题提供了解决方案。

案例实现

人口规模不变。当新的一代形成时,体能最差的个体就会死亡,给后代留下空间。重复这些阶段的顺序,以产生优于前一代的新一代。

这个迭代过程的伪代码:

STARTJava中的示例实现

下面是一个遗传算法在Java中的实现例子。我们可以随意调试和修改这些代码。给定一组五个基因,每个基因可以保存一个二进制值0或1。这里的适合度是基因组中的1个数。如果基因组中有5个1,个体的适应度达到最大。如果基因组中没有1,则个体的适应度达到最小值。遗传算法希望最大化适应度,为个体组成的种群提供最大适应度。注意:在这个例子中,经过交叉操作和变异操作后,适应度最低的个体被适应度最高的新后代所取代。

您可能还会对下面的文章感兴趣: