遗传算法GA | 彩潭有鲤的札记

type

status

date

slug

summary

原理

以求二元函数为例：

种群和个体的概念

遗传算法启发自进化理论，而我们知道进化是由种群为单位的，种群是什么呢？

维基百科上解释为:在生物学上，是在一定空间范围内同时生活着的同种生物的全部个体。

显然要想理解种群的概念，又先得理解个体的概念。在遗传算法里，个体通常为某个问题的一个解,并且该解在计算机中被编码为一个向量表示!

我们的例子中要求3*(1-x)**2*np.exp(-(x**2)-(y+1)**2)- 10*(x/5 - x**3 - y**5)*np.exp(-x**2-y**2)- 1/3**np.exp(-(x+1)**2 - y**2)最大值,所以该问题的解为一组可能的( )的取值。比如( )，( ) . . .就是求最大值问题的一个可能解,也就是遗传算法里的个体，把这样的一组一组的可能解的集合就叫做种群，比如在这个问题中设置100个这样的的可能的取值对,这100个个体就构成了种群。

编码、解码与染色体的概念

在上面个体概念里提到个体(也就是一组可能解)在计算机程序中被编码为一个向量表示，而在我们这个问题中，个体是的取值,是两个实数,所以问题就可以转化为如何将实数编码为一个向量表示,可能有些朋友有疑惑,实数在计算机里不是可以直接存储吗，为什么需要编码呢？这里编码是为了后续操作(交叉和变异)的方便。

生物的DNA有四种碱基对，分别是ACGT。 DNA的编码可以看作是DNA上碱基对的不同排列,不同的排列使得基因的表现出来的性状也不同(单眼皮双眼皮)。在计算机中，我们可以模仿这种编码，但是碱基对的种类只有两种，分别是0和1。只要我们能够将不同的实数表示成不同的0，1二进制串表示就完成了编码，也就是说其实我们并不需要去了解一个实数对应的二进制具体是多少，我们只需要保证有一个映射:

，(x is decimal systemy is binary system)

能够将十进制的数编码为二进制即可，至于这个映射是什么，其实可以不必关心。将个体（可能解）编码后的二进制串叫做染色体，染色体（DNA）就是个体（可能解）的二进制编码表示。为什么可以不必关心映射呢？因为其实我们在程序中操纵的都是二进制串，而二进制串生成时可以随机生成，如：

实际上是没有需求需要将一个十进制数转化为一个二进制数，而在最后我们肯定要将编码后的二进制串转换为我们理解的十进制串，所以我们需要的是的逆映射，也就是将二进制转化为十进制，这个过程叫做解码: 首先我们限制二进制串的长度为10（长度自己指定即可，越长精度越高，例如我们有一个二进制串（在程序中用数组存储即可）:

这个二进制串如何转化为实数呢？不要忘记我们的这个限制，我们目标是求一个逆映射将这个二进制串映射到即可，为了更一般化我们将的取值范围用一个变量表示：

为将二进制串映射到指定范围，首先先将二进制串按权展开，将二进制数转化为十进制数，我们有，然后将转换后的实数压缩到之间的一个小数，。通过以上这些步骤所有二进制串表示都可以转换为之间的小数，现在只需要将区间内的数映射到我们要的区间即可。假设区间内的数称为num:

现在再来看看编码过程不难看出上面我们的DNA（二进制串）长为10，10位二进制可以表示种不同的状态，可以看成是将最后要转化为的十进制区间切分成份，显而易见，如果我们增加二进制串的长度，那么我们对区间的切分可以更加精细，转化后的十进制解也更加精确。

例如：十位二进制全1按权展开为，最后映射到区间时为，而按权展开为，；如果我们将实数编码为位二进制，（12个1）最后转化为，而（前面11个1）按权展开为，。，可以看出用10位二进制编码划分区间后，每个二进制状态改变对应的实数大约改变，而用12位二进制编码这个数字下降到，所以DNA长度越长，解码为10进制的实数越精确。 解码过程:

这里我设置DNA_SIZE=24（一个实数DNA长度），两个实数一共用48位二进制编码，我同时将和编码到同一个48位的二进制串里，每一个变量用24位表示，奇数24列为的编码表示，偶数24列为的编码表示。

适应度和选择

我们已经得到了一个种群，现在要根据适者生存规则把优秀的个体保存下来，同时淘汰掉那些不适应环境的个体。现在摆在我们面前的问题是如何评价一个个体对环境的适应度？在我们的求最大值的问题中可以直接用可能解（个体）对应的函数的函数值的大小来评估，这样可能解对应的函数值越大越有可能被保留下来，以求解上面定义的函数F的最大值为例：

