【正文】 . 背包問題 ? 解碼法 —— FF Heuristic（優(yōu)先適合啟發(fā)式） 解碼法是修復程序（修復可行性的方法） ? 步驟 a. 將選上物品按 pi /wi 降序排列 b. 選前 K個物品，使 例 ： → 降序排列： 2， 1， 6， 5 → → 五 .算法應用 ???????111kiiikiii xwWxw(1 1 0 0 1 1 0 )x ?2 1 2 1 6w w W w w w? ? ? ? ?(1 1 0 0 0 0 0 )x ?88 1. 背包問題 ? 順序編碼法 ? 步驟 a. 隨機產(chǎn)生一個項目順序 ，即保留項目 順序的前 k位，使 五 .算法應用 ? ?12, , , nx x x?? ?????111kiiikiii xwWxw89 1. 背包問題 ? 順序編碼法 例： n=7 用順序 ( 3 2 5 1 4 6 7 )表示選擇物品的順序，用優(yōu)先適合啟發(fā)式保留前 k位，使解可行 由于 k=3， (3 2 5) 五 .算法應用 ?? ?????111kiiikiii xwWxw 1523523wW ???????編碼長度是可變的，如何做交叉和變異 ? 90 1. 背包問題 ? 順序編碼法 ? 插入式交叉 a. 在 P1上選一個隨機的斷點 b. 在 P2上隨機選一個基因片斷插入 P1的斷點處 c. 去掉 P1上的重復基因 d. 按優(yōu)先適合啟發(fā)式得到可行解 五 .算法應用 91 1. 背包問題 ? 順序編碼法 ? 插入式交叉 例 ： 五 .算法應用 去掉重復基因： 3 2 166。 4 6 166。 1 5 可行嗎 ？選 5時背包裝 不 下 ，去掉 5，則 3 2 4 6 1 P1 3 2 166。 1 5 4 3 2 166。 4 6 166。 1 5 4 P2 1 2 166。 4 6 166。 3 5 X 92 1. 背包問題 ? 順序編碼法 思考： ？ b. 二進制編碼時，編碼空間與解空間的對應關系如何？ c. 變長順序編碼時，編碼空間與解空間的對應關系如何？ 五 .算法應用 93 2. 最小生成樹 ? 問題的提出 難點：對于下面的紅色的圖形，如何設計一個合適的編碼方法？ 五 .算法應用 1 2 3 4 5 6 1 2 4 3 5 7 6 8 9 10 94 2. 最小生成樹 ? 傳統(tǒng)的編碼方法 ? 節(jié)點表示法 {(1,2),(2,3),(2,5),(2,6),(4,6)} 無法避免回路 五 .算法應用 1 2 3 4 5 6 1 2 4 3 5 7 6 8 9 10 95 2. 最小生成樹 ? 傳統(tǒng)的編碼方法 ? 邊編碼法 {1,2,4,5,10} 無法保證是樹，無法保證可行性 五 .算法應用 1 2 3 4 5 6 1 2 4 3 5 7 6 8 9 10 傳統(tǒng)編碼缺點：麻煩，無法做遺傳運算，無法保持合法性 96 2. 最小生成樹 ? 傳統(tǒng)的編碼方法 ? 邊編碼法 {1,2,4,5,10} 無法保證是樹，無法保證可行性 五 .算法應用 1 2 3 4 5 6 1 2 4 3 5 7 6 8 9 10 為解決以上問題，人們提出了 Pr?fer數(shù)編碼方法 97 2. 最小生成樹 ? Pr?fer數(shù)的定義：用 n2位自然數(shù)唯一的表達出一棵 n個節(jié)點的生成樹，其中每個數(shù)字在 1和 n之間，而且交叉變異仍是一棵生成樹 ? 葉子：樹中度數(shù)為 1的節(jié)點 例 ： 1， 3， 4， 5 五 .算法應用 1 2 3 4 5 6 98 2. 最小生成樹 ? Pr?fer數(shù)滿足生成樹的要求 ? 覆蓋所有節(jié)點 ? 連通的 ? 沒有回路 五 .算法應用 1 2 3 4 5 6 99 2. 最小生成樹 ? 編碼步驟 a. 設節(jié)點 i是標號最小的葉子 b. 若 i與 j相連，令 j是編碼中的第一個數(shù)字 c. 刪去邊 (i , j) d. 轉(zhuǎn) a,直到剩下一條邊為止 五 .算法應用 1 2 3 4 5 6 100 圖解： i=1, ( i , j )=(1,2), j=2。 i=3, ( i , j )=(3,2), j=2 i=4, ( i , j )=(4,6), j=6。 i=5, ( i , j )=(5,2), j=2 編碼：（ 2 2 6 2） 1 2 3 4 5 6 2 3 4 5 6 2 4 5 6 2 5 6 2 6 101 2. 最小生成樹 ? 解碼步驟 a. 令 Pr?fer數(shù)中的節(jié)點集為 P ,不包含在 P中的節(jié) 點集為 P’ ； b. 若 i為 P’中最小標號的節(jié)點， j為 P上最左邊數(shù) 字連接邊 (i , j)，并從 P’中去掉 i，從 P中去掉 j， 若 j不再在 P中，將 j加入 P’中 c. 重復 b，直到 P中沒有節(jié)點 (即為空 )， P’中剩下 (s,r) d. 連接 (s,r) 五 .算法應用 102 圖解： P= { 2, 2, 6, 2 } P’= { 1, 3, 4, 5 } (1,2) P= { 2, 6, 2 } P’= { 3, 4, 5 } (3,2) P= { 6, 2 } P’= { 4, 5 } (4,6) P= { 2 } P’= { 5, 6 } (5,2) P= { Ф } P’= { 6, 2 } (6,2) 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 103 2. 最小生成樹 ? 最小生成樹的的優(yōu)點 ? 對于一個 n個節(jié)點的 Pr?fer數(shù)的個數(shù)為 ， 生成樹的個數(shù)也是 ? 最小生成樹實現(xiàn)了解空間和編碼空間的一一對應，交叉變異不破壞合法性 五 .算法應用 2nn?2nn?一個好的編碼方法對遺傳算法至關重要 104 1 7 6 5 2 3 4 作 業(yè) 對上圖中的生成樹進行編碼，要求給出完整編碼過程 105 1 7 5 P= { 6, 3, 2, 4, 4 } P’= { 1, 5, 7 } 4 2 3 6 作 業(yè) 對上面的 Pr?fer數(shù)編碼進行解碼，要求給出完整的解碼過程 106 1. 編碼是成功的關鍵 (如最小樹問題 ) ① 最好能使編碼空間與解空間一一對應 ② 減少編碼冗余，編碼應盡可能短 ③ 便于遺傳運算 —— 有利于保持合法性、可行性；實在沒有辦法保持，要設計合理的修復程序，盡可能保持父輩的特征。 六 .學習遺傳算法的幾點體會 107 2. 遺傳算子的設計有最大的創(chuàng)新空間 3. 選擇壓力的調(diào)整使多樣性和收斂性得到合適的分配。開始時多樣性重要，重廣域搜索；剛要結(jié)束時收斂性重要，重局域搜索。 調(diào)整方法：適值函數(shù)的構(gòu)造；合適的標定方法 六 .學習遺傳算法的幾點體會 108 4. 在 GA的研究中我們要做一些什么 ① 擴大 GA的應用 , GA應用面廣，適應性最好 ② 算法改進方向的研究 ③ 理論研究 ④ 算法開發(fā)中的幾個技術 (見下頁 ) 六 .學習遺傳算法的幾點體會 109 I. 參數(shù)整定：經(jīng)驗加反復試驗 (Tuning) 如： Pc， Pm， NG， NP幾種參數(shù)的選定 II. 判斷好壞算法的辦法： ⑴ 快 ⑵ 能解的問題大 ⑶ 達優(yōu)率高，大問題 50%的達優(yōu)率 六 .學習遺傳算法的幾點體會 110 III. 算例的選擇： ⑴ 自己編的 —— 沒有說服力，但可以解釋算法 ⑵ 隨機產(chǎn)生的 —— 適合沒有前例的例子 ⑶ 文獻的例子 —— 面較大 ⑷ 網(wǎng)上的例子 —— 典型問題 QAP,TSP 六 .學習遺傳算法的幾點體會