当前位置：首页 > article >正文

遗传算法初探

article 2026/4/8 10:32:19

组成要素

编码

分为二进制编码、实数编码和顺序编码

初始种群的产生

分为随机方法、基于反向学习优化的种群产生。
基于反向学习优化的种群其思想是先随机生成一个种群P(N)，然后按照反向学习方法生成新的种群OP(N),合并两个种群，得到一个新的种群S(N)，对S(N)按适应度排序，选择适应度最高的N个个体作为初始种群。

适应度函数的设计

$f (x)$ 表示目标函数， $F (x)$ 为适应度函数
线性关系为 $F (x) = a f (x) + b$
幂律关系为 $F=f^a$
对数关系为 $F (x) = a * l n f (x) + b$
指数关系为 $F(x)=a*e^{bf(x)} + c$

选择策略

对于个体i，其适应度为 $F_i$ ，假定规模为n，则个体被选中的概率为 $P_i=\frac{F_i}{\sum_{i = 1}^n{F_i}}$
可以使用锦标赛选择策略，从种群中选取n个个体，选取最优的个体放入下一代种群中

遗传操作

有交叉和变异两种运算。
其中交叉分为有：单点交叉，双点交叉，单形杂交，球形杂交
变异有：按位变异，高斯变异，有向变异

停止条件

设置最大迭代次数或者适应值函数评估次数，也可以规定的搜索精度

算法流程

数学原理

称为模式定理
模式的原始长度 $L (H)$ ：模板中总的基因位数
模板的定义矩 $\delta(H)$ ：模板中从左到右第一个确定字符与最后一个确定字符的距离
模板的阶数 $o (H)$ ：模板中确定字符的个数
模板的容量 $D (H)$ ：模板包含字符串的个数，对于二进制编码来说， $D(H)= 2^{L(H)-O(H)}$
设第(t+1)代种群 $P (t + 1)$ 含有H中元素个数的期望值为 $E(H\bigcap P(t+1))$ ，l为种群P(t)中个体和串长，在只有选择操作情况下时
$E(H\bigcap P(t+1))=|H\bigcap P(t)| \cdot N \cdot \frac{f(H,t)}{F(t)} = |H\bigcap P(t)| \cdot \frac{f(H, t)}{\bar{F}(t)}$
在考虑杂交概率情况下 $p_c$ 时，期望值为
$E(H\bigcap P(t+1))= |H\bigcap P(t)| \cdot \frac{f(H, t)}{\bar{F}(t)} \cdot (1 - p_c \cdot \frac{\delta (H)}{l - 1})$
在考虑变异概率情况下 $p_m$ 时，期望值为 $E(H\bigcap P(t+1))= |H\bigcap P(t)| \cdot \frac{f(H, t)}{\bar{F}(t)} \cdot (1 - p_c \cdot \frac{\delta (H)}{l - 1}) \cdot (1 - p_m)^{o(H)}$

非线性约束优化

$\begin{equation} \begin{aligned} \min & \quad f(x) \\ \text{s.t.} \quad & g_i(x) \le 0, \quad i = 1, 2, \ldots, m \\ & h_j(x) = 0, \quad j=1,2,\ldots, p \end{aligned} \end{equation}$
其中 $x=[x_1, x_2, \ldots, x_n]$
选择策略有

约束违背的度数
$p(x)=\sum_{i=1}^{m+p} {q_i(x)^2} \\ \begin{equation} q_j(x)=\left\{ \begin{aligned} & max(0, g_j(x)), \quad 1 \le j \le m \\ & |h_j(x)|, \quad 1 \le j \le p \end{aligned} \right. \end{equation}$
约束违背的数目
$s(x)=\sum_{j=1}^{m+p} {num_j(x)} \\ \begin{equation} num(x)=\left\{ \begin{aligned} & 0, \quad q_j(x) \le 0 \\ & 1,其他 \end{aligned} \right. \end{equation}$
个体的特征向量表达为
$v (x) = (f (x), p (x), s (x))$