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