每日一博 | 遗传算法如何模拟大自然的进化？

达尔文：物竞天择，适者生存。

遗传算法概述

遗传算法（Genetic Algorithm，GA）的算法思想来源于达尔文的进化论学说和Mendel的遗传理论，本质是模拟种群个体不断进化以逐渐适应环境的过程。遗传算法通过自然选择、交叉、变异等遗传操作模拟种群进化过程，使种群中个体的优良基因得以保留，提高个体的适应能力，进而不断增强对环境的适应能力。见下表：

从上表中，我们可以看到遗传算法是以染色体形式对问题的解进行描述，通过对编码串类似自然进化的遗传操作，来完成新个体的产生。当新个体产生后，我们就可以根据个体的适应值，遵循自然选择法则，适者生存来选取优秀个体再次进化，直到进化完成。

其中，遗传算法的流程图如下：

在算法初始化时，首先随机产生一批初始种群，根据适应度函数公式计算种群中各个染色体的适应度值；进一步，按照适者生存、优胜劣汰的法则，选择种群中的个体进行复制、交叉、变异的遗传操作产生出子代染色体，个体适应度越大被选择进行遗传操作的概率越高，从而将种群中的优良基因进行保留同时适应度较差的个体将逐渐被淘汰；最后，进化多代后达到算法终止条件，算法收敛到某个对环境适应性最好的染色体上，这个染色体对应的编码也就是该问题的最优解。

遗传算法具体实现

根据上述流程图我们来一步一步理解下：

确定实际问题参数

首先，我们假如问题是找出下式子的最大值：

很显然，在该范围内存在x=0时，f(x)=1最大。如下图:

至此，我们已经确定了问题的参数，即在[-1,1]上找出f(x)的最大值。

对参数进行编码

采用二进制编码，将某个变量值代表的个体表示为一个{0,1}二进制串。串长取决于求解的精度。如果确定求解精度到3位小数，由于区间长度为1-(-1)=2，必须将区间[-1，1]分为2×10^3等份。因为

所以编码的二进制串长至少需要11位。二进制串转化为十进制：

例如,s=<01000110000>,x’=560; 得x=-0.453. 则 <00000000000>与<11111111111>表示区间的两个端点-1和1。至此，我们对该问题进行了二进制串编码。

初始化种群

一个二进制串叫做一个个体(individual)。有若干个个体组成个体的集合，称为种群(population)，种群中含有的个体的数量叫做种群的规模(population size)。随机生成初始种群：

评价群体

要评价群体，就得必须有一个评价标准，遗传算法是根据个体的适应值进行评价个体是否进入下一代的。很显然这里的适应值函数就是我们的目标函数f(x)，直接将目标函数作为适应值函数。有了适应值函数，可以对初始种群进行评估。

停止条件

在进化算法中，常见的进化停止算法有三种：

• 设置进化代数，当种群进化N代之后，进化停止，选出适应值最高的个体，该个体即是最优解。
• 设置评价次数，当种群进化过程中的评价次数达到M后，进化结束，输出适应值最高个体。
• 种群收敛，如果种群收敛，则输出最优个体，进化结束。当然，如果没达到进化停止的条件，则对种群进行遗传操作，来产生新个体。

遗传操作

遗传操作一般分为三种：交叉，变异，复制

• 交叉：两个个体随机以某个点为交叉点进行交叉点后的基因互换。如下图，两条染色体将第四个基因后面的基因互换：
• 变异：在某个基因上随机选出一个变异位置，将该位置上的基因进行随机互换。如下图选择第一个基因将 0变异成为 1：
• 复制：
  复制就是将优秀的个体，原封不动的复制到下一代种群中，以保存优秀基因。这里出现了一个问题：选择哪些基因进行遗传操作呢？

适者生存

和自然进化一样在选择的时候一般按照一个原则：适应值高的存活的概率大，即选中进行遗传操作的概率大。一般有以下几个方法进行选择：

• 轮盘赌选择法 ( Roulette Wheel Selection)：利用各个个体适应度所占比例的大小决定其子孙保留的可能性。
• 锦标赛选择法（ tournament selection）：每次随机选取几个个体之中适应度最高的一个个体遗传到下一代群体中，重复M次.
• 随机遍历选择法：像轮盘赌一样计算选择概率，然后根据指针等距离地选择个体。 这样，适应值高的个体存活的概率大，进行遗传操作的概率高，产生后代的机会就大，符合自然进化的选择方法。

在进行遗传操作后，在保证种群大小不变的情况下进行淘汰适应值低的个体。然后进行下一代进化。直至进化结束，产生出最优个体为止。

♥点个赞再走呗♥