遗传算法及其应用¶
一、遗传算法¶
简介¶
遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法
-
遗传算法对 \(M\) 个个体组成的集合进行迭代,这个集合称为种群,第 \(t\) 代个体用 \(P(t)\) 表示
-
作用在种群上的遗传算子 \((\text{gene operator})\) 有三种:选择、交叉、变异
- 选择 \((\text{selection})\) : 按一定的规则从上一代种群中选择个体
- 交叉 \((\text{crossover})\) : 两个个体的基因按一定的规则交换
- 变异 \((\text{mutation})\) : 个体的某些基因发生变异
算法流程¶
-
初始化: 设置迭代次数 \(T\), 置迭代计数器 \(t=0\), 随机生成 \(M\) 个个体组成种群 \(P(0)\)
-
个体评价: 计算种群中每个个体的适应度 \((\text{fitness})\)
-
算子作用
- 选择: 从种群 \(P(t)\) 中选择个体生成种群 \(Q(t)\)
- 交叉: 从种群 \(Q(t)\) 中选择两个个体进行交叉生成种群 \(R(t)\)
- 变异: 从种群 \(R(t)\) 中选择个体进行变异生成种群 \(P(t+1)\)
-
终止条件: 若满足终止条件 (\(t>T\)) 则停止, 否则 \(t=t+1\) 返回第三步
-
输出: 输出适应度最大的个体
算法特点¶
-
以决策变量的编码进行运算,对于一些无数值概念的优化问题也可以操作
-
对目标函数的要求很弱 : 不需要求导,不需要连续,只需要能够计算目标函数值
-
每个种群有 \(M\) 个个体,在这之中包括了 很多群体信息。这些信息可以避免搜索 一些不必搜索的点，所以实际上相当于搜索了史多的点，这是遗传算法所特有的一种隐含的并行性
-
使用概率搜索技术,可以避免陷入局部最优解
二、基本遗传算法¶
\(\text{Simple genetic algorithm}, \text{SGA}\)
算法构成¶
-
染色体编码方式: 定长二进制编码
-
个体适应度评价标准:基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的机会多少
- 这要求适应度都要是正数,因此需要确定目标函数值到适应度的映射关系
-
遗传算子
- 选择运算: 比例选择
- 交叉运算: 单点交叉
- 变异运算: 位变异
-
算法参数
- 种群规模 \(M\)
- 进化 次数 \(T\)
- 交叉概率 \(p_c\)
- 变异概率 \(p_m\)
算法流程¶
适应度评价¶
- 对目标函数 \(f(x)\) 最大化的优化问题
这里 \(C\) 要选择一个较小的数(如果太大了会使得所有基因型的适应度都差不多)
- 对目标函数 \(f(x)\) 最小化的优化问题
这里 \(C\) 要选择一个较大的数(理由和上面差不多)
比例选择算子¶
指个体被选中并遗传到下一代群体中的概率与该个体的适应度大小成正比
单点交叉算子¶
选择两个个体后,在某一点将两个个体的染色体都分为两部分,然后交换后半部分
位变异算子¶
对个体的每一个基因座依概率 \(p_m\) 指定为变异点,对变异点用其他等位基因替换
遗传算法的基本实现技术¶
编码方式¶
-
(有意义积木块编码原则):应使用能易于产生与所求问题相关的且具有低阶、短定义长度模式的编码方案
-
(最小字符集编码原则):应使用能使问题得到自然表示或描述的具有最小编码字符集的编码方案
二进制编码¶
设参数取值范围为 \([U_{\text{min}},U_{\text{max}}]\),用长度为 \(L\) 的二进制编码,则编码精度 \(\delta = \frac{U_{\text{max}}- U_{\text{min}}}{2^l-1}\)
对于基因 \(X: b_lb_{l-1}\cdots b_1\),其对应的实数值为 \(U = U_{\text{min}} + \delta\sum\limits_{i=1}^l b_i2^{i-1}\)
格雷编码¶
二进制编码 \(X: b_lb_{l-1}\cdots b_1\) 与格雷编码 \(X: g_lg_{l-1}\cdots g_1\) 的转换
$$ \begin{cases} g_l = b_l \ g_i = (b_{i+1}+b_i) \mod 2 \end{cases}
i=1,2,\cdots,l-1 $$
浮点数编码¶
浮点数编码方法，是指个体的每个基因值用某一范围内的一个浮点数来表示，个体的編码长度等于其决策变量的个数。因为这种编码方法使用的是决策变量的真实值，所以浮点数编码方法也叫做真值编码方法。
[!NOTE] 相当于直接用决策变量来运算
符号编码¶
符号编码方法是指个体染色体编码串中的基因值取自一个 数值含义、而只有代码含义的符号集. 例如 TSP 问题中将一条路线表示为 \([A,B,C,D,E,A]\)
多参数级联编码¶
每个参数用一种编码方案,按顺序连接得到基因型
多参数交叉编码¶
每个参数用一种编码方案,交叉连接得到基因型
适应度函数¶
适应度变换¶
线性尺度变换 \(F^\prime = aF+b\)
\(F\to F'\)
一般要满足两个条件
-
第一个条件： \(F^\prime_{avg}=F_{avg}\)
公式 \(F'_{\text{avg}} = F_{\text{avg}}\) 要求变换后所有个体的新适应度的平均值与原适应度的平均值保持一致。这个条件的作用是确保适应度接近平均值的个体在选择时不会因为变换而失去优势，仍然能够按预期的数量被遗传到下一代。它保证了种群的稳定性，使得那些适应度在平均值附近的个体仍然有机会在选择中保留，而不是因为适应度变换导致某些个体完全失去竞争力。 -
第二个条件： \(F^\prime_{max} = CF_{avg}\)
变换后群体中的最大适应度 \(F'_{\text{max}}\) 要等于原平均适应度的某个指定倍数。这是为了控制遗传算法中优秀个体对整个种群的主导程度。如果不加以限制，某些个体的适应度可能会变得过高，导致它们主导整个群体，进而造成种群的多样性下降，容易陷入局部最优解。通过设定最大适应度的倍数，可以避免过度偏向最优个体，同时保留足够的多样性来继续探索解空间。
选择算子¶
在选择的时候可以保留历史最优个体,这样可以避免把最优个体进化掉,但是另一方面这也容易陷入局部最优解
交叉算子¶
单点交叉,多点交叉
均匀交叉 (\(\text{uniform crossover}\),两个配对个体的每一个基因座上的基因都以相同的交叉概率进行交换，从而形成两个新的个体)
变异算子¶
使用变异算子主要是为了增加种群多样性,防止出现早熟. 也能提高一点局部搜索能力(接近最优解的时候,交叉很难找到最优解)
-
基本位变异: 选择一个基因座,以一定概率改变其值
-
均匀变异: 对每一个基因座以一定概率进行变异