遺傳算法課件ppt-文庫(kù)吧在線文庫(kù)
【正文】 要將以上二者綜合考慮。 例： NP=100,T=50 即 100名學(xué)生，成績(jī)前 50名的選出。 五 .GA的各種變形（ 37） ??? ff m a x ???? ff i40 背包問(wèn)題 個(gè)物品，對(duì)物品 ，價(jià)值為 ，重量為 ， 背包容量是 。 六 .應(yīng)用（ 6） ? ?xP 0??? Wxw ii???? ??niii Wxw10 ? ? 10 ?? xP?47 b. 解碼法 —— First Fit Heuristic(優(yōu)先適合啟 發(fā)式 )解碼法是一段修復(fù)程序 (修復(fù)可行性的方法 ) ⑴ 步驟： I. 將選上物品按 降序排列； II. 選前 個(gè)物品，使 ； ⑵ 解碼法的關(guān)鍵：如何在 GA中解決可行性問(wèn)題 ⑶ 編碼方法：采用順序編碼 六 .應(yīng)用（ 7） ii wpK ?? ?????111kiiikiii xwWxw48 例： =7 用順序 ( 3 2 5 1 4 6 7 )表示選擇物品的順序 用優(yōu)先適合啟發(fā)式保留前 K位，使解可行 即： =3， ( 3 2 5 ) 問(wèn)題：編碼長(zhǎng)度是可變的，如何做交叉和變異 六 .應(yīng)用（ 8） ?? ?????111kiiikiii xwWxw? ?nxxxX , 21 ??1523523 wW ???????nn30 50 10 40 100 49 ⑷ 變長(zhǎng)順序編碼的遺傳算法插入式交叉算法 a) 在 上選一個(gè)隨機(jī)的斷點(diǎn)； b) 在 上隨機(jī)選一個(gè)基因片斷插入 的斷點(diǎn)處； c) 去掉 上的重復(fù)基因； d) 按優(yōu)先適合啟發(fā)式得到可行解 見下頁(yè)例題 六 .應(yīng)用（ 9） 1P2P 1P1P50 例題 ： 六 .應(yīng)用（ 10） 去掉重復(fù)基因： 3 2 166。 六 .應(yīng)用（ 11） 52 ? 對(duì)于二進(jìn)制編碼來(lái)說(shuō) 7個(gè)項(xiàng)目的背包問(wèn)題共有編碼 個(gè)，這與解空間是一一對(duì)應(yīng)的，但是不能保證解的可行性；對(duì)于邊長(zhǎng)順序編碼來(lái)說(shuō)，其初始編碼（及隨機(jī)產(chǎn)生的項(xiàng)目順序）共有 個(gè)，與解空間不是一一對(duì)應(yīng)的，但是能夠保證解的可行性。 4 6 166。 六 .應(yīng)用（ 3） 44 III. 懲罰策略： 要求設(shè)計(jì)適當(dāng)?shù)膽土P函數(shù)，但設(shè)計(jì)不好會(huì)掩蓋目標(biāo)函數(shù)的優(yōu)化。 五 .GA的各種變形（ 34） ? ? ? ? 11111 11????? ??? ????? qqqq NPjNPjNP? ? 11 ??? jj qqp ? ? NPqqq??? 1137 b. 舉例 : 且： 采用旋輪法，隨機(jī)產(chǎn)生 當(dāng) ，選擇個(gè)體 五 .GA的各種變形（ 35） iki PPPP ??? ?1? ?? ?1.0 8 ...2321????????????? NoqqpNoqqpNoqpNo?112 1 23 1 2 31k k kp p pp p p pp p p p pp p p p p????? ? ???)1,0(Uk ??i前 i1個(gè)個(gè)體的選擇概率 前 i個(gè)個(gè)體的選擇概率 38 III. 正比選擇：個(gè)體 i的選擇概率 令： ， 用動(dòng)態(tài)標(biāo)定來(lái)調(diào)節(jié)選擇壓力，采用 旋輪法 來(lái)共 同完成種群的選擇。如下圖表示： 開始：希望選擇壓力小 后來(lái)：希望選擇壓力大 k?k?k k?30 III. 冪律標(biāo)定： 函數(shù)表達(dá)式： 的取值， 1時(shí)選擇壓力加大 1時(shí)選擇壓力減小 IV. 對(duì)數(shù)標(biāo)定： 函數(shù)表達(dá)式： 對(duì)數(shù)標(biāo)定的作用：縮小目標(biāo)函數(shù)值的差別 五 .GA的各種變形（ 28） ???ff ???f a L n f b? ??31 V. 指數(shù)標(biāo)定： 函數(shù)表達(dá)式： 指數(shù)標(biāo)定的作用：擴(kuò)大差別 VI. 窗口技術(shù)：
數(shù)學(xué)相關(guān)推薦
鄂ICP備17016276號(hào)-1