【正文】 1 5 可行嗎？ 選 5時(shí)背包裝不下，去掉 5 3 2 4 6 1 3 2 166。 缺點(diǎn)：這種方法將花費(fèi)較多的時(shí)間在適應(yīng)值的 排序 上。 ? ?? ??01112????????????YXZYXZ1x 2x3x 4x1x? 2x?3x?4x?1P2P? ?? ?nkknkkyyyyyYxxxxxX,121121????????20 II. 變異 a. 位值變異： 任選一位加 Δ（ 變異步長(zhǎng)）， 例： 五 .GA的各種變形（ 18） ? ? ? ? ? ?ao r Naao r UaU ,0,0 ???? ?? ?nknkxxxxZxxxxX????,2121????21 b. 向梯度方向變異 缺點(diǎn)：只能用于目標(biāo)函數(shù)可微的問題。 7 6 1C2C 2 1 166。 6 7 2 1 166。1 第三章 遺傳算法 2 ?五 .遺傳算法的各種變形 ? ? ? (Scaling) ? ? ?六 . 應(yīng)用 遺傳算法 3 其它編碼方法 ① 順序編碼：用 1到 N的自然數(shù)的不同順序來 編碼，此種編碼不允許重復(fù)，即 且 ，又稱自然數(shù)編碼。 3 4 5 166。 3 4 5 166。 例 :對(duì)于最大化問題可采用如下操作： 優(yōu)點(diǎn)：考慮到了問題本身的性質(zhì)，效率較高。 五 .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é)。 1 5 4 3 2 166。 4 6 166。每人的選擇概率為 1／ 50，有平均 2個(gè)機(jī)會(huì)。 約束是個(gè)凸集，可行性可以保持，但是分散 性太差，又出現(xiàn)了向中間匯集的問題。 3 4 5 166。 1 2 5 166。 該法適用范圍很廣：指派問題、旅行商問題和單機(jī)調(diào)度問題等等。 7 6 1C2C 2 1 166。 6 7 166。但染色體種群也可能因此而趨于聚集，導(dǎo)致種群的多樣性較差。 五 .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)定來調(diào)節(jié)選擇壓力，采用 旋輪法 來共 同完成種群的選擇。 4 6 166。 六 .應(yīng)用（ 6） ? ?xP 0??? Wxw ii???? ??niii Wxw10 ? ? 10 ?? xP?47 b. 解碼法 —— First Fit Heuris