1、,資料庫行銷基因演算法,授課教授 周世玉 教授研究生 包栯綺 王常翰 葉家祺,大量借用自生物領域，建立在類比生物思考過程上似進化過程- 物競天擇，適者生存 增加個體對環境的適應性來解決問題，即考慮個體加權數，用在訓練過程，若得到的適應性越高，則可視為基因演算法的預測能力越高被應用在三個領域：訓練類神經網路(最常被應用)、生成記憶基礎理解的評分函數、排程的最適化功能,基因演算法 (Genetic Algorithms),與自然界不同的是，母群體的數量是保持恆定，即該群體不致滅種規則導向，而非資料導向在同一個函數中加入許多限制條件做最適化運算在資料採礦及資料分析上並不普遍，因為資料採礦著重分類、預
2、測，而不是最適化如果問題中的限制比變數還多時，基因演算法是個好工具,特性,1950 生物學家和電腦學家合作，模擬基因運作1960初 學者電腦化的遺傳學- 染色體、基因、配 對基因、適配函數，應用到其他領域(約翰 賀藍)1967 論文描述最適化技術，但過於倚賴隨機選擇而受質疑1970 發展出這項技術的理論基礎，即如何運作,基因演算法的演進過程,1.設定問題定義基因組及適配函數，創造第一代基因組(五位元基因參數，ex: 01111)2.藉由選擇、交配及突變來修訂起始群體3.重複步驟2，直到這個群體不再進步為止藉由適配函數的值不斷改善，得到一個基因組及一組適配值,基因演算法的過程,案例配適函數 (f
3、itness function): 31p-p2 , p為031的整數F.O.C 令f(p) = 31- 2p=0 p=15.5 15,16S.O.C f” (p) = -2 0 有最大值 將母體中適者的基因組最大化,選擇 (selection),三個運算元修訂起始群體,保持母體個數不變(物種不滅)，但新一代的適合度會比上一代更好。有較高的適合度基因會存活(深色)，增殖而陰影部份的基因死亡,三個運算元修訂起始群體,交配 (crossover)突變 (mutation),2 個基因結合的方式。基因交配的位置決定了基因分裂與再度重組,基因在某個位置上突然的改變，這會出現與原先母體不曾有過的特徵,生
4、存是建立在依照比例再任意選擇基因組的基準上在輪盤上，各個基因組所佔的面積與其適配值成正比(輪盤法則),被選中的機率=176/471,= 37.4% x 4,= 31*22-222,平均配適度471/4= 117.75,選擇過程,平均配適度117.75 140提升22.25,被選中的機率較低,被選中的機率較高,平均配適度117.75 178.5提升60.75,新產生的基因組子嗣 (children)隨機決定是否交配基因交配機率 (crossover probability),選擇和交配後,選擇後,突變可以改善物種適應性，但也往往是毀滅性的結果。,178.5 155.5降低 23，但比起起始的母群
5、體，仍提升37.75,小結,基因演算法的主要方式是選擇與交配，突變是次要因素，為的是避免過早得到最適化(局部)的結果。基因演算法作為資料採礦的工具之一，最佳的解決方案不一定容易獲得，但卻可以逼進最佳解決方案。與其他資料採礦及最適化技術不同之處，在於其只管0與1二個符號排列成哪一種基因組，卻不在意這些位元所代表的值是多少，只有在以上的適配函數中其值有意義,目的：用來解決資源在種種限制下如何分配的問題安排醫院內40名住院醫生的門診排班表排班方式需兼顧：門診部隨時有人駐守門診部內，需同時有相同數目的第一年、第二年、與第三年住院醫生第三年住院醫生平均每天看8個病人，第二年住院醫生看6個病人，第一年住院
6、醫生看4個病人每名住院醫生還必須花4個星期的時間負責一些工作 (如：加護病房、腫瘤小組、社區醫院)資深住院醫生輪到負責加護病房時，不需要再到門診看診，但其它醫生則不然資淺的醫生輪到負責心臟護理時，不需要再到門診看診，但其它醫生則不然不可以安排多於2位當天需要至加護病房的住院醫生至門診看診不可以安排多於3位當天有其它輪值的住院醫生至門診看診,個案研究(一),個案研究(二),反適配函數 適配值越高，排班表就越糟當某天門診的醫生少於3位時，適配值會因這個錯誤大大增加當某天門診沒有資深住院醫生時，適配值會略為增加如果某天只有不到3名醫生出外輪值，適配值會大為增加結果：平均適配值13014072,為什麼
7、交配只選擇1個節點?,為什麼突變的機率如此低?,為什麼不用2個 或3個節點做 交配?,基模,在希臘文是形式、外型之意。這裡指的是基因組中的型態。組成0 與 1 (固定位置)* (其他部分，表示0或1)Ex. 1*100*0*1基模與基因組的關係固定位置有對應到，即吻合。Ex.基模: 10* 基因組: 1000 1001 1011 1010,基模(Schema),基模的序號(Order)固定位置符號(1和0)的數目。 Ex.1*10111的序號是6基模的定義長度(Defining length)最外圍的兩個固定位置符號的距離Ex.1*10111的定義長度是 7-1=6 *1010*1的定義長度是
8、 10-4=6 0*的定義長度是 1-1=0,基模(Schema),基因組000傳遞給下一代，則其所有吻合的基模也存活下來。(包括基模0*、*0*、*00、0*0、*0、*等)基模的適配值=(N個基因組適配值總和)/Nf,基模 & 適配值,基模: 10*， 00*,選擇,基模(Schema),這一面的基模是*0,011,111,110,010,000,100,101,這一面的基模是1*,這一面的基模是*1*,*11,11*,*10,01*,0*0,1*0,*00,10*,1*1,頂點=序號為3的基因組 邊=序號為2的基模 面=序號為1的基模 立方體=序號為0的基模,基基模定理(或基因演算法基礎
9、理論)簡短、低序號和高適配值的基模在繁衍下一代過程中，較容易生存下來，為基因演算法的運作基石(building blocks) 。,基模定理(Schema Theorem),基模: 1*1， 10*,交配,不確定平行理論(Implicit parallelism)若每一代有n個不同的基因組，則需處理n3個基模。只含有2個符號(0和1)較好的原因,基模定理(Schema Theorem),00,11,10,01,00,11,10,01*0,*1,1*,0*,*,類神經網路 & 基因演算法,2,0,4,3,1,5,W24,輸出節點,W23,W14,W13,W04,W03,W36,W45,輸入節點1
10、,輸入節點3,輸入節點2,10110001,不需要確實了解類神經網路如何運作這些加權值組成一個基因組基因演算法才能將其最適化,每個加權值介於0與1之間，是由許多位元組成。,適配函數比較預測的輸出值與實際的輸出值當差異(錯誤)為0時，即為完美的預測基因演算法即求此函數的最小值,類神經網路 & 基因演算法,適配函數決定加權值在系統內的比重,基因演算法利用選擇、交配和突變訓練母群體,產生極佳預測效果的類神經網路,群聚(crowding)基因演算法不足之處在於，這一代的整個群體會完全被下一代取代群聚使被取代的目標通常是相似性較高的次群體成對(diploid)染色體演算特性跟單倍染色體差不多，均有選擇、交配和突變不同之處在於每個基因都有另個成對的基因若兩者相同，就沒問題；若不相同，則加入顯性訊息於其中一個Ex.一個藍眼睛基因與個棕眼睛配成對時,簡易演算法之外,產生可解釋的結果結果易於應用可以處理的資料類型範圍極大可以用在最適化(optimization)的問題上和類神經網路結合容易,基因演算法的優點,許多問題有編碼(encoding)上的困難不保證最適化運算成本極高可以運用的商業套裝軟體不多,基因演算法的缺點,THE ENDThanks for listening!,
