遗传算法原理

一、遗传算法简介

遗传算法是进化算法的一个分支. 它将达尔文的进化理论搬进了计算机.
科学定义如下：
**遗传算法（Genetic Algorithm, GA）**起源于对生物系统所进行的计算机模拟研究。它是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法，借鉴了达尔文的进化论和孟德尔的遗传学说。其本质是一种高效、并行、全局搜索的方法，能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最佳解。
相关术语：
基因型、表现型、进化、适应度、选择、复制、交叉、变异、编码、解码、个体、种群。

二、“袋鼠跳”问题

可以把遗传算法的过程看作是一个在多元函数里面求最优解的过程。可以这样想象，这个多维曲面里面有数不清的“山峰”，而这些山峰所对应的就是局部最优解。而其中也会有一个“山峰”的海拔最高的，那么这个就是全局最优解。而遗传算法的任务就是尽量爬到最高峰，而不是陷落在一些小山峰。
这样则可以设想所得到的每一个解就是一只袋鼠，我们希望它们不断的向着更高处跳去，直到跳到最高的山峰。所以求最大值的过程就转化成一个“袋鼠跳”的过程。
几种袋鼠跳的方式：

爬山法（最速上升爬山法）
从搜索空间中随机产生邻近的点，从中选择对应解最优的个体，替换原来的个体，不断重复上述过程。这种方式常常只能收敛到离开初始位置比较近的局部最优解上面。对于存在很多局部最优点的问题，通过一个简单的迭代找出全局最优解的机会非常渺茫。
模拟退火
这个方法来自金属热加工过程的启发。在金属热加工过程中，当金属的温度超过它的熔点（Melting Point）时，原子就会激烈地随机运动。与所有的其它的物理系统相类似，原子的这种运动趋向于寻找其能量的极小状态。在这个能量的变迁过程中，开始时，温度非常高，使得原子具有很高的能量。随着温度不断降低，金属逐渐冷却，金属中的原子的能量就越来越小，最后达到所有可能的最低点。利用模拟退火的时候，让算法从较大的跳跃开始，使到它有足够的“能量”逃离可能“路过”的局部最优解而不至于限制在其中，当它停在全局最优解附近的时候，逐渐的减小跳跃量，以便使其“落脚 ”到全局最优解上。（在模拟退火中，袋鼠喝醉了，而且随机地大跳跃了很长时间。运气好的话，它从一个山峰跳过山谷，到了另外一个更高的山峰上。但最后，它渐渐清醒了并朝着它所在的峰顶跳去。）
遗传算法
模拟物竞天择的生物进化过程，通过维护一个潜在解的群体执行了多方向的搜索，并支持这些方向上的信息构成和交换。是以面为单位的搜索，比以点为单位的搜索，更能发现全局最优解。（在遗传算法中，有很多袋鼠，它们降落到喜玛拉雅山脉的任意地方。这些袋鼠并不知道它们的任务是寻找珠穆朗玛峰。但每过几年，就在一些海拔高度较低的地方射杀一些袋鼠，并希望存活下来的袋鼠是多产的，在它们所处的地方生儿育女。）（或者换个说法。从前，有一大群袋鼠，它们被莫名其妙的零散地遗弃于喜马拉雅山脉。于是只好在那里艰苦的生活。海拔低的地方弥漫着一种无色无味的毒气，海拔越高毒气越稀薄。可是可怜的袋鼠们对此全然不觉，还是习惯于活蹦乱跳。于是，不断有袋鼠死于海拔较低的地方，而越是在海拔高的袋鼠越是能活得更久，也越有机会生儿育女。就这样经过许多年，这些袋鼠们竟然都不自觉地聚拢到了一个个的山峰上，可是在所有的袋鼠中，只有聚拢到珠穆朗玛峰的袋鼠被带回了美丽的澳洲。）

三、遗传算法的实现

遗传算法的实现过程实际上就像自然界的进化过程那样。