pred是将可能解带入函数F中得到的预测值，因为后面的选择过程需要根据个体适应度确定每个个体被保留下来的概率，而概率不能是负值，所以减去预测中的最小值把适应度值的最小区间提升到从0开始，但是如果适应度为0，其对应的概率也为0，表示该个体不可能在选择中保留下来，这不符合算法思想，遗传算法不绝对否定谁也不绝对肯定谁，所以最后加上了一个很小的正数。有了求最大值的适应度函数求最小值适应度函数也就容易了：

因为根据适者生存规则在求最小值问题上，函数值越小的可能解对应的适应度应该越大，同时适应度也不能为负值，先将适应度减去最大预测值，将适应度可能取值区间压缩为[np.min(pred)−np.max(pred),0] ，然后添加个负号将适应度变为正数，同理为了不出现0，最后在加上一个很小的正数。

有了评估的适应度函数，下面可以根据适者生存法则将优秀者保留下来了。选择则是根据新个体的适应度进行，但同时不意味着完全以适应度高低为导向（选择top k个适应度最高的个体，容易陷入局部最优解），因为单纯选择适应度高的个体将可能导致算法快速收敛到局部最优解而非全局最优解，我们称之为早熟。作为折中，遗传算法依据原则：适应度越高，被选择的机会越高，而适应度低的，被选择的机会就低。

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

交叉、变异

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

具体地繁殖后代过程包括交叉和变异两步。交叉是指每一个个体是由父亲和母亲两个个体繁殖产生，子代个体的DNA（二进制串）获得了一半父亲的DNA，一半母亲的DNA，但是这里的一半并不是真正的一半，这个位置叫做交配点，是随机产生的，可以是染色体的任意位置。通过交叉子代获得了一半来自父亲一半来自母亲的DNA，但是子代自身可能发生变异，使得其DNA即不来自父亲，也不来自母亲，在某个位置上发生随机改变，通常就是改变DNA的一个二进制位（0变到1，或者1变到0）。

需要说明的是交叉和变异不是必然发生，而是有一定概率发生。先考虑交叉，最坏情况，交叉产生的子代的DNA都比父代要差（这样算法有可能朝着优化的反方向进行，不收敛），如果交叉是有一定概率不发生，那么就能保证子代有一部分基因和当前这一代基因水平一样；而变异本质上是让算法跳出局部最优解，如果变异时常发生，或发生概率太大，那么算法到了最优解时还会不稳定。交叉概率，范围一般是0.6~1，突变常数（又称为变异概率），通常是0.1或者更小。

迭代起来，让种群去进化

完整代码

调库实现GA

GA

GA输入参数

入参	默认值	意义
func	-	目标函数
n_dim	-	目标函数的维度
size_pop	50	种群规模
max_iter	200	最大迭代次数
prob_mut	0.001	变异概率
lb	-1	每个自变量的最小值
ub	1	每个自变量的最大值
constraint_eq	空元组	等式约束
constraint_ueq	空元组	不等式约束
precision	1e-7	精准度，int/float或者它们组成的列表

GA输出参数：

ga.generation_best_Y 每一代的最优函数值

ga.generation_best_X 每一代的最优函数值对应的输入值

ga.all_history_FitV 每一代的每个个体的适应度

ga.all_history_Y 每一代每个个体的函数值

ga.best_y 最优函数值

ga.best_x 最优函数值对应的输入值

GA实现整数规划

在多维优化时，想让哪个变量限制为整数，就设定 precision 为整数即可

例如，我想让我的自定义函数 demo_func 的某些变量限制为整数+浮点数（分别是隔2个，隔1个，浮点数），那么就设定precision=[2, 1, 1e-7]

说明：

当 precision 为整数时，对应的自变量会启用整数规划模式。

在整数规划模式下，变量的取值可能个数最好是，这样收敛速度快，效果好。

如果 precision 不是整数（例如是0.5）,则不会进入整数规划模式，如果还想用这个模式，那么把对应自变量乘以2，这样 precision 就是整数了

GA实现曲线拟合

GA用于旅行商问题

GA_TSP 针对TSP问题重载了 交叉(crossover)、变异(mutation) 两个算子

GA_TSP输入参数

入参	默认值	意义
func	-	目标函数
n_dim	-	城市个数
size_pop	50	种群规模
max_iter	200	最大迭代次数
prob_mut	0.001	变异概率

GA_TSP输出参数

ga.generation_best_Y 每一代的最优函数值

ga.generation_best_X 每一代的最优函数值对应的输入值

ga.all_history_FitV 每一代的每个个体的适应度

ga.all_history_Y 每一代每个个体的函数值

ga.best_y 最优函数值

ga.best_x 最优函数值对应的输入值

GA_TSP问题如何固定起点和终点

固定起点和终点要求路径不闭合（因为如果路径是闭合的，固定与不固定结果实际上是一样的）

假设你的起点和终点坐标指定为(0, 0) 和 (1, 1)，这样构建目标函数

起点和终点不参与优化。假设共有n+2个点，优化对象是中间n个点

目标函数（总距离）按实际去写。