【文章內(nèi)容簡介】 三 .模板理論 sf f以上證明沒有考慮交叉變異，那么交叉變異會不會破壞種群模板 S？概率有多大？ 43 2. 模板理論 ? 引理 2：第 t代以概率 pc做交叉，對長度為 l(s)的模板 S中的個體，則在第 t+1代中該個體仍在模板 S中的概率下界為： 其中， P(s,t)為第 t代個體為 S的概率。 三 .模板理論 ? ? ? ?( , 1 ) 1 1 ,1pc l sP s t P s tn?? ? ? ??????44 2. 模板理論 ? 引理 2 證明： 交叉破壞 S的條件 做了交叉： pc 交叉點在 S內(nèi)： l(s)/(n1) 配偶不在 S中： 1P(s,t) 則不被破壞的概率為： 三 .模板理論 ? ? ? ?( , 1 ) 1 1 ,1p c l sP s t P s tn?? ? ? ??????若配偶不屬于模板 S，是否能產(chǎn)生后代為模板 S？ 45 2. 模板理論 ? 引理 3：若第 t代以 pm做變異，對于一個階數(shù)為K(s)的模板 S中的個體，則在第 t+1代仍在 S中的概率下界為： 三 .模板理論 ? ? ? ?, 1 1P s t pm K s? ? ? ?46 2. 模板理論 ? 引理 3 證明： 對于 S來說 當(dāng) K(s)=1時，不被破壞的概率為： 1pm 當(dāng) K(s)1時，不被破壞的概率為 取其泰勒展開式的第一項： 1pm?K(s) 三 .模板理論 ? ? ? ?1 Kspm?47 2. 模板理論 ? 主定理（模板定理）：第 t代以概率 pc和 pm做交叉和變異時，長度為 l(s)，階數(shù)為 K(s)，適值均值比為 f(s,t)的模板 S在第 t+1代的期望個體數(shù)的下界為： 三 .模板理論 ? ?? ?? ? ? ? ? ? ? ?( , 1 )1 1 , , ,1E s tpc l sP s t pm K s f s t N s tn?????? ? ? ??????交叉破壞 變異破壞 48 2. 模板理論 ? 主定理（模板定理）：第 t代以概率 pc和 pm做交叉和變異時，長度為 l(s)，階數(shù)為 K(s)，適值均值比為 f(s,t)的模板 S在第 t+1代的期望個體數(shù)的下界為： 三 .模板理論 ? ?? ?? ? ? ? ? ? ? ?( , 1 )1 1 , , ,1E s tpc l sP s t pm K s f s t N s tn?????? ? ? ??????交叉破壞 變異破壞 當(dāng) 時， E(s,t)隨代數(shù)增加而增加 ? ? ? ? ? ?? ? ? ?1, 1 1 ,1pc l sf s t P s t pm K sn????? ? ? ? ??????49 1. 編碼 ? 編碼原則 ? 完備性（ pleteness）：問題空間的所有解都能表示為所設(shè)計的基因型 ? 健全性（ soundness）：任何一個基因型都對應(yīng)于一個可能解； ? 非冗余性（ nonredundancy）：問題空間和表達(dá)空間盡一一對應(yīng) 四 .算法變形 50 1. 編碼 ? 編碼方式 ? 二進(jìn)制編碼：適用于背包問題、實優(yōu)化、指派問題等 ? 整數(shù)編碼：適用于時間優(yōu)化，伙伴挑選等 ? 順序編碼：適用于指派、旅行商問題，單機調(diào)度等，合法性問題 ? 浮點數(shù)編碼：適用于實優(yōu)化等，簡單運算方便 四 .算法變形 51 1. 編碼 ? 二進(jìn)制編碼與浮點數(shù)編碼的比較 ? 在交叉操作時，二進(jìn)制編碼比浮點數(shù)編碼產(chǎn)生新個體的可能性多，而且產(chǎn)生的新個體不受父個體所構(gòu)成的超體的限制 ? 在變異操作時，二進(jìn)制編碼的種群穩(wěn)定性比浮點數(shù)編碼差 四 .算法變形 52 2. 適值函數(shù)的標(biāo)定 ? 適應(yīng)度函數(shù)的重要性： 適應(yīng)度函數(shù)的選取直接影響遺傳算法的收斂速度以及能否找到最優(yōu)解；一般而言，適應(yīng)度函數(shù)是由目標(biāo)函數(shù)變換而成的，對目標(biāo)函數(shù)值域的某種映射變換稱為適應(yīng)度的標(biāo)定（ fitness scaling）。 四 .算法變形 53 2. 適值函數(shù)的標(biāo)定 ? 標(biāo)定的目的 四 .算法變形 1122334410011002999997ffffffff????????選擇壓力小，差別 小，選優(yōu)功能弱化 了 0254444433422411????????????ffffffffffff選擇壓力大，差別放 大，選優(yōu)功能強化了 標(biāo)定 54 2. 適值函數(shù)的標(biāo)定 ? 標(biāo)定方法 ? 線性標(biāo)定 函數(shù)表達(dá)式 F為適值函數(shù)， f為目標(biāo)函數(shù) a. 對 max f(x) ，令 函數(shù)表達(dá)式 ： b. 對 min f(x) ，令 函數(shù)表達(dá)式 ： 四 .算法變形 F af b??1a?m inbf ?? ? ? m inF f f ?? ? ?1a ?? m a x ? m a xF f f ?? ? ? ?55 2. 適值函數(shù)的標(biāo)定 ? 標(biāo)定方法 ? 動態(tài)線性標(biāo)定（最常用） 函數(shù)表達(dá)式 ， k為迭代指標(biāo) 優(yōu)點：計算容易不占用時間 a. 對 max f(x) ，令 函數(shù)表達(dá)式 ： b. 對 min f(x) ，令 函數(shù)表達(dá)式 ： 四 .算法變形 kkF a f b??1ka ? m ink k kbf ?? ? ? m inkkF f f ?? ?1ka ?? m a xk k k???m a xkkF f f ?? ? ? ?56 2. 適值函數(shù)的標(biāo)定 ? 標(biāo)定方法 ? 動態(tài)線性標(biāo)定（最常用） 的作用： 的加入使最壞個體仍有繁殖的可能， 隨 k的增大而減小 的取值： 調(diào)節(jié) M 和 r，從而來調(diào)節(jié) 四 .算法變形 k? k?k?k M?0 rkk ?? ?1?? ? ?,?rk?57 2. 適值函數(shù)的標(biāo)定 ? 標(biāo)定方法 ? 冪率標(biāo)定 函數(shù)表達(dá)式 α的取值， α 1時加大差別 α 1時減小差別 ? 對數(shù)標(biāo)定 函數(shù)表達(dá)式 對數(shù)標(biāo)定的作用：縮小差別 四 .算法變形 Ff??lnF a f b??58 2. 適值函數(shù)的標(biāo)定 ? 標(biāo)定方法 ? 指數(shù)標(biāo)定 函數(shù)表達(dá)式 指數(shù)標(biāo)定的作用：擴(kuò)大差別 ? 窗口技術(shù) 函數(shù)表達(dá)式 為前 W代中的最小目標(biāo)值，它考慮了各代 的波動，這樣 具有記憶性 四 .算法變形 bfF ae c??wF af f??wf minfwf59 2. 適值函數(shù)的標(biāo)定 ? 標(biāo)定方法 ? 正規(guī)化技術(shù) 函數(shù)表達(dá)式 正規(guī)化技術(shù)的作用：將 F映射到 (0,1)區(qū)間，抑制 超級染色體 正規(guī)化技術(shù)的實質(zhì)：特殊的動態(tài)標(biāo)定 四 .算法變形 m inm a x m inf f rFf f r?????kkF a f b?? rffa k ???minma x1m inm a x m ink frbf f r??60 3. 遺傳操作 —— 選擇 ? 幾個概念 ? 選擇壓力（ selection pressure） ：最佳個體選中的概率與平均個體選中概率的比值 ? 多樣性損失（ loss of diversity）：在選擇階段未選中個體數(shù)目占種群的比例 四 .算法變形 61 3. 遺傳操作 —— 選擇 ? 個體選擇概率的計算方法 ? 按比例的適應(yīng)度分配 某個體 i，其適應(yīng)度為 fi，則其被選取的概率 Pi為 四 .算法變形 1ii NPiifPf???62 3. 遺傳操作 —— 選擇 ? 個體選擇概率的計算方法 ? 基于排序的適應(yīng)度分配 步驟： a. 從好到壞排序所有個體 q ,則第 i個個體的選 擇概率為： 四 .算法變形 1(1 ) iiP q q ???? ? ? ?1111111iNPNPiq q qq????? ???? ????63 3. 遺傳操作 —— 選擇 ? 個體選擇概率的計算方法 ? 基于排序的適應(yīng)度分配 步驟： c. NP有限時要歸一化，則有下面的兩個公式： 四 .算法變形 ? ? 11 ??? jj qqp ?NPqq?? 164 3. 遺傳操作 —— 選擇 ? 常用選擇方法