首先寻找一种对问题潜在解进行“数字化”编码的方案。（建立表现型和基因型的映射关系）
然后用随机数初始化一个种群（那么第一批袋鼠就被随意地分散在山脉上），种群里面的个体就是这些数字化的编码。
接下来，通过适当的解码过程之后（得到袋鼠的位置坐标），用适应性函数对每一个基因个体作一次适应度评估（袋鼠爬得越高，越是受我们的喜爱，所以适应度相应越高）。
用选择函数按照某种规定择优选择（我们要每隔一段时间，在山上射杀一些所在海拔较低的袋鼠，以保证袋鼠总体数目持平。）。
让个体基因变异（让袋鼠随机地跳一跳）。
然后产生子代（希望存活下来的袋鼠是多产的，并在那里生儿育女）。

遗传算法并不保证你能获得问题的最优解，但是使用遗传算法的最大优点在于你不必去了解和操心如何去“找”最优解。（你不必去指导袋鼠向那边跳，跳多远。）而只要简单的“否定”一些表现不好的个体就行了。（把那些总是爱走下坡路的袋鼠射杀，这就是遗传算法的精粹！）
一般步骤如下：

开始循环直至找到满意的解。
1.评估每条染色体所对应个体的适应度。
2.遵照适应度越高，选择概率越大的原则，从种群中选择两个个体作为父方和母方。
3.抽取父母双方的染色体，进行交叉，产生子代。
4.对子代的染色体进行变异。
5.重复2，3，4步骤，直到新种群的产生。
结束循环。

在这里插入图片描述
下面具体介绍遗传算法过程。

1.遗传算法编码

1）二进制编码

假设人类染色体目前只有“0”，“1”两种碱基，我们也用一条链条把他们有序的串连在一起，因为每一个单位都能表现出 1 bit的信息量，所以一条足够长的染色体就能为我们勾勒出一个个体的所有特征。
染色体大致结构为：
010010011011011110111110
上面的编码方式虽然简单直观，但明显地，当个体特征比较复杂的时候，需要大量的编码才能精确地描述，相应的解码过程（类似于生物学中的DNA翻译过程，就是把基因型映射到表现型的过程。）将过分繁复。

2）浮点数编码

为改善遗传算法的计算复杂性、提高运算效率，提出了浮点数编码。染色体大致如下：
1.2 –3.3 – 2.0 –5.4 – 2.7 – 4.3

3）符号编码（略）

那么利用这两种编码方式来对什么编码呢？
因为编码的目的是建立表现型到基因型的映射关系，而表现型一般就被理解为个体的特征。考虑到袋鼠对当前问题的“个体特征”（也就是对跳的结果有影响的特征）是袋鼠的位置，具体来说就是横坐标。
那么如何用编码来表现出袋鼠的横坐标呢？
由于横坐标是一个实数，即对这个实数编码。对于二进制编码方式来说，编码会比较复杂，而对于浮点数编码方式来说，则仅仅需要一个浮点数而已。
以二进制编码为例，那么如何建立二进制数到一个实数的映射？
比如求解如下图所示的一元函数最大值问题：
在这里插入图片描述
明显地，一定长度的二进制编码序列，只能表示一定精度的浮点数。譬如我们要求解精确到六位小数，由于区间长度为2 – (-1) = 3 ,为了保证精度要求，至少把区间[-1,2]分为3 × 106等份。又因为
$2097152=2^{21}<3*10^6<2^{22}=4194304$
所以编码的二进制串至少需要22位。
把一个二进制串（b0,b1,…bn)转化为区间里面对应的实数值通过下面两个步骤。
（1）将一个二进制串代表的二进制数转化为10进制数：
$(b_0...b_{20}b_{21})_2=(\sum_{i=0}^{21} b_i*2^i)_{10}=x^t$
（2）对应区间内的实数:
$x=-1+x^t\frac{(2-(-1))}{2^{22}-1}$
（可类比模数转换）
例如一个二进制串<1000101110110101000111>表示实数值0.637197。
$x^t=(1000101110110101000111)_2=2288967$
$x=-1+2288967\frac{3}{2^{22}-1}=0.637197$
二进制串<0000000000000000000000>和<1111111111111111111111>则分别表示区间的两个端点值-1和2。

