Python智能优化：遗传算法

         遗传算法：借鉴达尔文的进化论，要求解的问题模拟成一个生物进化的过程，通过复制、交叉、变异等操作产生下一代的解，并逐步淘汰掉适应度函数值低的解。进化N代后就很有可能会进化出适应度函数值很高的个体。

首先，介绍一下几个基本概念：

种群(Population)：生物进化以群体形式进行称为种群。即为要优化的数据集。

个体：组成种群的单个生物。可理解为数据集中的一条观测。

基因 ( Gene ) ：遗传因子序列。遗传算法要求数据集的每条数据被转为二进制序列参与运算。如：原数据：5,6，二进制序列为101110

适应度：个体适应环境的能力。每一轮迭代计算的目标函数的值。

选择(遗传)：以某一概率分布挑选用于配对的个体，适应度大的容易被选中。

交叉：以某一概率相互交换某两个个体之间的部分染色体，从而产生新个体。

变异：对个体的某一个或某一些基因座上的基因值进行改变，从而产生新个体。

        假设现在要求解一个函数的最大值，如下：

如上可知，x1和x2均等于7时，函数取到最大值98。下面将用遗传算法得到这个结果：

(1) 个体编码（参见代码中函数gene_population）
      遗传算法的运算对象是表示个体的符号串，所以必须把变量 x1, x2 编码为一种符号串。通常用无符号二进制整数来表示。
       例如，某数据(表现型)x＝[ 5，6 ]转为二进制串(基因型)为X=101110 。数据集所有数据都转成二进制串后，就得到一个用于运算的种群。

 (2) 适应度汁算（参见代码中函数gene_fitness）
        种群中个体适应度的大小来评定各个个体的优劣程度，从而决定其遗传机会的大小。
        本例中，目标函数总取非负值，并且是以求函数最大值为优化目标，故可直接利用目标函数值作为个体的适应度。

(3)  选择运算（参见代码中函数gene_selected）

       或称为复制运算，把当前种群中适应度高的个体按某种规则遗传到下一代群体中。本例中，我们采用”轮盘赌“算法，每轮给每条二进制串产生一个0-1的随机数，根据二进制序列的适应度的累计概率区间来确定哪些个体复制到下一代群体中。如下图：

上图共4条二进制串，根据目标函数算出适值(适应度)及适值的占比，最后根据”轮盘赌“算法选出适值概率区间最大的3条观测进入个体配对。

(4)  交叉运算（参见代码中函数gene_cross）

       以某一概率相互交换某两个个体之间的部分染色体(二进制串)。
       本例采用单点交叉法，即每条染色体随机选择一个分割点进行交叉，如下：

图中所说新个体111101，111即7，101即5，适应度7^2+5^2=74，高于初始种群中的所有个体适应度。

(5)  变异运算（参见代码中函数gene_mutation）

      对个体的某一个或某一些基因座上的基因值按某一较小的概率进行改变。
      本例中，我们采用基本位变异的方法来进行变异运算，每条经过(5)筛选的个体，都随机选择一个变异点，进行取反操作，原来是0的变为1，1的变为0。

经过以上5步，一轮生物进化完成，看下子代种群的适应度信息：

可见，新产生的第2条个体111111的适值为98，已经达到目标函数的最大值。

     接下来，使用Python pandas包实现如上所述的遗传算法。产生数据集如下：

target为目标函数，data为如上介绍的4条数据集。算法代码如下：

bin_code函数将10进制数转为二进制，unit将两个变量值拼接为一个二进制串。

首先产生4条二进制序列的随机概率值r，用轮盘赌算法检查每个r落在了哪个个体的适值概率区间p，返回落入区间的个体。

首先打乱个体的排列，后续按照相邻的两条二进制串进行配对。for循环中如果有4条观测则循环2次，每两条进行一次配对，如有5条也配对两次，多出的一条本轮不参与配对(if条件会判断)。

随机点位，即在二进制串长度范围内，本例为6，则随机生成4个0-5的数字，将所有4条观测在随机点位上的数字取反。

本轮种群进化结束后，输出本轮最佳个体，总适应度等信息。

迭代执行上述过程，默认执行10次，下面实际运行一下：

如上，首先新建类的实例ho，调用gene_start函数执行算法，可见迭代到第8次时，遗传算法求解到目标函数的最佳值98，此时x1和x2都取7，总的适应度为198。OK，晚安！