遗传算法初探
组成要素
编码
分为二进制编码、实数编码和顺序编码
初始种群的产生
分为随机方法、基于反向学习优化的种群产生。
基于反向学习优化的种群其思想是先随机生成一个种群P(N)，然后按照反向学习方法生成新的种群OP(N),合并两个种群，得到一个新的种群S(N)，对S(N)按适应度排序，选择适应度最高的N个个体作为初始种群。
适应度函数的设计
f
(
x
)
f(x)
f(x)表示目标函数，
F
(
x
)
F(x)
F(x)为适应度函数
线性关系为
F
(
x
)
=
a
f
(
x
)
+
b
F(x)=af(x) + b
F(x)=af(x)+b
幂律关系为
F
=
f
a
F=f^a
F=fa
对数关系为
F
(
x
)
=
a
∗
l
n
f
(
x
)
+
b
F(x)=a*lnf(x) + b
F(x)=a∗lnf(x)+b
指数关系为
F
(
x
)
=
a
∗
e
b
f
(
x
)
+
c
F(x)=a*e^{bf(x)} + c
F(x)=a∗ebf(x)+c
选择策略
对于个体i，其适应度为
F
i
F_i
Fi，假定规模为n，则个体被选中的概率为
P
i
=
F
i
∑
i
=
1
n
F
i
P_i=\frac{F_i}{\sum_{i = 1}^n{F_i}}
Pi=∑i=1nFiFi
可以使用锦标赛选择策略，从种群中选取n个个体，选取最优的个体放入下一代种群中
遗传操作
有交叉和变异两种运算。
其中交叉分为有：单点交叉，双点交叉，单形杂交，球形杂交
变异有：按位变异，高斯变异，有向变异
停止条件
设置最大迭代次数或者适应值函数评估次数，也可以规定的搜索精度
算法流程
数学原理
称为模式定理
模式的原始长度
L
(
H
)
L(H)
L(H)：模板中总的基因位数
模板的定义矩
δ
(
H
)
\delta(H)
δ(H)：模板中从左到右第一个确定字符与最后一个确定字符的距离
模板的阶数
o
(
H
)
o(H)
o(H)：模板中确定字符的个数
模板的容量
D
(
H
)
D(H)
D(H)：模板包含字符串的个数，对于二进制编码来说，
D
(
H
)
=
2
L
(
H
)
−
O
(
H
)
D(H)= 2^{L(H)-O(H)}
D(H)=2L(H)−O(H)
设第(t+1)代种群
P
(
t
+
1
)
P(t+1)
P(t+1)含有H中元素个数的期望值为
E
(
H
⋂
P
(
t
+
1
)
)
E(H\bigcap P(t+1))
E(H⋂P(t+1))，l为种群P(t)中个体和串长，在只有选择操作情况下时
E
(
H
⋂
P
(
t
+
1
)
)
=
∣
H
⋂
P
(
t
)
∣
⋅
N
⋅
f
(
H
,
t
)
F
(
t
)
=
∣
H
⋂
P
(
t
)
∣
⋅
f
(
H
,
t
)
F
ˉ
(
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)}
E(H⋂P(t+1))=∣H⋂P(t)∣⋅N⋅F(t)f(H,t)=∣H⋂P(t)∣⋅Fˉ(t)f(H,t)
在考虑杂交概率情况下
p
c
p_c
pc时，期望值为
E
(
H
⋂
P
(
t
+
1
)
)
=
∣
H
⋂
P
(
t
)
∣
⋅
f
(
H
,
t
)
F
ˉ
(
t
)
⋅
(
1
−
p
c
⋅
δ
(
H
)
l
−
1
)
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})
E(H⋂P(t+1))=∣H⋂P(t)∣⋅Fˉ(t)f(H,t)⋅(1−pc⋅l−1δ(H))
在考虑变异概率情况下
p
m
p_m
pm时，期望值为
E
(
H
⋂
P
(
t
+
1
)
)
=
∣
H
⋂
P
(
t
)
∣
⋅
f
(
H
,
t
)
F
ˉ
(
t
)
⋅
(
1
−
p
c
⋅
δ
(
H
)
l
−
1
)
⋅
(
1
−
p
m
)
o
(
H
)
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)}
E(H⋂P(t+1))=∣H⋂P(t)∣⋅Fˉ(t)f(H,t)⋅(1−pc⋅l−1δ(H))⋅(1−pm)o(H)
非线性约束优化
min
f
(
x
)
s.t.
g
i
(
x
)
≤
0
,
i
=
1
,
2
,
…
,
m
h
j
(
x
)
=
0
,
j
=
1
,
2
,
…
,
p
\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}
mins.t.f(x)gi(x)≤0,i=1,2,…,mhj(x)=0,j=1,2,…,p
其中
x
=
[
x
1
,
x
2
,
…
,
x
n
]
x=[x_1, x_2, \ldots, x_n]
x=[x1,x2,…,xn]
选择策略有
- 约束违背的度数
p ( x ) = ∑ i = 1 m + p q i ( x ) 2 q j ( x ) = { m a x ( 0 , g j ( x ) ) , 1 ≤ j ≤ m ∣ h j ( x ) ∣ , 1 ≤ j ≤ p 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} p(x)=i=1∑m+pqi(x)2qj(x)={max(0,gj(x)),1≤j≤m∣hj(x)∣,1≤j≤p - 约束违背的数目
s ( x ) = ∑ j = 1 m + p n u m j ( x ) n u m ( x ) = { 0 , q j ( x ) ≤ 0 1 , 其他 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} s(x)=j=1∑m+pnumj(x)num(x)={0,qj(x)≤01,其他
个体的特征向量表达为
v ( x ) = ( f ( x ) , p ( x ) , s ( x ) ) v(x)=(f(x), p(x), s(x)) v(x)=(f(x),p(x),s(x))