遺傳算法課件ppt(完整版)
【正文】 函數(shù)表達(dá)式： 為前 W代中的最小目標(biāo)值，它考慮了各代 的波動(dòng)，這樣 具有記憶性 五 .GA的各種變形（ 29） caef bf ???wfaff ???wfwfminf32 G. 正規(guī)化技術(shù)： 函數(shù)表達(dá)式： 正規(guī)化技術(shù)的作用： 將 映射到 (0,1)區(qū)間，抑制超級(jí)染色體 正規(guī)化技術(shù)的實(shí)質(zhì)：特殊的動(dòng)態(tài)標(biāo)定 即 其中： 五 .GA的各種變形（ 30） frffrfff??????m inm a xm inkk bfaf ???rffak??? m inm a x1rffrfb k?????m inm a xm in33 選擇策略 傳統(tǒng)的 GA選擇和遺傳是一起進(jìn)行的，即使 后代不如父代，卻無(wú)法糾正。但染色體種群也可能因此而趨于聚集，導(dǎo)致種群的多樣性較差。 CX步驟： ⑴ 選 的第一個(gè)元素作為 的第一位， 選 的第一個(gè)元素作為 的第一位； 五 .GA的各種變形（ 10） 2P1P 1C2C13 ⑵ 到 中找 的第一個(gè)元素賦給 的相對(duì)位置 … ，重復(fù)此過(guò)程，直到 上得到 的第一個(gè)元素為止，稱為一個(gè)循環(huán)； ⑶ 對(duì) 最前 的基因按 、 基因 輪替 原則重復(fù)以上過(guò)程； ⑷ 重復(fù)以上過(guò)程，直到所有位都完成。 6 7 166。 1P2PX Y 9 b. 順序交叉 ( OX )Order Crossover：可看做是帶有不同修復(fù)程序的部分映射交叉的變形。 7 6 1C2C 2 1 166。 76 43 166。 該法適用范圍很廣：指派問(wèn)題、旅行商問(wèn)題和單機(jī)調(diào)度問(wèn)題等等。 125 166。 1 2 5 166。 1 2 5 166。 3 4 5 166。 3 4 5 166。 約束是個(gè)凸集，可行性可以保持，但是分散 性太差，又出現(xiàn)了向中間匯集的問(wèn)題。一般來(lái)說(shuō)，算法開(kāi)始時(shí)應(yīng)注重廣域搜索，通過(guò)使用較小的選擇壓力來(lái)實(shí)現(xiàn)；隨著迭代的進(jìn)行，逐步偏重于局部搜索，通過(guò)使用較大的選擇壓力來(lái)實(shí)現(xiàn)。每人的選擇概率為 1／ 50，有平均 2個(gè)機(jī)會(huì)。如何選取物品裝入背包，使背 包中的價(jià)值最大。 4 6 166。 1282 7 ?5040!7 ?53 。 1 5 4 3 2 166。 ? 背包問(wèn)題示例 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 43 ① 如何處理約束來(lái)保持可行性 I. 拒絕策略： 可行解不易達(dá)到時(shí)，很難達(dá)到一個(gè)初始種群 II. 修復(fù)策略： 將不可行解修復(fù)為可行的，但將失去多樣性。 五 .GA的各種變形（ 32） 35 II. 順序選擇： a. 步驟： ⑴ 從好到壞排序所有個(gè)體 ⑵ 定義最好個(gè)體的選擇概率為 ,則第 個(gè)個(gè)體的選擇概率為： 五 .GA的各種變形（ 33） ? ? ? ? 11 ??? jqqjpq j36 ⑶ 由于 有限時(shí)要?dú)w一化，則有下面的公式： ，其中 順序選擇的優(yōu)點(diǎn)：選擇概率可以離線計(jì)算，節(jié)省算法執(zhí)行時(shí)間，且選擇壓力可控； 缺點(diǎn)：把選擇概率固定化了，選擇壓力不可調(diào)節(jié)。 五 .GA的各種變形（ 24） ? ?xfmax? ? m infxff ???? ?xfmin? ?xfff ??? m a xa b minf?a bmaxf27 II. 動(dòng)態(tài)線性標(biāo)定 (最常用 )：線性標(biāo)定中的參數(shù)隨著迭代次數(shù)的增加而變化時(shí)就得到了動(dòng)態(tài)線性標(biāo)定 優(yōu)點(diǎn)：計(jì)算容易不占用時(shí)間 函數(shù)表達(dá)式： ， 為迭代指標(biāo) a. 最常用最大化 =1 , 函數(shù)表達(dá)式： 五 .GA的各種變形（ 25） kk bfaf ??? kkk fb ???? m inkakfff ????? m in第 k代的最小目標(biāo)函數(shù)值 28 b. 加入的意義 （同線
數(shù)學(xué)相關(guān)推薦
鄂ICP備17016276號(hào)-1