基因演算法 介紹.ppt

基因演算法 介紹 想像非洲的草原 羚羊 與 豹 之間的生態 大自然有選擇的機制 淘汰較弱的個體 讓適應環境的個體有機會繁衍下一代 演化式計算 的概念 Basic EC-cycle 基因演算法 1975年 John Holland 學者所提出 成為非常著名的演算法 Genetic Algorithm (GA) 基因演算法 又稱: 遺傳演算法 基因演算法的概念 將問題編碼成 染色體的型式 基因: 0 or 1 染色體: x = 0 1 0 0 1 1 0 設計 適應函數 (fitness function) f(x) :適應函數，給一 x 可得一 適應值 f(x) 適應值愈高, 表愈適應環境 基因演算法三個基本動作 選擇(Selection)與複製 (Reproduction)： X = 0 1 0 0 1 1 0 選擇 適應值高 之染色體 複製成多個染色體 基因演算法三個基本動作 交換 (crossover)： 父：0 1 0 0 1 1 0　　　　0 1 1 1 0 1 0 母：1 0 1 1 0 0 1 　　　 1 0 0 0 1 0 1 基因演算法三個基本動作 突變 (mutation)： 0 1 0 0 1 1 0 演算法步驟 Step1：隨機產生N個染色體 Step2：利用適應函數算出每個染色體的適應值 Step3 : 選擇與複製: 選擇 適應值高 之染色體 複製成多個染色體 Step4：利用交換及突變的動作產生新的染色體 Step5：測試新染色體的適應值是否達到門檻值 是：則 停止 否：則 Go to Step3 範例1 假設 x 在 (0,31) 之間，y = x2，求 x = ? ，y 可得最大值 將問題編碼成 基因的型式 x :　0 0 0 0 0～1 1 1 1 1 設計 適應函數 (fitness function) f (x) = y = x2 範例1 Step 1, 2, 3 取4組染色體　 x　 f (x)　 f (x) /m　 複製個數 0 1 1 1 0　　　(14)　　196　　 0.71　　　1 1 1 0 0 0　　　(24)　　576　　 2.07　　　2 1 0 0 0 1　　　(17)　　289　　 1.04　　　1 0 0 1 1 1　　　( 7)　　 49　　 0.18　　　0 範例1 Step 4.1 交換 　　 x　　　 f (x) 0 1 1 1 0　　　　　0 1 0 0 0　(8)　　　82 = 64 1 1 0 0 0　　　　　1 1 1 1 0　(30)　　302 = 900 1 1 0 0 0　　　　　1 1 0 0 1　(25)　　252 = 625 1 0 0 0 1　　　　　1 0 0 0 0　(16)　　162 = 256　　　　 　 範例1 範例1 Step4.2突變 (機率0.1) 4個染色體 × 5個基因 = 20個基因 20 × 0.1 = 2 　　有2個基因要突變 1 st：0 1 0 0 0 ?　 0 1 1 0 0 (12) 　　　　第一個染色體之第3基因突變 3 rd：1 1 0 0 1 ? 　1 0 0 0 1 (17) 　 第三個染色體之第2基因突變 　　　　 範例1 Step5 停止條件有三種可能方法： 設定繁衍代數 (ex：1000代) 收斂 (ex：最佳適應值已50代未改進) 適應值達到門檻 否則，Go to Step3 編碼（coding）-1 運用基因演化算法的目的是求問題的解，在初始階段的編碼步驟是把與問題相關變數的值（或稱為問題解）以特定編碼的方式將其組合成一條染色體 （chromosome，或稱為字串string），每一條染色體即代表一可能的問題解答， 最簡單而且被廣泛使用的是標準二進位編碼法 （Standard binary encoding）。這種編碼法是將染色體內的每個基因用二進位碼{0，1}來表示，而編碼後的染色體即是一串由01組合字串（string）。 適應函數 根據問題的特性來定義染色體生存的壓力 (selection pressure)，意即作為基因演算法中「適者生存」的選擇標準。 當其適應值愈高時，表示該染色體所代表的解愈趨近好的解 因此在演化過程中存活的機率愈高(selected to live)；反之，該染色體可能遭遇被淘汰的命運(selected to die)。 選擇與複製 (輪盤法) Step1：Random挑出4個基因組(染色體) Step2：　　x　　　　　　　 f(x)