一文搞懂什么是遗传算法Genetic Algorithm【附应用举例】

代码链接放文末。

本文参考了很多张军老师《计算智能》的第四章内容。

本文来源：https://blog.csdn.net/qq_44186838/article/details/109181453

遗传算法

1.1 遗传算法简介

1.1.1 基本原理

重温高中生物哈哈！

遗传算法（Genetic Algorithm，GA）是进化计算的一个分支，是一种模拟自然界生物进化过程的随机搜索算法。

GA思想源于自然界“自然选择”和“优胜劣汰”的进化规律，通过模拟生物进化中的自然选择和交配变异寻找问题的全局最优解。它最早由美国密歇根大学教授John H. Holland提出，现在已经广泛应用于各种工程领域的优化问题之中。

遗传算法通过比较适应值区分染色体的优劣，适应值越大的染色体越优秀。评估函数涌过来计算染色体对应的适应值。

选择算子按一定的规则对群体的染色体进行选择，得到父代种群。（一般的，越优秀的染色体被选中的次数越多。）

交配算子作用于每两个成功交配的染色体，染色体交换各自部分的基因，形成两个子代染色体。子代染色体取代父代进入新种群，而没有交配的染色体自动进入新的种群。

变异算子使得新种群进行小概率的变异。染色体发生变异的基因改变数值，经过变异的新种群替代原种群进入下一次进化。

在这里插入图片描述
下面我们再来了解几个概念。

模式：指群体中编码的某些位置具有相似结构的染色体集合。

在这里插入图片描述
Holland的模式定理提出，遗传算法的实质是通过选择、交配和变异算子对模式进行搜索，低阶、定义长度较小且平均适应值高于群体平均适应值的模式在群体中的比例将呈指数级增长。即随着进化的不断进行，较优染色体的个数将快速增加。

积木块假设

积木块：指低阶、定义长度较小且平均适应值高于群体平均适应值的模式。

积木块假设认为在遗传算法运行过程中，积木块在遗传算子的影响下能够相互结合，产生新的更加优秀的积木块，最终接近全局最优解。

1.1.2 研究进展
在这里插入图片描述
这个大致看下就可以了。

1.2 遗传算法的流程

(1) 染色体编码
目前用于染色体编码的方法有格雷码编码、字母编码、多参数交叉编码等。这里仅给出两种常见的较为简单的编码方法：二进制编码方法和浮点数编码方法。

二进制编码方法
在这里插入图片描述

二进制编码操作简单，但当你的L较大时，计算难度会增大，难以解决精度要求高的问题，因此，我们需要寻求另外的编码方法。

在这里插入图片描述
(2) 群体的初始化

一般情况下，遗传算法在群体初始化阶段采用的是随机数初始化方法。采用生成随机数的方法，对染色体的每一维变量进行初始化赋值。初始化染色体时必须注意染色体是否满足优化问题对有效解的定义。

如果在进化开始时保证初始群体已经是一定程度上的优良群体的话，将能够有效提高算法找到全局最优解的能力。

(3) 适应值评价

评估函数用于评估各个染色体的适应值，进而区分优劣。评估函数常常根据问题的优化目标来确定，比如在求解函数优化问题时，问题定义的目标函数可以作为评估函数的原型。
在遗传算法中，规定适应值越大的染色体越优。因此对于一些求解最大值的数值优化问题，我们可以直接套用问题定义的函数表达式。但是对于其他优化问题，问题定义的目标函数表达式必须经过一定的变换。

(4) 选择算子

轮盘赌选择法
在这里插入图片描述
按适应值大小切分区域大小，即适应值越大的染色体占比越大，越有可能被选中，同时由于是随机选取，也保证了适应值小的染色体也有被选中的可能。

(5) 交配算子
在染色体交配阶段，每个染色体能否进行交配由交配概率Pc（一般取值为0.4到0.99之间）决定，其具体过程为：对于每个染色体，如果Random(0, 1)小于Pc则表示该染色体可进行交配操作（其中Random(0, 1)为[0, 1]间均匀分布的随机数），否则染色体不参与交配直接复制到新种群中。

