遗传算法

发表于 2020-12-05 更新于 2022-05-22 分类于机器学习本文字数： 24k 阅读时长 ≈ 22 分钟

群体智能之遗传算法总结

选择

轮盘法（按比例选择法）

基本思想：各个个体被选中概率与其适应度大小成正比

流程：

1. 初始化每个个体适应度（共M个个体）

这里举例，M = 4 s1 = 13 (01101) s2 = 24 (11000) s3 = 8 (01000) s4 = 19 (10011) PS: s1 表现型: 13 基因型（二进制编码，串长取决于求解精度）：01101 表现型用十进制基因型用二进制编码

2. 计算适应度

\[ f(s_1) = f(13)=13^2=169 \\\\ f(s_2) = f(24)=24^2=576 \\\\ f(s_3) = f(8)=8^2=64 \\\\ f(s_4) = f(19)=19^2=361 \\\\ \]

3. 选择

染色体选择概率:

染色体累积概率：

根据以上两概率，可画轮盘图：

PS: 这里可看出累积概率被用作标记区间间隔点，而选择概率则是区间大小，区间越大，被选中几率越高产生随机数：
\[ r1 = 0.450126, \ r2 = 0.110347 \\ r3 = 0.572496, \ r4 = 0.98503 \] 随机产生相同个体数的数，看这些随机数落在哪个区间，若某区间一次都没被选中，则区间对应个体淘汰

PS: 重复选中，则代表着有被淘汰的个体，一次都没被选中的淘汰 s2 被选中2次，本该一个染色体1次，说明重复了1次，因为还是要选择4个，于是（淘汰一个），一次都没被选中的 s3 淘汰举例，求一元函数最大值 \[ f(x)_{max}=xsin⁡(10π*x)+2.0 \\\\ x∈[-1,2] \]

函数

的曲线

编码

变量 x（十进制）作为表现型表现型 --> 基因型的映射称为编码通常用二进制编码将变量值代表的某个体表示为一个二进制串 [0, 1, 0, 1, 0, 1] 若设定精确到 6位小数由区间长度 2 - (-1) = 3，因此将闭区间 [-1, 2]分为 3*10^6 等份又因，
\[ 2097152=2^{21}<3*10^6<=2^{22}=4194304 \]
所以，编码的二进制串至少需 22 位

$
g 为 x^{'} 对应的累积概率（可代表它在区间上偏移百分之多少的位置）, \\ 代表区间长为3被划分为 2^{22}-1 块，每一块的长度 \\
于是， \\
则代表此x^{'} 的偏移长，再加上区间前-1.0，于是便映射到了区间上
$ 串[0………0] 和串[1……1] （每个里都是22个数）分别表示区间的两个端点值 -1 和 2

步骤

0. 数据形状

n 个个体，每个个体 m 串长 \[ x = \left[ \begin{array} { c c c c } { x _ { 1 } ^ { 1 } } & { x _ { 1 } ^ { 2 } } & { \cdots } & { x _ { 1 } ^ { m } } \\ { x _ { 2 } ^ { 1 } } & { x _ { 2 } ^ { 2 } } & { \cdots } & { x _ { 2 } ^ { m } } \\ { \vdots } & { \vdots } & { \ddots } & { \vdots } \\ { x _ { n } ^ { 1 } } & { x _ { n } ^ { 2 } } & { \cdots } & { x _ { n } ^ { m } } \end{array} \right] \] 一行一个体例如：

4 个体，5 串长

1. 二进制 -> 十进制

\[ \left[ \begin{array} { c } { 13 } \\ { 24 } \\ { 8 } \\ { 19 } \end{array} \right] _ { 4 \times 1 } \]

2. 映射到区间 [-1, 2]

\[ \left[ \begin{array} { c } { a } \\ { b } \\ { c } \\ { d } \end{array} \right] _ { 4 \times 1 } \]

3. 产生初始种群

产生串长为 22 的随机二进制串（染色体的基因码）产生 n 个即 -> 产生一定数的个体（n个）组成种群

4. 计算适应度

个体适应度越大越易存活（被选中概率越大）在本例，目标函数 $f(x)$ 在定义域 [-1, 2] 上恒大于 0 ，且求 $f(x)_{max}$ 所以，此时直接引用目标函数作适应度函数
\[ f(s) = f(x) \]
eg: $x_1 = 0.637197$ ---编码--> [1,0,0, ..., 1,1,1] 此个体适应度: $f(s_1) = f(x_1) = x_1sin(10 \pi * x_1) + 2.0 = 2.286345$ 选择：使用轮盘法（也可以用其它，选择策略基于个体适应度进行，若求最小值，则较小适应值个体被选择概率更大）下面是经选择后两个体:
\[ s_2=[0,0,0,0 | 0,1,0,1,0] \\\\ s_3=[0,1,1,0 | 1,0,1,0,1] \] 中间 | 为交叉点注意: 二进制串，这里随便写的，只是举例交叉：交叉：随机选一交叉点，将之后的串交叉（互换） \[ s_2^{'}=[0,0,0,0 | 1,0,1,0,1] \\\\ s_3^{'}=[0,1,1,0 | 0,1,0,1,0] \] PS：只设置一个交叉点，称为单点交叉单点交叉，适合二进制编码交叉单点交叉又称为简单交叉，它是指在个体编码串中只随机设置一个交叉点，然后在该点相互交换两个配体个体的部分染色体变异：交叉算子：根据交叉概率 $p_c$（预先指定，一般 0.9）来判断父代个体是否交叉交叉算子是GA核心，好坏直接决定整个算法优劣变异算子：变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动据变异概率 $p_m$ （预先指定，一般0.1）来判断父代个体是否变异作用：所以，一般设计为一种随机变换交叉变异后，产生父代种群 $FP(g)$ 生成新子代种群 $P(g+1)$ 进行下一轮迭代（跳转到个体选择）结束迭代条件：1.迭代次数满足要求进化：就是不断迭代的过程迭代：

计算适应度标记适应度最大的选择遍历种群个体（遍历每一行）先利用交叉造出新个体，保持种群数不变，再利用变异，保持多样性 Q&A Q: 剩下的个体都要进行变异吗？ A: 不是，对所有个体应用一个概率进行变异，概率值自己设定（变异概率），变异：

对群中所有个体以事先设定的变异概率判断是否进行变异对进行变异的个体随机选择变异位进行变异（通常就选1位进行变异） Q: 交叉概率？变异概率？ A: 交叉概率，即每个个体是否进行交叉的概率变异概率，即每个个体是否进行变异的概率，每个个体都要应用此概率，概率命中则执行操作概率为事先自己设定补充遗传算法的每个操作对不同的应用选择的策略各有优劣，所以具体情况，具体分析适应度：

按比例基于排序选择：

轮盘赌选择随机遍历抽样局部选择截断选择锦标赛选择交叉：因编码分二进制、浮点数编码，所以，交叉和变异都有两类实值重组：离散重组、中间重组、线性重组、扩展线性重组二进制交叉：单点交叉、多点交叉、均匀交叉、洗牌交叉、缩小代理交叉变异：实值变异、二进制变异参考感谢帮助！遗传算法遗传算法详解附python代码实现 https://blog.csdn.net/u013719780/article/details/78724971 https://blog.csdn.net/qq_40130759/article/details/79535575 遗传算法的交叉变异详解