基因遗传演算法介绍和应用.ppt

基因遺傳演算法介紹及應用 研 究 生：葉彥伯 指導教授：施 明 璋 教授 日 期：2007/05/01 * 歷史 1960年John Holland提出以基因遺傳法則來解決數學尋優問題，遺傳演算法就是利用基因遺傳的原則寫出來的程式。 達爾文的物種進化論就說明了物競天擇、強者生存的競爭原則。 遺傳演算法常用於數學尋優、模糊邏輯控制器的設計及類神經網路權重之搜尋。 為什麼需要遺傳演算法 1.避免陷入局大質或局小值 ex：梯度尋優 2.可同時進行多變數的尋優 3.自由度極高 基因遺傳演算法步驟 隨機選定初始族群 計算每個基因的適應性函數 要不要停止運算?停止的條件為何? 開始遺傳法則，透過運算找出新世代 (a)利用輪盤法選出較佳的基因(b)隨機交配(c)隨機突變 (5) 保留最好的基因至下一代 (6) 繼續步驟(2) 基因遺傳演算法介紹 基因遺傳演算法 基因演化流程 變數產生流程 基因遺傳演算法 系統變數 區段式模糊的控制方塊圖: ex：設計Fuzzy控制器之Gain值為系統變數，探討其對系統的影響 基因編碼 基因演算法中，用來表示特性的就是染色體編碼。把參數編成二進位數， 稱二進位基因演算法(Binary Genetic Algorithms，簡稱BGA) 十進位 二進位(7 bits) 0 000 0000= 0 10 111 1111= 127 換算公式為 其中 B為二進位換成十進位數 UB為基因最大數 LB為基因最小數 L為字串編碼長度(bit length) x為基因的實數值 目標函數 適應函數是用來評估每個染色體所代表之解答的好壞，即其適應度。通常適應函數即為最佳化問題的目標函數。 選取與複製 基因演算法中的選取機制是模擬自然界適者生存的現象，適應度高的染色體存活率較高，而適應度低的染色體存活率相對就較低。因此，適應度較高的染色體所擁有後代有可能比較多。如果有某一個染色體適應度明顯高於其他的染色體，就有可能藉著世代替換，而逐漸成為這個族群的主體。 選取的方式，以輪盤式(Roulette Wheel Selection)以適應值觀點來看，其適應值越大者所占面積也就越大，每個物種在輪盤上所佔有的面積比例也就是代表其被挑選至交配池的機率；然後隨機地選取輪盤上的一點，其所對應的物種即被選中送至交配池中。 輪盤法 以賭輪盤的方式來看，把一個輪盤分成若干扇形，面積越大的編號，越容易中獎，因此獎金會比較低。以適應性函數觀點來看，其值越大者所佔的面積就越大，其選中的機率就越大。 交配 交配方式有許多種，最常用的三種為單點交配（Single-point crossover）、雙點交配（Double-point crossover）以及均等交配（Uniform crossover）。一般文獻記載認為雙點交配其效果較好，這是統計上的結果。 雙點交配 1001 0110 5 0111 0011 隨機產生交配點為2、6 10|01 01|10 5 01|11 00|11 新的子代 舊的子代 1011 0010 5 0101 0111 在此一般設定的交配率為0.5~1 突變 在選取複製及交配後，在整個族群中，無法涵蓋其他完全不同於雙親的新一代成員，在廣泛搜尋最佳值的過程中，若只在舊一代之基因碼內複製交配，容易落入最佳局部解之陷。 突變的好處是產生新品種，使搜尋最佳值時，不會陷在局大值或局小值。 突變前 1001 0|110 突變後 1001 1|110 在此一般設定的突變率為0.03~0.08 基因演化流程 變數產生流程 基因遺傳演算法 範例1 尋找 的最小值 Best fitness for MIN. problem is (-18 x = 9 y = 8尋找 的最大值 x = -0y = 0z = 0.00