【正文】 順序編碼交叉 在順序編碼遺傳運(yùn)算的過程中會遇見不合法 的編碼，應(yīng)戰(zhàn)的策略有二：拒絕或修復(fù) 例如：經(jīng)交叉后，后代編碼不合法 P1: 21 166。 67 C1: 21 166。 67 P2: 43 166。 76 C2: 43 166。 76 四 .算法變形 71 3. 遺傳操作 —— 交叉或重組 ? 順序編碼交叉 ? 部分映射交叉 (PMX) 步驟： a. 選切點(diǎn) X,Y； b. 交換中間部分； c. 確定映射關(guān)系； d. 將未換部分按映射關(guān)系恢復(fù)合法性 四 .算法變形 72 3. 遺傳操作 —— 交叉或重組 ? 順序編碼交叉 ? 部分映射交叉 (PMX) 四 .算法變形 P1: 2 1 166。 6 7 166。 P2: 4 3 166。 7 6 166。 映射關(guān)系： 31， 42， 55 C1: 4 3 166。 6 7 C2: 2 1 166。 7 6 73 3. 遺傳操作 —— 交叉或重組 ? 順序編碼交叉 ? 順序交叉 (OX) 步驟： a. 選切點(diǎn) X,Y； ； c. 從切點(diǎn) Y后第一個(gè)基因起列出原序，去掉已有 基因； d. Y后第一個(gè)位置起填入。 3 4 5 166。 1 2 5 166。 1 2 5 166。 3 4 5 166。 1 2 5 166。 3 4 5 166。 四 .算法變形 77 3. 遺傳操作 —— 交叉或重組 ? 順序編碼交叉 ? 循環(huán)交叉 (CX) 四 .算法變形 P1: 2 4 5 3 8 9 6 1 7 2 3 6 P2: 3 9 8 6 5 4 2 7 1 3 6 2 3 2 ， 9 4 ， 5 8 ， 7 1 6 C1: 2 9 5 3 8 4 6 7 1 C2: 3 4 8 6 5 9 2 1 7 78 3. 遺傳操作 —— 交叉或重組 ? 順序編碼交叉 ? 循環(huán)交叉 (CX ) 與 OX的特點(diǎn)不同的是， CX較好的保留了位值 特征，適合指派問題；而 OX較好的保留了相鄰 關(guān)系、先后關(guān)系滿足了 TSP問題的需要。 80 3. 遺傳操作 —— 交叉或重組 ? 實(shí)數(shù)編碼交叉 ? 線性重組： 子個(gè)體＝父個(gè)體 1＋ α （父個(gè)體 2－父個(gè)體 1）， 其中， α是比例因子，由 [d,1+d]上均勻分布地隨 機(jī)數(shù)產(chǎn)生 d=0時(shí)稱為中間重組 四 .算法變形 81 3. 遺傳操作 —— 變異 ? 二進(jìn)制編碼變異：位變異 ? 順序編碼變異： 2opt ? 實(shí)數(shù)編碼變異 ? 位值變異：任選一位加 Δ， Δ服從均勻分布、指數(shù)分布或者正態(tài)分布 ? 梯度方向變異 四 .算法變形 82 1. 背包問題 n個(gè)物品，對物品 i，價(jià)值為 pi ，體積為 wi ，背包容量 是 W。 五 .算法應(yīng)用 i 1 2 3 4 5 6 7 wi 40 50 30 10 10 40 30 pi 40 60 10 10 3 20 60 pi /wi 1 1 2 83 1. 背包問題 ? 模型 五 .算法應(yīng)用 11m a x..{ 0 , 1 }niiiniiiipxs t w x Wx??????84 1. 背包問題 ? 求解難點(diǎn)：如何處理約束來保持解的可行性 ? 拒絕策略：可行解不易達(dá)到時(shí)，很難達(dá)到一個(gè)初始種群 ? 修復(fù)策略：將不可行解修復(fù)為可行的，但將失去多樣性 ? 懲罰策略：設(shè)計(jì)懲罰函數(shù)，但設(shè)計(jì)不好會掩蓋目標(biāo)函數(shù)的優(yōu)化 五 .算法應(yīng)用 下面，我們將分別采用懲罰策略、解碼法、順序編碼的方法來解決上述難題 85 1. 背包問題 ? 懲罰函數(shù)法 將適值函數(shù) 標(biāo)定為 ，其中 是目標(biāo)函數(shù) 令 ，其中 五 .算法應(yīng)用 ? ? ? ? ? ?F x f x P x? ? ?fx? ? 11niiiw x WPx???????????? ?? ??nii WwW1,max?注： 與 是 的兩個(gè)端點(diǎn) W???nii Ww1???niii Wxw1? ??? 0,0,0 ?x ? ??? 1,1,1 ?x86 1. 背包問題 ? 懲罰函數(shù)法 ? 函數(shù)式的意義 a. 的作用是使 ，保證 b. 可行也罰，只有當(dāng) 不罰 ，盡量裝滿 五 .算法應(yīng)用 ????? ??niii Wxw10 ? ?10 ?? xP? ?Px0??? Wxw ii87 1. 背包問題 ? 解碼法 —— FF Heuristic（優(yōu)先適合啟發(fā)式） 解碼法是修復(fù)程序（修復(fù)可行性的方法） ? 步驟 a. 將選上物品按 pi /wi 降序排列 b. 選前 K個(gè)物品，使 例 ： → 降序排列： 2， 1， 6， 5 → → 五 .算法應(yīng)用 ???????111kiiikiii xwWxw(1 1 0 0 1 1 0 )x ?2 1 2 1 6w w W w w w? ? ? ? ?(1 1 0 0 0 0 0 )x ?88 1. 背包問題 ? 順序編碼法 ? 步驟 a. 隨機(jī)產(chǎn)生一個(gè)項(xiàng)目順序 ，即保留項(xiàng)目 順序的前 k位，使 五 .算法應(yīng)用 ? ?12, , , nx x x?? ?????111kiiikiii xwWxw89 1. 背包問題 ? 順序編碼法 例： n=7 用順序 ( 3 2 5 1 4 6 7 )表示選擇物品的順序，用優(yōu)先適合啟發(fā)式保留前 k位，使解可行 由于 k=3， (3 2 5) 五 .算法應(yīng)用 ?? ?????111kiiikiii xwWxw 1523523wW ???????編碼長度是可變的，如何做交叉和變異 ? 90 1. 背包問題 ? 順序編碼法 ? 插入式交叉 a. 在 P1上選一個(gè)隨機(jī)的斷點(diǎn) b. 在 P2上隨機(jī)選一個(gè)基因片斷插入 P1的斷點(diǎn)處 c. 去掉 P1上的重復(fù)基因 d. 按優(yōu)先適合啟發(fā)式得到可行解 五 .算法應(yīng)用 91 1. 背包問題 ? 順序編碼法 ? 插入式交叉 例 ： 五 .算法應(yīng)用 去掉重復(fù)基因： 3 2 166。 1 5 可行嗎 ？選 5時(shí)背包裝 不 下 ，去掉 5，則 3 2 4 6 1 P1 3 2 166。 4 6 166。 4 6 166。 i=3, ( i , j )=(3,2), j=2 i=4, ( i , j )=(4,6), j=6。 六 .學(xué)習(xí)遺傳算法的幾點(diǎn)體會 107 2. 遺傳算子的設(shè)計(jì)有最大的創(chuàng)新空間 3. 選擇壓力的調(diào)整使多樣性和收斂性得到合適的分配。 調(diào)整方法：適值函數(shù)的構(gòu)造；合適的標(biāo)定方法 六 .學(xué)習(xí)遺傳算法的幾點(diǎn)體會 108 4. 在 GA的研究中我們要做一些什么 ① 擴(kuò)大 GA的應(yīng)用 , GA應(yīng)用面廣，適應(yīng)性最好 ② 算法改進(jìn)方向的研究 ③ 理論研究 ④ 算法開發(fā)中的幾個(gè)技術(shù) (見下頁 ) 六 .學(xué)習(xí)遺傳算法的幾點(diǎn)體會 109 I. 參數(shù)整定：經(jīng)驗(yàn)加反復(fù)試驗(yàn) (Tuning) 如： Pc， Pm， NG， NP幾種參數(shù)的選定 II. 判斷好壞算法的辦法： ⑴ 快 ⑵ 能解的問題大 ⑶ 達(dá)優(yōu)率高，大問題 50%的達(dá)優(yōu)率 六 .學(xué)習(xí)遺傳算法的幾點(diǎn)體會 110 III. 算例的選擇： ⑴ 自己編的 —— 沒有說服力，但可以解釋算法 ⑵ 隨機(jī)產(chǎn)生的 —— 適合沒有前例的例子 ⑶ 文獻(xiàn)的例子 —— 面較大 ⑷ 網(wǎng)上的例子 —— 典型問題 QAP,TSP 六 .學(xué)習(xí)遺傳算法的幾點(diǎn)體會