每两个按照Pc交配概率选择出来的染色体进行交配，经过交换各自的部分基因，产生两个新的子代染色体。具体操作是随机产生一个有效的交配位置，染色体交换位于该交配位置后的所有基因。

注意：因为父代是两个染色体，生成的子代也是两个染色体，故种群染色体总数N值不会改变。

(6) 变异算子

染色体的变异作用于基因之上，对于交配后新种群中染色体的每一位基因，根据变异概率Pm判断该基因是否进行变异。

如果Random(0, 1)小于Pm，则改变该基因的取值（其中Random(0, 1)为[0, 1]间均匀分布的随机数）。否则该基因不发生变异，保持不变。

在这里插入图片描述
下面给出算法基本步骤

在这里插入图片描述

如果到这里有些困惑的话，没有关系，我们来看一个实例。

在这里插入图片描述
解题如下：

在这里插入图片描述

够简单理解吧。

**1.3 遗传算法的改进 **

没有完美的算法，只有适合的算法。下文会贴出每种问题对应的多种研究，感兴趣的可以自行上网查看。

1.3.1 算子选择
在这里插入图片描述

1.3.2 参数设置

群体规模N

影响算法的搜索能力和运行效率。
若N设置较大，一次进化所覆盖的模式较多，可以保证群体的多样性，从而提高算法的搜索能力，但是由于群体中染色体的个数较多，势必增加算法的计算量，降低了算法的运行效率。
若N设置较小，虽然降低了计算量，但是同时降低了每次进化中群体包含更多较好染色体的能力。
N的设置一般为20~100。

染色体长度L

影响算法的计算量和交配变异操作的效果。
L的设置跟优化问题密切相关，一般由问题定义的解的形式和选择的编码方法决定。
对于二进制编码方法，染色体的长度L根据解的取值范围和规定精度要求选择大小。
对于浮点数编码方法，染色体的长度L 跟问题定义的解的维数D相同。
除了染色体长度一定的编码方法，Goldberg等人还提出了一种变长度染色体遗传算法Messy GA，其染色体的长度并不是固定的。

基因取值范围R

R视采用的染色体编码方案而定。
对于二进制编码方法，R ={0,1}，而对于浮点数编码方法，R与优化问题定义的解每一维变量的取值范围相同。

交配概率Pc

决定了进化过程种群参加交配的染色体平均数目。
取值一般为0.4至0.99。也可采用自适应方法调整算法运行过程中的交配概率。

变异概率Pm

增加群体进化的多样性，决定了进化过程中群体发生变异的基因平均个数。
Pm的值不宜过大。因为变异对已找到的较优解具有一定的破坏作用，如果Pm的值太大，可能会导致算法目前处于的较好的搜索状态倒退回原来较差的情况。
Pm的取值一般为0.001至0.1之间。也可采用自适应方法调整算法运行过程中的Pm值。

适应值评价

影响算法对种群的选择，恰当的评估函数应该能够对染色体的优劣做出合适的区分，保证选择机制的有效性，从而提高群体的进化能力。
评估函数的设置同优化问题的求解目标有关。
评估函数应满足较优染色体的适应值较大的规定。
为了更好地提高选择的效能，可以对评估函数做出一定的修正。
目前主要的评估函数修正方法有：线性变换；乘幂变换；指数变换等。

终止条件

决定算法何时停止运行，输出找到的最优解，采用何种终止条件，跟具体问题的应用有关。
可以使算法在达到最大进化代数时停止，最大进化代数一般可设置为100~1000，根据具体问题可对该建议值作相应的修改。
也可以通过考察找到的当前最优解是否达到误差要求来控制算法的停止。
或者是算法在持续很长的一段进化时间内所找到的最优解没有得到改善时，算法可以停止。

1.3.3 混合遗传算法

提出混合遗传算法的原因有两个，一是遗传算法存在局部搜索能力较弱的缺陷，二是当遗传算法应用到专门的领域时往往不是最佳的方法。

在这里插入图片描述
1.3.4 并行遗传算法