遺傳算法課件ppt(文件)
【正文】 2 1P2P 3 2 ， 9 4 ， 5 8 ， 7 1 6 2 9 3 4 6 3 4 6 9 2 1C2C1P 1P2P 2P 2 9 5 3 8 4 6 7 1 3 4 8 6 5 9 2 1 7 1C2C15 CX的特點(diǎn)： 與 OX的特點(diǎn)不同的是， CX較好的保留了位值 特征，適合指派問題；而 OX較好的保留了相鄰 關(guān)系、先后關(guān)系滿足了 TSP問題的需要。 約束是個(gè)凸集，可行性可以保持，但是分散 性太差，又出現(xiàn)了向中間匯集的問題。 五 .GA的各種變形（ 19） ? ?? ?aUxfXZ,0???????22 適值函數(shù)的標(biāo)定 (Scaling) 五 .GA的各種變形（ 20） 997999100210014321????ffff0254444433422411????????????ffffffffffff 相對(duì) 差別放大，選擇壓力變大，選優(yōu)功能強(qiáng)化了 標(biāo)定 相對(duì) 差別小，選擇壓力小，選優(yōu)功能弱化了 23 ① 標(biāo)定的目的： 使適值函數(shù)不會(huì)太大，有一定差別 I. 選擇壓力的概念： 選擇壓力是種群好、壞個(gè)體被選中的概率 之差，差大稱為選擇壓力大 。一般來說，算法開始時(shí)應(yīng)注重廣域搜索，通過使用較小的選擇壓力來實(shí)現(xiàn)；隨著迭代的進(jìn)行，逐步偏重于局部搜索，通過使用較大的選擇壓力來實(shí)現(xiàn)。下面介紹的選擇 策略都是先遺傳后選擇。每人的選擇概率為 1／ 50，有平均 2個(gè)機(jī)會(huì)。 五 .GA的各種變形（ 36） 00 ?PP ???NPiii PPP1??? NPiiiiFFP139 停止準(zhǔn)則 ① 指定最大代數(shù)（常用）：該方法簡(jiǎn)單但不準(zhǔn)確。如何選取物品裝入背包，使背 包中的價(jià)值最大。 下面，我們將分別采用懲罰策略和解碼法來處理上面的背包問題。 4 6 166。 1 5 4 1 2 166。 1282 7 ?5040!7 ?53 。 3 5 1P2PX 51 （ 5）變長(zhǎng)順序編碼的遺傳算法插入式變異算法 a) 隨機(jī)刪除一個(gè)基因； b) 在染色體中隨機(jī)插入一個(gè)沒有的基因； c) 對(duì)于以上原始后代用優(yōu)先適合啟發(fā)式方法產(chǎn)生一個(gè)可行解。 1 5 4 3 2 166。 ⑶ 罰函數(shù)法的目的：把解拉向邊界，盡量裝滿。 ? 背包問題示例 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 ① 如何處理約束來保持可行性 I. 拒絕策略： 可行解不易達(dá)到時(shí)，很難達(dá)到一個(gè)初始種群 II. 修復(fù)策略： 將不可行解修復(fù)為可行的，但將失去多樣性。計(jì)算公式： 或 第二種方法因很難實(shí)現(xiàn)，所以很少使用。 五 .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的各種變形（ 31） 34 I. 截?cái)噙x擇： 選擇 最好的前 T個(gè) 個(gè)體，讓每一個(gè)有 1/T的選擇概率，平均得到 NP/T個(gè)繁殖機(jī)會(huì)。 五 .GA的各種變形（ 24） ? ?xfmax? ? m infxff ???
數(shù)學(xué)相關(guān)推薦
鄂ICP備17016276號(hào)-1