2.物竞天择——适应性评分与选择函数

1）物竞——适应度函数

自然界生物竞争过程往往包含两个方面：生物相互间的搏斗与及生物与客观环境的搏斗过程。
但当前问题中，袋鼠并不需要互相搏斗以争取生存的权利。它们的生死存亡更多是取决于人的判断。
衡量哪只袋鼠该杀，哪只袋鼠不该杀，需要一个衡量的标准，当前条件下即袋鼠所在的海拔高度。（因为你单纯地希望袋鼠爬得越高越好。）所以我们直接用袋鼠的海拔高度作为它们的适应性评分。即适应度函数直接返回函数值就行了。
在这里插入图片描述
如果这个曲线上任一点的 y 值是 pred 的话, 我们的 fitness 就是下面这样:

def get_fitness(pred):return pred

2）天择——选择函数

自然界中，越适应的个体就越有可能繁殖后代。但是也不能说适应度越高的就肯定后代越多，只能是从概率上来说更多。（毕竟有些所处海拔高度较低的袋鼠很幸运，逃过了你的眼睛。）那么我们怎么来建立这种概率关系呢？下面我们介绍一种常用的选择方法――轮盘赌（Roulette Wheel Selection）选择法。
比如我们有5条染色体，他们所对应的适应度评分分别为：5，7，10，13，15。
所以累计总适应度为：5+7+10+13+15=50。
所以各个个体被选中的概率为：

5/50=10%
7/50=14%
10/50=20%
13/50=26%
15/50=30%

可以想象一下，我们转动轮盘，轮盘停下来的时候，指针会随机地指向某一个个体所代表的区域，那么非常幸运地，这个个体被选中了。（很明显，适应度评分越高的个体被选中的概率越大。）
精英选择机制

3.遗传变异――基因重组（交叉）与基因突变

这两个步骤就是使得子代不同于父代的根本原因（注意，我没有说是子代优于父代，只有经过自然的选择后，才会出现子代优于父代的倾向）。对于这两种遗传操作，二进制编码和浮点型编码在处理上有很大的差异，其中二进制编码的遗传操作过程，比较类似于自然界里面的过程，下面将分开讲述。

1）基因重组/交叉(recombination/crossover)

a) 二进制编码

二进制编码的基因交换过程非常类似高中生物中所讲的同源染色体的联会过程――随机把其中几个位于同一位置的编码进行交换，产生新的个体。
在这里插入图片描述

b) 浮点数编码

如果一条基因中含有多个浮点数编码，那么也可以用跟上面类似的方法进行基因交叉，不同的是进行交叉的基本单位不是二进制码，而是浮点数。
而如果对于单个浮点数的基因交叉，就有其它不同的重组方式了，比如中间重组：随机产生就能得到介于父代基因编码值和母代基因编码值之间的值作为子代基因编码的值。比如5.5和6交叉，产生5.7，5.6。

考虑到“袋鼠跳”问题的具体情况――袋鼠的个体特征仅仅表现为它所处的位置。可以想象，同一个位置的袋鼠的基因是完全相同的，而两条相同的基因进行交叉后，相当于什么都没有做，所以我们不打算在这个例子里面使用交叉这一个遗传操作步骤。（当然硬要这个操作步骤也不是不行的，你可以把两只异地的袋鼠捉到一起，让它们交配，然后产生子代，再把它们送到它们应该到的地方。）

2）基因突变(Mutation)

a) 二进制编码

基因突变过程：基因突变是染色体的某一个位点上基因的改变。基因突变使一个基因变成它的等位基因，并且通常会引起一定的表现型变化。正如上面所说，二进制编码的遗传操作过程和生物学中的过程非常相类似，基因串上的“ 0”或“ 1”有一定几率变成与之相反的“ 1”或“ 0”。例如下面这串二进制编码：

