【正文】 tic(優(yōu)先適合啟 發(fā)式 )解碼法是一段修復(fù)程序 (修復(fù)可行性的方法 ) ⑴ 步驟： I. 將選上物品按 降序排列； II. 選前 個(gè)物品，使 ； ⑵ 解碼法的關(guān)鍵：如何在 GA中解決可行性問題 ⑶ 編碼方法：采用順序編碼 六 .應(yīng)用（ 7） ii wpK ?? ?????111kiiikiii xwWxw48 例： =7 用順序 ( 3 2 5 1 4 6 7 )表示選擇物品的順序 用優(yōu)先適合啟發(fā)式保留前 K位，使解可行 即： =3， ( 3 2 5 ) 問題：編碼長度是可變的，如何做交叉和變異 六 .應(yīng)用（ 8） ?? ?????111kiiikiii xwWxw? ?nxxxX , 21 ??1523523 wW ???????nn30 50 10 40 100 49 ⑷ 變長順序編碼的遺傳算法插入式交叉算法 a) 在 上選一個(gè)隨機(jī)的斷點(diǎn)； b) 在 上隨機(jī)選一個(gè)基因片斷插入 的斷點(diǎn)處； c) 去掉 上的重復(fù)基因； d) 按優(yōu)先適合啟發(fā)式得到可行解 見下頁例題 六 .應(yīng)用（ 9） 1P2P 1P1P50 例題 ： 六 .應(yīng)用（ 10） 去掉重復(fù)基因： 3 2 166。 例： NP=100,T=50 即 100名學(xué)生，成績前 50名的選出。 五 .GA的各種變形（ 16） 1P2P? ?? ?nllkknllkkyyyyyyYxxxxxxX,111111????????????切點(diǎn) 切點(diǎn) 1C2C? ?? ?nllkknllkkyyxxyyYxxyyxxX,111111????????????19 五 .GA的各種變形（ 17） c. 凸組合交叉：可以克服上面簡單交叉操作導(dǎo)致的解的不可行性。 6 7 1 2 166。 五 .GA的各種變形（ 5） 8 PMX例題 ： 五 .GA的各種變形（ 6） 映射關(guān)系： 31， 42， 55 則： 4 3 166。 合法性問題：是否符合采用的編碼規(guī)則的問題 五 .GA的各種變形（ 1） ji xx ?Nx i ,2,1 ??4 ② 實(shí)數(shù)編碼： ,R為實(shí)數(shù)集 特征：方便運(yùn)算簡單，但反映不出基因的特征 ③ 整數(shù)編碼類似于順序編碼，但編碼允許重復(fù) 適用于：新產(chǎn)品投入，時(shí)間優(yōu)化，伙伴挑選 例： 3212345 對順序編碼來說是不合法的，而 對整數(shù)編碼來說是合法的； 010200不合法的 01 編碼； 五 .GA的各種變形（ 2） ? ? RxxxxX in ?? , 21 ?5 遺傳運(yùn)算中的問題 在 順序編碼 遺傳運(yùn)算的過程中會(huì)遇見不合法 的編碼，應(yīng)戰(zhàn)的策略有二 :拒絕或修復(fù)。 3 4 5 166。 1 2 5 166。 五 .GA的各種變形（ 19） ? ?? ?aUxfXZ,0???????22 適值函數(shù)的標(biāo)定 (Scaling) 五 .GA的各種變形（ 20） 997999100210014321????ffff0254444433422411????????????ffffffffffff 相對 差別放大，選擇壓力變大，選優(yōu)功能強(qiáng)化了 標(biāo)定 相對 差別小，選擇壓力小，選優(yōu)功能弱化了 23 ① 標(biāo)定的目的： 使適值函數(shù)不會(huì)太大，有一定差別 I. 選擇壓力的概念： 選擇壓力是種群好、壞個(gè)體被選中的概率 之差，差大稱為選擇壓力大 。 五 .GA的各種變形（ 36） 00 ?PP ???NPiii PPP1??? NPiiiiFFP139 停止準(zhǔn)則 ① 指定最大代數(shù)（常用）：該方法簡單但不準(zhǔn)確。 1 5 4 1 2 166。