遗传算法

智能优化算法，即现代启发式算法，其本质思想都是一样的，基本思想都是择优进化：优秀的解根据一定策略变得更好，劣质的解根据一定策略向好的发展

优化算法：

遗传算法 粒子群算法 模拟退火 蚁群算法 AOA 算术优化 鲸鱼算法 萤火虫算法 SMA 黏菌算法 HHO 哈里斯鹰算法

遗传算法的学习分两大块，算法原理以及代码逻辑，代码逻辑需要根据基于 Matlab/Python 从而去运用其中设置好的函数包

一、算法原理

算法步骤：

定义（definition):

定义解 X 的形式和适应度函数 F(X)，设置终止遗传条件，交叉率 P​**_c​与变异率 P​_m**

终止遗传条件：可以是遗传代数，可以是适应度函数条件

设置初始个体：N 个个体 X 组成一个种群 S，个体即我们希望得到的解 X，一个个体本质上其实是一个染色体 X，一个染色体含有多个基因（比如解的形式是 4 个空间坐标，那么染色体就有 12 个有序基因）

适应度评估（Fitness Evaluation） ：

对种群中的每个个体进行评估，计算其适应度值，以作为选择下一代个体的依据。计算每个个体的适应度函数 F(X)

选择（Selection）：

根据个体的适应度选择优秀的个体进行繁殖。常用的方法有轮盘赌选择、锦标赛选择、精英保留策略等

轮盘赌选择：按照 F(X_i)权重计算个体选择概率 P(X_i)， 每次从种群中按照概率选择一个个体复制，选择 N 次选择出 N 个个体组成后代

精英保留策略：从 S 中个体中适应度函数最高的 K 个组成名人堂直接保留，剩下的再进行选择 N-K 个

锦标赛选择：略

交叉（Crossover） ：

将两个父代个体的基因组合起来，生成新的个体（后代）。常见的交叉方式有单点交叉、多点交叉和均匀交叉。

选择哪些个体进行交叉？

自己拟定：可以随机选择，可以设置概率映射选择，可以选取适应度函数高的 NPc 个

个体间如何进行交叉？

自己拟定：可以染色体两两配对，也可以三个染色体一组；可以单基因交叉，也可以多基因交叉，还可以融合遗传

变异（Mutation） ：

对个体的部分基因进行随机改变，以增加种群的多样性，防止算法陷入局部最优。变异可以是对某个基因的随机修改。

选择哪些个体进行变异？

自己拟定：可以随机选择，可以设置概率映射选择，可以选取适应度函数高的 NP_m个

个体如何变异？

自己拟定：可以单基因变异也可以多基因变异

迭代遗传：

完成以上步骤后即产生了下一代，回到适应度评估的步骤，检查遗传终止条件，若停止则输出，若不停止则继续循环

注释：

• 选择、交叉、变异顺序不定，可以自定顺序

二、算法实现

我们发现定义、适应度函数评估、选择都是很好代码实现

关键在于交叉与变异，这里就要谈到编码问题了，注意！！

编码是遗传算法最难的地方

编码与解码

用一句话概括编码与解码的本质：

具体问题具体分析，编码和解码不能割裂开来看，合适即可：能在数学上说明解可以编码和解码；可以进行交叉和变异，可以写出代码就 ok

常见的编码方式：二进制编码、实数编码

二进制编码：

计算机当中的浮点数没有绝对连续的数，也没有绝对的无限小数，其实一切数都是**离散**的。

编码：

所以当我们想去表达解的范围在[1,50]时，其实是需要取出[1,50]的一串等差数列的，那么一个长度为 L 的区间范围，设置多少个数呢？

我们可以设置 2​ⁿ​个数，那么数之间的间隔（精度）为 L/2​ⁿ​ -1,所以我可以根据我希望的精度去设置 n 的大小

这 2n 个数我们就可以用 n 位数二进制去表示

解码：

先把二进制转化为十进制，用等差数列公式解码得到二进制实际对应的数

