組成要素
編碼
分為二進制編碼、實數編碼和順序編碼
初始種群的產生
分為隨機方法、基于反向學習優化的種群產生。
基于反向學習優化的種群其思想是先隨機生成一個種群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=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 ) = 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+p?qi?(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+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))
