遗传算法

发表于 更新于 分类于
本文字数： 2.9k 阅读时长 ≈ 3 分钟
群体智能 之 遗传算法 总结

选择

轮盘法（按比例选择法）

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

流程：

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 位

  1. 二进制转十进制 \(x^{'}\) : 乘权求和法

  2. 此 \(x^{'}\) 对应在区间[-1, 2] 内的实数：（转换为在区间内的点）（将 \(x{'}\) 压缩到区间内）

$$ 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.迭代次数满足要求

进化：

​ 就是不断迭代的过程

迭代：

  1. 计算适应度
  2. 标记适应度最大的
  3. 选择
  4. 遍历种群个体（遍历每一行）

先利用交叉造出新个体，保持种群数不变，再利用变异，保持多样性

​

Q&A

Q: 剩下的个体都要进行变异吗？

A: 不是，对所有个体应用一个概率进行变异，概率值自己设定（变异概率），

变异：

  1. 对群中 所有个体 以事先设定的 变异概率 判断是否进行变异
  2. 对进行变异的个体 随机选择变异位进行变异 （通常就选1位进行变异）

Q: 交叉概率？变异概率？

A: 交叉概率，即每个个体 是否进行交叉 的概率

变异概率，即 每个个体 是否进行变异的概率，

每个个体都要应用此概率，概率命中 则 执行操作

概率为 事先自己设定

补充

遗传算法的每个操作对不同的应用选择的策略各有优劣，所以具体情况，具体分析

适应度：

  1. 按比例
  2. 基于排序

选择：

  1. 轮盘赌选择
  2. 随机遍历抽样
  3. 局部选择
  4. 截断选择
  5. 锦标赛选择

交叉：因编码分 二进制、浮点数编码，所以，交叉和变异都有两类

实值重组：

离散重组、中间重组、线性重组、扩展线性重组

二进制交叉：

单点交叉、多点交叉、均匀交叉、洗牌交叉、缩小代理交叉

变异：

实值变异、二进制变异

参考

感谢帮助！

相关文章