遗传算法及其应用¶

一、遗传算法¶

简介¶

遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法

遗传算法对 $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$

\[SGA(C,E,P_0,M,T,\Phi,\Gamma,\Psi,T)\]

\[ \begin{cases} C : \text{个体编码方式} \\ E : \text{个体适应度评价标准} \\ P_0 : \text{初始种群} \\ M : \text{种群规模} \\ T : \text{进化次数} \\ \Phi : \text{选择运算} \\ \Gamma : \text{交叉运算} \\ \Psi : \text{变异运算} \\ T : \text{终止条件} \end{cases} \]

算法流程¶

适应度评价¶

对目标函数 $f(x)$ 最大化的优化问题

\[ F(x) = \begin{cases} f(x) + C & if \; f(x)+C \geq 0 \\ 0 & if \; f(x) + C < 0 \end{cases} \]

这里 $C$ 要选择一个较小的数(如果太大了会使得所有基因型的适应度都差不多)

对目标函数 $f(x)$ 最小化的优化问题

\[ F(x) = \begin{cases} C - f(x) & if \; f(x) \leq C \\ 0 & if \; f(x) > C \end{cases} \]

这里 $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}

\[\begin{cases} b_l = g_l \\ b_i = (b_{i+1}+g_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}$,两个配对个体的每一个基因座上的基因都以相同的交叉概率进行交换，从而形成两个新的个体)

变异算子¶

使用变异算子主要是为了增加种群多样性,防止出现早熟. 也能提高一点局部搜索能力(接近最优解的时候,交叉很难找到最优解)

基本位变异: 选择一个基因座,以一定概率改变其值
均匀变异: 对每一个基因座以一定概率进行变异

三、遗传算法的高级实现技术¶

倒位算子¶

倒位操作 $(\text{inverse operation})$ 是指颠倒个体编码串中随机指定的二个基因座之间的基因排列顺序，从而形成一个新的染色体

多倍体和显性操作算子¶

二倍体的记忆能力使得生物能够记忆以前所经历过的环境及变化，使得生物的遗传进化过程能够快速地适应环境的变化。这个特点在遗传算法中的应用意义就在于，使用二倍体结构的遗传算法能够解决动态环境下的复杂系统优化问题，而常规的遗传算法却不能很好地应用于动态环境，它难于跟踪环境的动态变化过程

变长编码技术¶

四、并行遗传算法¶

$\text{Parallel Genetic Algorithm}, \text{PGA}$

主要目的是为了提高遗传算法的运行速度(传统遗传算法实质上是串行的)

标准并行遗传算法¶

$\text{Standard Parallel Genetic Algorithm}, \text{SPGA}$

分解并行遗传算法¶

$\text{Decomposition Parallel Genetic Algorithm}, \text{DPGA}$

五、遗传算法的数学理论¶

模式¶

模式表示一些相似的模块，它描述了在某些位置上具有相似结构特征的个体编码串的一个子集

$H=10*1*0=\{ 1001000,100110,101100,101110\}$

定义在长度为 $l$ 的二进制编码串上的模式有 $3^l$ 个
- 一般来说,在含有 $k$ 个字母表,长为 $l$ 的编码串上,模式有 $(k+1)^l$ 个
模式阶
- 在模式 $H$ 中具有确定基因值的位置数目称为该模式的模式阶 $(\text{Schema order})$, 记为 $o(H)$
- 如 $o(1*23*)=3$
模式长度
- 模式 $H$ 中第一个确定基因值和最后一个确定基因值之间的距离称为该模式的模式长度 $(\text{Schema length})$, 记为 $\delta(H)$
- 如 $\delta(1*23*)=3$
- 只有一个确定基因值的模式的模式长度为 $1$

模式定理¶

在 $\text{SGA}$ 的情形下讨论

假设第 $t$ 代群体 $P(t)$ 中的个体为 $A_i,i=1,2,\cdots,M$, 其中能与模式 $H$ 匹配(基因型里有 $H$) 的个体个数为 $m(H,t)$, 设每个个体的适应度为 $F(A_i)$, 第$t$ 代群体的平均适应度为 $\bar{F}(t)$, 模式 $H$ 在第 $t$ 代个体的平均适应度为

\[ f(H,t) =\frac{ \sum\limits_{A_i\in H\cap P(t)}F(A_i) }{\#H\cap P(t)} \]

选择算子

\[ \begin{align*} m(H,t+1) &= \sum\limits_{A_i\in H\cap P(t)} \frac{M\times F(A_i)}{F(t)}\\ &= \sum\limits_{A_i\in H\cap P(t)} \frac{M\times f(H,t)}{F(t)}\\ &= \frac{M\times f(H,t)}{F(t)} \sum\limits_{A_i\in H\cap P(t)} 1\\ &= \frac{M\times f(H,t)}{F(t)}m(H,t)\\ &= \frac{f(H,t)}{\bar{F}(t)}\times m(H,t) \end{align*} \]

若模式 $H$ 的平均适应度 $f(H,t)$ 总是高出群体平均适应度 $C$ 倍, 即 $f(H,t)=(1+C)\bar{F}(t)$, 那么有

\[ m(H,t+1)=(1+C)\times m(H,t) \]

这表明如果 $H$ 的平均适应度高于群体平均适应度, 那么其样本数呈指数级增长;否则指数级衰减

交叉算子

\[ p_{survive}(H) \geq 1-p_c \cdot \frac{\delta(H)}{l-1} \]

于是经过选择和交叉

\[ m(H,t+1) \geq (1-p_c \cdot \frac{\delta(H)}{l-1})\times (1+C)\times m(H,t) \]

在 $H$ 平均适应度大于群体平均适应度的情况下, 其模式定义长度越小,其样本数增长越快

变异算子

模式 $H$ 被破坏只能是其确定基因值被变异, 其概率为

\[ 1-(1-p_m)^{o(H)} \]

因为 $p_m$ 通常设置的很小, 所以有

\[ 1-(1-p_m)^{o(H)} \approx p_m \cdot o(H) \]

从而模式生存的概率为

\[ 1-p_m \cdot o(H) \]

这表明模式的模式阶越大,其生存概率越小

总的来说我们有

\[ m(H,t+1) \geq \frac{f(H,t)}{\bar{F}(t)} \left[ 1-p_c\cdot \frac{\delta(H)}{l-1} - p_m\cdots o(H) \right]\times m(H,t) \]

[!NOTE] 这里选择和变异的概率应该是乘起来的, 但是 $(1-x)(1-y)\approx 1-x-y$ 当 $x=o(1)$

模式定理: 在遗传算法中,经过选择,交叉和变异算子的作用,具有低阶短定义长度并且平均适应度高于群体适应度的模式按指数级增长.

积木块假设与遗传算法欺骗问题¶

模式定理说明了具有某种结构特征的模式在遗传进化过程中其样本数将按指数级增长，这种模式就是具有低阶、短的定义长度，且平均适应度高于群体平均适应度的模式。这种类型的模式被称为基因块或积木块( $\text{building block}$)

积木块假设: 个体基因块通过选择、交叉和变异等算子的作用能拼接在一起形成适应度更高的个体编码串
遗传算法欺骗问题($\text{GA deception problem}$): 存在不满足积木块假设的问题
- 例如求 $f(x,y) = \begin{cases} x^2+y^2 & (x,y)\in [-2,2]\times [-2,2]\setminus\{(0,1)\} \\ 1000 & x=y=0 \end{cases}$ 的最大值