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

基因遺傳演算法介紹及應用研研 究究 生：葉彥伯生：葉彥伯 指導教授：施指導教授：施 明明 璋璋 教授教授日日 期：期：2007/05/012007/05/01歷史 1960年John Holland提出以基因遺傳法則來解決數學尋優問題，遺傳演算法就是利用基因遺傳的原則寫出來的程式。達爾文的物種進化論就說明了物競天擇、強者生存物競天擇、強者生存的競爭原則。遺傳演算法常用於數學尋優、模糊邏輯控制器的設計及類神經網路權重之搜尋。為什麼需要遺傳演算法1.避免陷入局大質或局小值ex：梯度尋優2.可同時進行多變數的尋優3.自由度極高基因遺傳演算法步驟(1)隨機選定初始族群(2)計算每個基因的適應性函數(3)要不要停止運算?停止的條件為何?(4)開始遺傳法則，透過運算找出新世代(5)(a)利用輪盤法選出較佳的基因(b)隨機交配(c)隨機突變(6)(5)保留最好的基因至下一代(7)(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）。一般文獻記載認為雙點交配其效果較好，這是統計上的結果。雙點交配21001 011035 0111 0011隨機產生交配點為2、6210|01 01|1035 01|11 00|11新的子代舊的子代21011 001035 0101 0111在此一般設定的交配率為0.51突變在選取複製及交配後，在整個族群中，無法涵蓋其他完全同於雙親的新一代成員，在廣泛搜尋最佳值的過程中，只在舊一代之基因碼內複製交配，容入最佳局部解之陷。突變的好處是產生新品種，使搜尋最佳值時，不會陷在局大值或局小值。突變前 1001 0|110突變後 1001 1|110在此一般設定的突變率為0.030.08基因演化程變數產生程基因遺傳演算法範例1尋找的最小值Best fitness for MIN.problem is(-18.55472108)x=9.03899000 y=8.66819400尋找的最大值x=-0.00157200y=0.00034800z=0.00016700Best fitness for MAX.problem is(78.99999738)範例2車電子控制主動式懸吊系統示意圖：（1）（2）（3）（4）系統架構及數學模式 範例3系統變數區段式模糊的控制方塊圖:ex：設計Fuzzy控制器之Gain值為系統變數，探討其對系統的影響在此利用平方誤差積分準則ISE令目標函數定義為目標函數模糊歸屬函數與邏輯規則表歸屬函數:模糊規則表:Department of Mechanical Engineering,National Cheng-Kung University,Taiwan GA Fuzzy 控制器模糊控制方塊圖:Ge=3.01539400Gv=1.85172500Gu=0.41446600Best fitness is(723.5479101)GA Fuzzy 控制最佳化結果最佳化值與手調值之比較fuzzy控制器 凸波路面 路面起伏40mm 車速80km/hr區段式模糊控制方塊圖:區段式GA Fuzzy 控制器Ge1=3.94331900Gv1=70.94448500Gu1=0.91635200Ge2=2.24012400Gv2=28.74675000Gu2=0.96437700Ge3=0.65921200Gv3=26.99616900Gu3=0.89149200Best fitness is(755.8842233)區段式GA Fuzzy 控制最佳化結果最佳化值與手調值之比較區段式fuzzy控制器 凸波路面 路面起伏40mm 車速80km/hrEnd