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

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

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

遗传算法的概念

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

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

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

初始化

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

选择操作

交叉操作

突变操作

初始化

这个过程从种群中的一群个体开始，每个个体都是待解决问(原创www.isoyu.com版权)题的候选解。

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

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

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

群体、染色体和基因

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

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

选择操作

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

交叉操作

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

比如下图的交集是3:

父母在交集之前交换基因，从而产生后代。

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

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

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

突变操作

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

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

终止

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

案例实现

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

这个迭代过程的伪代码:

开始
Java中的实例实现

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