零基础学启发式算法（5）-遗传算法 (Genetic Algorithm)

一、遗传算法 (Genetic Algorithm, GA) 

源于达尔文的进化论，将问题的一个解当作种群中的一个个体。

gene:基因

chromosome: 染色体

population:种群

crossover:交叉

mutation:变异

selection:选择

通过多轮的“选择，交叉和变异”，选择适应度最好的个体作为问题的最优解。

1. 选择：优胜劣汰，适者生存。

2. 交叉：丰富种群，持续优化。

3. 变异：随机扰动，避免局部最优。

算法的整个流程如下所示：

二、流程

1.初始化种群

    在初始化种群时，首先对每一个个体进行编码，编码后的个体可以称之为一个染色体。一个染色体可以表示为：

        x=(p1,p2,…,pm)

    其中，m 为染色体的长度或编码的位数。初始化种群个体共 n 个，对于任意一个个体染色体的任意一位 i，随机生成一个随机数 rand∈U(0,1)，若 rand>0.5，则 pi=1，否则 pi=0。

    常用的编码方式有

• 二进制编码，

• 实值编码，

• 矩阵编码，

• 树形编码等。

    以二进制为例，对于 p∈{0,1,…,100} 中 pi=50 可以表示为：

        xi=5010=01100102

2.计算适应度

    适应度函数( Fitness Function ) f(x)用来评价个体的优劣程度，通常为问题的目标函数，对最小化优化问题 f(x)=−min∑L(y^,y)，对最大化优化问题 f(x)=max∑L(y^,y)，其中 L 为损失函数。

3.选择

    对于种群中的每个个体，计算其适应度，记第 i 个个体的适应度为 Fi=f(xi)。则个体在一次选择中被选中的概率为：

    为了保证种群的数量不变，我们需要重复 n 次选择过程，单次选择采用轮盘赌的方法。利用计算得到的被选中的概率计算每个个体的累积概率：

对于如下一个示例：

    每次选择时，随机生成 rand∈U(0,1)，当 CPi−1≤rand≤CPi 时，选择个体 xi。选择的过程如同在下图的轮盘上安装一个指针并随机旋转，每次指针停止的位置的即为选择的个体。

4.交叉

• 单点交叉：在染色体中选择一个切点，然后将其中一部分同另一个染色体的对应部分进行交换得到两个新的个体。交叉过程如下图所示：

• 多点交叉：在染色体中选择多个切点，对其任意两个切点之间部分以概率 Pc 进行交换，其中 Pc 为一个较大的值，例如 Pm=0.9。两点交叉过程如下图所示：

• 均匀交叉：染色体任意对应的位置以一定的概率进行交换得到新的个体。交叉过程如下图所示：

5. 变异

    将个体染色体编码串中的某些基因座上的基因值用该基因座上的其它等位基因来替换，从而形成新的个体。

    变异以一定的概率 Pm 发生变化，其中 Pm 为一个较小的值，例如 Pm=0.05。

以下变异算子适用于二进制编码和浮点数编码的个体：

• 基本位变异（Simple Mutation）：对个体编码串中以变异概率、随机指定的某一位或某几位仅因座上的值做变异运算。

  

• 均匀变异（Uniform Mutation）：分别用符合某一范围内均匀分布的随机数，以某一较小的概率来替换个体编码串中各个基因座上的原有基因值。（特别适用于在算法的初级运行阶段）

• 边界变异（Boundary Mutation）：随机的取基因座上的两个对应边界基因值之一去替代原有基因值。特别适用于最优点位于或接近于可行解的边界时的一类问题。

• 非均匀变异：对原有的基因值做一随机扰动，以扰动后的结果作为变异后的新基因值。对每个基因座都以相同的概率进行变异运算之后，相当于整个解向量在解空间中作了一次轻微的变动。

• 高斯近似变异：进行变异操作时用符号均值为Ｐ的平均值，方差为P**2的正态分布的一个随机数来替换原有的基因值。

对于基本的遗传算法还有多种优化方法，例如：精英主义，即将每一代中的最优解原封不动的复制到下一代中，这保证了最优解可以存活到整个算法结束。

三、例子

寻找多峰函数的最大值这个问题为例：

将(x, y)这一可能的解作为一个个体；将多峰函数的函数值f(x, y)作为个体的适应度；对(x, y)进行编码作为个体的基因；以适应度为标准不断筛选生物个体；

https://leovan.me/cn/2019/04/heuristic-algorithms/

https://learnwithpanda.com/2020/09/20/what-is-genetic-algorithm/

https://towardsdatascience.com/introduction-to-genetic-algorithms-including-example-code-e396e98d8bf3?gi=8c025ac095e1

https://www.jianshu.com/p/ae5157c26af9

https://blog.csdn.net/gzxb1995/article/details/89060839