遺傳算法課件ppt(已修改)
2025-08-28 00:12 本頁(yè)面
【正文】 1 第三章 遺傳算法 2 ?五 .遺傳算法的各種變形 ? ? ? (Scaling) ? ? ?六 . 應(yīng)用 遺傳算法 3 其它編碼方法 ① 順序編碼：用 1到 N的自然數(shù)的不同順序來(lái) 編碼，此種編碼不允許重復(fù)，即 且 ，又稱(chēng)自然數(shù)編碼。 該法適用范圍很廣：指派問(wèn)題、旅行商問(wèn)題和單機(jī)調(diào)度問(wèn)題等等。 合法性問(wèn)題：是否符合采用的編碼規(guī)則的問(wèn)題 五 .GA的各種變形（ 1） ji xx ?Nx i ,2,1 ??4 ② 實(shí)數(shù)編碼： ,R為實(shí)數(shù)集 特征：方便運(yùn)算簡(jiǎn)單，但反映不出基因的特征 ③ 整數(shù)編碼類(lèi)似于順序編碼，但編碼允許重復(fù) 適用于：新產(chǎn)品投入，時(shí)間優(yōu)化，伙伴挑選 例： 3212345 對(duì)順序編碼來(lái)說(shuō)是不合法的，而 對(duì)整數(shù)編碼來(lái)說(shuō)是合法的； 010200不合法的 01 編碼； 五 .GA的各種變形（ 2） ? ? RxxxxX in ?? , 21 ?5 遺傳運(yùn)算中的問(wèn)題 在 順序編碼 遺傳運(yùn)算的過(guò)程中會(huì)遇見(jiàn)不合法 的編碼，應(yīng)戰(zhàn)的策略有二 :拒絕或修復(fù)。 例如：經(jīng)雙切點(diǎn)交叉后，后代編碼不合法 ① 21 166。 345 166。 67 21 166。 125 166。 67 ② 43 166。 125 166。 76 43 166。 345 166。 76 我們采用下面的修復(fù)策略使以上的編碼合法。 五 .GA的各種變形（ 3） 1P2P1C2C6 ① 順序編碼的合法性修復(fù)： I. 交叉修復(fù)策略，分為以下幾種： a. 部分映射交叉 b. 順序交叉 c. 循環(huán)交叉 五 .GA的各種變形（ 4） 7 a. 部分映射交叉 (PMX) ( Partially Mapped Crossover)：用特別的修復(fù)程序解決簡(jiǎn)單的雙切點(diǎn)交叉引起的非法性，步驟： ⑴ 選切點(diǎn) X,Y； ⑵ 交換中間部分； ⑶ 確定映射關(guān)系； ⑷ 將未換部分按映射關(guān)系恢復(fù)合法性。 五 .GA的各種變形（ 5） 8 PMX例題 ： 五 .GA的各種變形（ 6） 映射關(guān)系： 31， 42， 55 則： 4 3 166。 1 2 5 166。 6 7 2 1 166。 3 4 5 166。 7 6 1C2C 2 1 166。 3 4 5 166。 6 7 166。 1 2 5 166。 4 3 166。 1 2 5 166。 7 6 166。 3 4 5 166。 1P2PX Y 9 b. 順序交叉 ( OX )Order Crossover：可看做是帶有不同修復(fù)程序的部分映射交叉的變形。 OX步驟： ⑴ 選切點(diǎn) X,Y； ⑵ 交換中間部分； ⑶ 從切點(diǎn) Y后第一個(gè)基因起列出原順序，去掉已有基因； ⑷ 從切點(diǎn) Y后第一個(gè)位置起，按順序填入。 五 .GA的各種變形（ 7） 10 OX例題： 五 .GA的各種變形（ 8） 列出基因： 6 7 2 1 3 4 5 7 6 4 3 1 2 5 則： 3 4 166。 1 2 5 166。 6 7 1 2 166。 3 4 5 166。 7 6 1C2C 2 1 166。 3 4 5 166。 6 7 166。 1 2 5 166。 4 3 166。 1 2 5 166。 7 6 166。 3 4 5 166。 1P2PX Y 11 OX的特點(diǎn)： 較好的保留了相鄰關(guān)系、先后關(guān)系 ,滿(mǎn)足了 TSP 問(wèn)題的需要 ,但不保留位值特征。 五 .GA的各種變形（ 9） 12 c. 循環(huán)交叉 (CX) Cycle Crossover 基本思想：子串位置上的值必須與父母的相同 位置上的位值相等。 CX步驟： ⑴ 選 的第一個(gè)元素作為 的第一位， 選 的第一個(gè)元素作為 的第一位； 五 .GA的各種變形（ 10） 2P1P
數(shù)學(xué)相關(guān)推薦
鄂ICP備17016276號(hào)-1