遗传算法（Genetic Algorithm，GA）最早是由美国的 John holland于20世纪70年代提出，该算法是用于解决最优化问题的一种搜索算法。它是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，通过数学的方式，利用计算机仿真运算，将问题的求解过程转换成类似生物进化中的染色体基因的交叉、变异等过程。其本质是一种高效、并行、全局搜索的方法，能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最佳解。

  遗传算法是用来解决最优化问题的，下面以求一个二元函数在 x∈[−3,3]，y∈[−3,3] 范围里的最大值为例子来详细讲解遗传算法的每一步。选取的二元函数为：

  将函数可视化，可视化代码和运行结果如下：

   可以很容易发现函数在这个局部的最大值大概在当x ≈ 0 , y ≈ 1.5 时，函数值取得最大值，而这里的 x , y 的取值就是我们最后想要得到的结果。

   为了更能方便理解遗传算法，这里需要引进几组概念。

   遗传算法是受进化理论启发而形成的。进化是由种群为单位的，种群在生物学上是指在一定空间范围内同时生活着的同种生物的全部个体。显然要想理解种群的概念，又先得理解个体的概念。在遗传算法里，个体通常为某个问题的一个解，并且该解在计算机中被编码为一个向量。例如，上面的例子中要求最大值，所以该问题的解为一组可能的 ( x , y ) 的取值。比如( x = 2.1 , y = 0.8 ) , ( x = − 1.5 , y = 2.3 ) . . . 就是求最大值问题的一个可能解，也就是遗传算法里的个体，把这样的一组一组的可能解的集合就叫做种群。比如在这个问题中设置100个这样的 x , y 的可能的取值对，那么这100个个体就构成了种群。

   在上面个体概念里提到个体（也就是一组可能解）在计算机程序中被编码为一个向量表示，而在我们这个问题中，个体是x , y 的取值，是两个实数，所以问题就可以转化为如何将实数编码为一个向量表示，编码是为了方便后续操作（交叉和变异）。在计算机中，将不同的实数用二进制串来表示就完成了编码，解码即为编码的逆行为。将个体（可能解）编码后的二进制串叫做染色体，染色体（或者有人叫DNA）就是个体（可能解）的二进制编码表示。   遗传算法中每一条染色体，对应着遗传算法的一个解决方案，一般用适应性函数（fitness function）来衡量这个解决方案的优劣。所以从一个基因组到其解的适应度形成一个映射，可以把遗传算法的过程看作是一个在多元函数里面求最优解的过程。

   遗传算法是在得到一个种群后根据适者生存规则把优秀的个体保存下来，同时淘汰掉那些不适应环境的个体。那么，如何评价一个个体对环境的适应度？以求解上述函数最大值为例，这个衡量的标准比较容易制定：函数值的大小，即适应度函数直接返回函数值就行了。即直接用可能解（个体）对应的函数的函数值的大小来评估，这样可能解对应的函数值越大越有可能被保留下来。其求解函数最大值的python代码如下：

pred是将可能解带入函数F中得到的预测值，因为后面的选择过程需要根据个体适应度确定每个个体被保留下来的概率，而概率不能是负值，所以所以最后加上了一个很小的正数。有了求最大值的适应度函数，求最小值适应度函数也就容易了，python代码如下:

.    有了评估的适应度函数，则可以根据适者生存法则将优秀者保留下来了。选择是根据新个体的适应度进行，但同时不意味着完全以适应度高低为导向（选择 k 个适应度最高的个体，容易陷入局部最优解，因为单纯选择适应度高的个体将可能导致算法快速收敛到局部最优解而非全局最优解，我们称之为早熟）作为折中，遗传算法依据原则：适应度越高，被选择的机会越高，而适应度低的，被选择的机会就低。常用的选择方法――轮盘赌（Roulette Wheel Selection）选择法。比如有5条染色体，他们所对应的适应度评分分别为：5，7，10，13，15，所以所以累计总适应度为： 则各个个体被选中的概率分别为： 可以想象一下，转动轮盘，轮盘停下来的时候，指针会随机地指向某一个个体所代表的区域，很明显，适应度评分越高的个体被选中的概率越大。

   遗传算法的选择在python中使用choice实现，np.random.choice函数是numpy库中用于生成随机样本的函数。它可以从一个给定的数组中随机抽取样本。该函数有三个必选参数: a、Size、p。其中a为数组，size为抽取样本的个数，p为每个元素被抽到的概率。还有其他可选参数如replace、weights、random_state等。代码如下：

其中，参数p描述了从np.arange(POP_SIZE)里选择每一个元素的概率，概率越高约有可能被选中，最后返回被选中的个体即可。

   通过选择得到了当前看来“还不错的基因”，但是这并不是最好的基因，需要通过繁殖后代（包含有交叉+变异过程）来产生比当前更好的基因，但是繁殖后代并不能保证每个后代个体的基因都比上一代优秀，这时需要继续通过选择过程来让试应环境的个体保留下来，从而完成进化，不断迭代上面这个过程种群中的个体就会一步一步地进化。具体地繁殖后代过程包括交叉和变异两步。

   交叉： 二进制编码的基因交换过程非常类似高中生物中所讲的同源染色体的联会过程――随机把其中几个位于同一位置的编码进行交换，产生新的个体。每一个个体是由父亲和母亲两个个体繁殖产生，子代个体的DNA（二进制串）获得了一半父亲的DNA，一半母亲的DNA，但是这里的一半并不是真正的一半，这个位置叫做交配点，是随机产生的，可以是染色体的任意位置。

   变异： 通过交叉子代获得了一半来自父亲一半来自母亲的DNA，但是子代自身可能发生变异，使得其DNA即不来自父亲，也不来自母亲，在某个位置上发生随机改变，通常就是改变DNA的一个二进制位（0变到1，或者1变到0）。例如下面这串二进制编码：

经过基因突变后，可能变成以下这串新的编码：

   需要说明的是交叉和变异不是必然发生，而是有一定概率发生。先考虑交叉，最坏情况，交叉产生的子代的DNA都比父代要差（这样算法有可能朝着优化的反方向进行，不收敛），如果交叉是有一定概率不发生，那么就能保证子代有一部分基因和当前这一代基因水平一样；而变异本质上是让算法跳出局部最优解，如果变异时常发生，或发生概率太大，那么算法到了最优解时还会不稳定。交叉概率，范围一般是0.6~1，突变常数（又称为变异概率），通常是0.1或者更小。对于这两个概率，我们一般管叫“步长”。一般来说步长越大，开始时进化的速度会比较快，但是后来比较难收敛到精确的点上。而小步长却能较精确的收敛到一个点上。所以很多时候为了加快遗传算法的进化速度，而又能保证后期能够比较精确地收敛到最优解上面，会采取动态改变步长的方法。这个过程与前面介绍的模拟退火过程比较相类似。

交叉和变异的实现代码如下：