遗传算法初探

构成要素

编码

分为二进制编码、实数编码暖和序编码
初始种群的产生

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

f(x)f(x)f(x)表现目标函数，F(x)F(x)F(x)为顺应度函数
线性关系为F(x)=af(x)+bF(x)=af(x) + bF(x)=af(x)+b
幂律关系为F=faF=f^aF=fa
对数关系为F(x)=a∗lnf(x)+bF(x)=a*lnf(x) + bF(x)=a∗lnf(x)+b
指数关系为F(x)=a∗ebf(x)+cF(x)=a*e^{bf(x)} + cF(x)=a∗ebf(x)+c
选择战略

对于个体i，其顺应度为FiF_iFi​，假定规模为n，则个体被选中的概率为Pi=Fi∑i=1nFiP_i=\frac{F_i}{\sum_{i = 1}^n{F_i}}Pi​=∑i=1n​Fi​Fi​​
可以使用锦标赛选择战略，从种群中选取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)=2L(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)​
在思量杂交概率情况下pcp_cpc​时，盼望值为
E(H⋂P(t+1))=∣H⋂P(t)∣⋅f(H,t)Fˉ(t)⋅(1−pc⋅δ(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)​)
在思量变异概率情况下pmp_mpm​时，盼望值为E(H⋂P(t+1))=∣H⋂P(t)∣⋅f(H,t)Fˉ(t)⋅(1−pc⋅δ(H)l−1)⋅(1−pm)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.gi(x)≤0,i=1,2,…,mhj(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=[x1,x2,…,xn]x=[x_1, x_2, \ldots, x_n]x=[x1​,x2​,…,xn​]
选择战略有

• 束缚违背的度数
  p(x)=∑i=1m+pqi(x)2qj(x)={max(0,gj(x)),1≤j≤m∣hj(x)∣,1≤j≤pp(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+p​qi​(x)2qj​(x)={​max(0,gj​(x)),1≤j≤m∣hj​(x)∣,1≤j≤p​​​
  
• 束缚违背的数目
  s(x)=∑j=1m+pnumj(x)num(x)={0,qj(x)≤01,其他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+p​numj​(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))