101101001011001

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

001101011011001

b) 浮点型编码

另一种使用进化理论的优化模式-**进化策略 (Evolution Strategy)**即采用实数编码。浮点数编码不能采用二进制编码中简单的0-1变换，这里考虑变异强度的概念。简单来说, 我们将爸妈遗传下来的值看做是正态分布的平均值, 再在这个平均值上附加一个标准差, 我们就能用正态分布产生一个相近的数了. 比如在这个8.8位置上的变异强度为1, 我们就按照1的标准差和8.8的均值产生一个离8.8的比较近的数, 比如8.7. 然后对宝宝每一位上的值进行同样的操作. 就能产生稍微不同的宝宝 DNA 啦. 所以, 变异强度也可以被当成一组遗传信息从爸妈的 DNA 里遗传下来. 甚至遗传给宝宝的变异强度基因也能变异. 进化策略的玩法也能多种多样。
即，浮点型编码的基因突变过程可以看作是对原来的浮点数增加或者减少一个小随机数。比如原来的浮点数串如下：

1.2,3.4,5.1, 6.0, 4.5

变异后，可能得到如下的浮点数串：

1.3,3.1,4.9, 6.3, 4.4

也就是说，传统的 ES DNA 形式分两种, 它有两条 DNA. 一个 DNA 是控制数值的, 第二个 DNA 是控制这个数值的变异强度. 比如一个问题有4个变量. 那一个 DNA 中就有4个位置存放这4个变量的值 (这就是我们要得到的答案值). 第二个 DNA 中就存放4个变量的变动幅度值.

DNA1=1.23, -0.13, 2.35, 112.5 可以理解为4个正态分布的4个平均值.
DNA2=0.1, 2.44, 5.112, 2.144 可以理解为4个正态分布的4个标准差.

所以这两条 DNA 都需要被 crossover 和 mutate.
采用这种方法，可以有两种遗传性系被继承给后代, 一种是记录所有位置的均值, 一种是记录这个均值的变异强度, 有了这套体系, 我们就能更加轻松自在的在实数区间上进行变异了. 这种思路甚至还能被用在神经网络的参数优化上, 因为这些参数本来就是一些实数.。

当然，这个小随机数也有大小之分，我们一般管它叫“步长”。（想想“袋鼠跳”问题，袋鼠跳的长短就是这个步长。）一般来说步长越大，开始时进化的速度会比较快，但是后来比较难收敛到精确的点上。而小步长却能较精确的收敛到一个点上。所以很多时候为了加快遗传算法的进化速度，而又能保证后期能够比较精确地收敛到最优解上面，会采取动态改变步长的方法。其实这个过程与前面介绍的模拟退火过程比较相类似。

到此为止，基因编码，基因适应度评估，基因选择，基因变异都一一实现了，剩下来的就是把这些遗传过程的“零件”装配起来写成代码了。

四、微生物遗传算法（Microbial GA）

遗传算法中有一点不得不提的是如何有效保留好的父母 (Elitism), 让好的父母不会消失掉. 这也是永远都给自己留条后路的意思. Microbial GA 就是一个很好的保留 Elitism 的算法. 一句话来概括: 在袋子里抽两个球, 对比两个球, 把球大的放回袋子里, 把球小的变一下再放回袋子里, 这样在这次选着中, 大球不会被改变任何东西, 就被放回了袋子, 当作下一代的一部分.
在这里插入图片描述
我们有一些 population, 每次在进化的时候, 我们会从这个 pop 中随机抽 2 个 DNA 出来, 然后对比一下他们的 fitness, 我们将 fitness 高的定义成 winner, 反之是 loser. 我们不会去动任何 winner 的 DNA, 要动手脚的只有这个 loser, 比如我们将 winner 的一部分 DNA crossover 去 loser 那, 期望 loser 有了 winner 的这一部分基因能变好一点. 然后 loser 再通过一部分几率 mutate 一下. 动完手脚后将 winner 和 loser 一同放回 pop 中.