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

本文主要是介绍零基础学启发式算法（5）-遗传算法 (Genetic Algorithm)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

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

gene:基因

chromosome: 染色体

population:种群

crossover:交叉

mutation:变异

selection:选择

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

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

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

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

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

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

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

对于如下一个示例：

指标 \ 个体	x1	x2	x3	x4	x5	x6
适应度 (F)	100	60	60	40	30	20
概率 (P)	0.322	0.194	0.194	0.129	0.097	0.064
累积概率 (CP)	0.322	0.516	0.71	0.839	0.936	1

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

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

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

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

基本位变异（Simple Mutation）：对个体编码串中以变异概率、随机指定的某一位或某几位仅因座上的值做变异运算。
均匀变异（Uniform Mutation）：分别用符合某一范围内均匀分布的随机数，以某一较小的概率来替换个体编码串中各个基因座上的原有基因值。（特别适用于在算法的初级运行阶段）
边界变异（Boundary Mutation）：随机的取基因座上的两个对应边界基因值之一去替代原有基因值。特别适用于最优点位于或接近于可行解的边界时的一类问题。
非均匀变异：对原有的基因值做一随机扰动，以扰动后的结果作为变异后的新基因值。对每个基因座都以相同的概率进行变异运算之后，相当于整个解向量在解空间中作了一次轻微的变动。
高斯近似变异：进行变异操作时用符号均值为Ｐ的平均值，方差为P**2的正态分布的一个随机数来替换原有的基因值。