补充： 对于有些时候，我们可以对于只有一个基因的染色体，它每位的二进制表示当作它的基因，在做变异和交叉操作的时候就是对于那些 0、1 基因操作

例子：求解 xsinxcos2x-2xsin3x+3xsin4x​在[0,50]的最大值

​​

取 n=20，L=50 进行编码，这就是解只有一个基因的情况，可以把这个基因当作整个染色体，其中的 0,1 编码当作另一种形式的基因，对于这些基因进行变异（0 变 1，1 变 0）、交叉操作

实数编码：

对于大多数数值型变量都可以选择实数编码（也叫浮点数编码）

这种情况下我们必须说：实数编码的交叉与变异操作就一定是对于基因去操作，而不会像上面一样对 0，1 操作

那么实数编码如何变异呢？

1. 常规变异（Gaussian Mutation） ：

   • 在这种方法中，从一个高斯分布中生成一个随机数，并将这个随机数加到被变异个体的基因值上。具体步骤如下：

x′=x+N(0,σ)

x 是当前基因值，x' 是变异后的基因值， N(0, \sigma) 是均值为0、标准差为 \sigma 的高斯分布的随机数。

2. 均匀变异（Uniform Mutation） ：

• 在均匀变异中，可以在一个指定范围内对基因进行随机调整。具体方法是随机选择一个范围并使基因值在这个范围内重新取值：

x′=x+randrange(−d,d)

d 是变异的幅度，randrange(-d, d)表示在 -d 到 d 之间随机取值

3. 多项式变异（Polynomial Mutation） ：

• 该方法通过多项式分布来决定变异的幅度，优点在于可以产生更平滑的变异效果。方法较为复杂，主要分为以下几步：

  1. 计算变异概率，决定是否进行变异。
  2. 根据多项式分布决定变异幅度。

例子： 在旅行商问题中，我们的解的形式为{1,2,3……,10}的某个排序，如何使用实数编码去表示排序？

在（0,1)这个区间随机生成一个有序数列{x1,x2,x3……,x10}，对生成的数列进行从小到大的排序，其下标的序列正好可以表示一种排序，这个解相当于有 10 个基因

比如我生成了{0.23,0.48,0.19,0.96,0.37,0.54,0,92,0.29,0,87,0.40},则表示的排序即为{2,5,1,10,4,7,9,3,8,6}

交叉与变异都可以建立对实数编码进行操作

其他特殊的编码方式：符号编码、排列编码法、复数编码、DNA 编码、多参数级联编码（个人觉得极其鸡肋，都可以用二进制/实数编码代替）

下面介绍一些遗传算法实现过程中需要考虑的问题：

异常处理

有两个地方需要注意数值溢出：变异和适应度函数，所以可以设置异常处理模块

• 变异需要限制解的变异范围
• 适应度函数有时候可能会趋于过大值，也需要对解有一定限制

动态交叉、变异

随着遗传代数，调整交叉率与变异率或者交叉变异方式

并行计算

为加速程序运行可以加入并行计算，将任务分配给多个 CPU 核心而不是只调用一个核心

Python 中可以使用以下库来实现并行计算：

1. ​​multiprocessing​​：这是 Python 标准库中用于并行计算的一个模块。
2. ​​joblib​​：一个第三方库，特别适用于科学计算，支持并行计算。

Windows 特有的注意事项：

必须将入口代码放在​if __name__ == '__main__':​块中，以防止在 Windows 上无限递归创建子进程

三、代码模板与论文模板

未完待续：

• 代码模板
• 如何在数学建模论文中阐述
• 例子说明
• 多目标遗传算法 NGSA-II（拥挤度函数与​快速非支配排序 ）

参考学习资料：

**[1]**​通俗易懂讲算法-最优化之遗传算法（GA）_哔哩哔哩_bilibili

**[2]**​智能优化算法 2：遗传算法_哔哩哔哩_bilibili

[3] 司守奎.数学建模算法与应用（第 3 版）[M].北京：国防工业出版社，2021.

**[4]**​遗传算法原理及其 matlab 程序实现_matlab 遗传算法 如何浮点数编码-CSDN 博客

‍