遺傳算法課件ppt(參考版)
2024-08-27 00:12本頁面
【正文】 1282 7 ?5040!7 ?53 。 3 5 1P2PX 51 （ 5）變長順序編碼的遺傳算法插入式變異算法 a) 隨機(jī)刪除一個基因； b) 在染色體中隨機(jī)插入一個沒有的基因； c) 對于以上原始后代用優(yōu)先適合啟發(fā)式方法產(chǎn)生一個可行解。 1 5 4 1 2 166。 1 5 4 3 2 166。 4 6 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á)到時，很難達(dá)到一個初始種群 II. 修復(fù)策略： 將不可行解修復(fù)為可行的，但將失去多樣性。如何選取物品裝入背包，使背 包中的價值最大。計算公式： 或 第二種方法因很難實(shí)現(xiàn)，所以很少使用。 五 .GA的各種變形（ 36） 00 ?PP ???NPiii PPP1??? NPiiiiFFP139 停止準(zhǔn)則 ① 指定最大代數(shù)（常用）：該方法簡單但不準(zhǔn)確。 五 .GA的各種變形（ 32） 35 II. 順序選擇： a. 步驟： ⑴ 從好到壞排序所有個體 ⑵ 定義最好個體的選擇概率為 ,則第 個個體的選擇概率為： 五 .GA的各種變形（ 33） ? ? ? ? 11 ??? jqqjpq j36 ⑶ 由于 有限時要?dú)w一化，則有下面的公式： ，其中 順序選擇的優(yōu)點(diǎn)：選擇概率可以離線計算，節(jié)省算法執(zhí)行時間，且選擇壓力可控； 缺點(diǎn)：把選擇概率固定化了，選擇壓力不可調(diào)節(jié)。每人的選擇概率為 1／ 50，有平均 2個機(jī)會。 五 .GA的各種變形（ 31） 34 I. 截斷選擇： 選擇 最好的前 T個 個體，讓每一個有 1/T的選擇概率，平均得到 NP/T個繁殖機(jī)會。下面介紹的選擇 策略都是先遺傳后選擇。 五 .GA的各種變形（ 24） ? ?xfmax? ? m infxff ???? ?xfmin? ?xfff ??? m a xa b minf?a bmaxf27 II. 動態(tài)線性標(biāo)定 (最常用 )：線性標(biāo)定中的參數(shù)隨著迭代次數(shù)的增加而變化時就得到了動態(tài)線性標(biāo)定 優(yōu)點(diǎn)：計算容易不占用時間 函數(shù)表達(dá)式： ， 為迭代指標(biāo) a. 最常用最大化 =1 , 函數(shù)表達(dá)式： 五 .GA的各種變形（ 25） kk bfaf ??? kkk fb ???? m inkakfff ????? m in第 k代的最小目標(biāo)函數(shù)值 28 b. 加入的意義 （同線性標(biāo)定中 ξ 的意義） 加入使最壞個體仍有繁殖的可能， 隨 的增大而減小 c. 的取值： ， ， ， 調(diào)節(jié) 和 ，從而來調(diào)節(jié) 五 .GA的各種變形（ 26） k?k? kk?k?M?0? rkk ?? ?1?? ? ?9 9 ,?rk?M r29 五 .GA的各種變形（ 27） d. 引入 的目的： 調(diào)節(jié)選擇壓力，即好壞個體選擇概率的 差，使廣域搜索范圍寬保持種群的多樣性，而 局域搜索細(xì)保持收斂性。一般來說，算法開始時應(yīng)注重廣域搜索，通過使用較小的選擇壓力來實(shí)現(xiàn)；隨著迭代的進(jìn)行，逐步偏重于局部搜索，通過使用較大的選擇壓力來實(shí)現(xiàn)。 五 .GA的各種變形（ 21） 24 II. 局部搜索、廣域搜索與選擇壓力的關(guān)系 局部搜索與廣域搜索是 GA中的一對矛盾，只注重局部搜索很可能陷入局優(yōu)，只注重廣域搜索則會導(dǎo)致精確開發(fā)能力不強(qiáng)。 五 .GA的各種變形（ 19） ? ?? ?aUxfXZ,0???????22 適值函數(shù)的標(biāo)定
數(shù)學(xué)相關(guān)推薦
鄂ICP備17016276號-1