Posted on August 18, 2003 in Genetic Algorithms by pestNo Comments »

ç¾ä»Šå……斥於電影或是電玩中的人物或角色,大多都無法é¿å…è¦èµ°å¾—"åƒäºº";當傳統的方法ç¹ç‘£è€Œç¼ºä¹å½ˆæ€§ï¼ŒåŸºå› æ¼”算法å†ä¸€æ¬¡ç‚ºå‹•畫製片指出一æ¢ç°¡å–®æ˜“用的路…。


傳統上,è¦åšå‡ºå‹•畫中的人物走路的畫é¢ï¼Œé€šå¸¸éƒ½éœ€è¦ä»”ç´°æè¿°æ¯å€‹ç•«é¢æ€Žéº¼èµ°ã€æˆ–æ˜¯æŠŠçœŸäººçš„å‹•ä½œæ‹æ”下來å†è¼¸å…¥é€²åŽ»ã€‚ç„¶è€Œé€™ç¨®åšæ³•太ç¹ç‘£ä¹Ÿç¼ºä¹å½ˆæ€§ï¼Œæ‰€ä»¥ Torsten Reil 決定é‹ç”¨åŸºå› æ¼”算法,來教導他的人物走路。

首先必須建立環境;把é‡åŠ›å’Œäººç‰©çš„è‚Œè‚‰çµæ§‹éƒ½åšå¥½é—œé€£ä¹‹å¾Œï¼Œæ¯ä¸€å€‹è§’è‰²æœ‰ä¸ƒç™¾çµ„åƒæ•¸å¯ä»¥èª¿æ•´ã€‚ä»–é€éŽé¡žç¥žç¶“網路來控制肌肉的é‹å‹•,但是由於系統實在太複雜而ä¸å¯èƒ½é€éŽäººä¾†èª¿æ•´ï¼Œæ‰€ä»¥é€™æ™‚å°±å¯ä»¥å°Žå…¥åŸºå› æ¼”算法來訓練。

由於系統中有é‡åŠ›ç­‰æ¢ä»¶ï¼Œæ‰€ä»¥ç³»çµ±è©•分的方法就採用人物走的步數來評分;走越多步的就越好,直到它跌倒為止。剛開始系統中的人物大都走ä¸äº†ä¸€æ­¥ï¼Œä½†è‡³å°‘æœ‰äº›æœƒæ¯”å…¶ä»–æ™šä¸€äº›å€’ä¸‹ï¼Œé€™äº›è¡¨ç¾æ¯”較好的個體會被複製二å份,å†åšä¸€äº›ç´°å¾®çš„çªè®Šæ”¾åˆ°ä¸‹ä¸€ä»£ã€‚åŒæ™‚系統也會å†ç”¢ç”Ÿå…«å個新的個體加入賽局。

但是由於評分標準是採用走的步數,所以有些角色就會發展出奇怪的走法,例如仆ä¼å‰é€²æˆ–是翻筋斗之類的,所以他å†é€²ä¸€æ­¥æŠŠéŠæˆ²è¦å‰‡åР入䏀æ¢ï¼Œå°±æ˜¯é‡å¿ƒä¸èƒ½ä½Žæ–¼æŸå€‹é«˜åº¦ã€‚

ç¶“éŽäºŒå回åˆï¼Œç³»çµ±å·²ç¶“能夠產生走得éžå¸¸é †æš¢çš„角色了;我們ä¸éœ€è¦çŸ¥é“它內部的類神經網路怎麼排列,但å¯ä»¥ç¢ºå®šçš„æ˜¯æ¼”化的力é‡å†ä¸€æ¬¡çš„快速替我們找到一個解答。

《本文摘譯自:Darwin in a Box》

相關網站:
Active Character Technology (有 Demo 短片)
Endorphin, å¯ä»¥è‡ªå‹•產生出動畫人物動作的軟體 (Demo)

Posted on June 26, 2003 in Genetic Algorithms by pestNo Comments »

今天在看 PostgreSQL çš„æ–‡ä»¶æ™‚ï¼Œç™¼ç¾æœ‰å€‹ç« ç¯€åœ¨è¬›é‹ç”¨åŸºå› æ¼”算法(Genetic Algorithms) 來最佳化資料庫的查詢方法(Query Plan),就來介紹一下 PostgreSQL 是如何應用的。

所謂的 Query Plan(查詢方法),是指資料庫管ç†ç¨‹å¼å¦‚何由ç¾å­˜çš„ Table 中,åšå‡ºä½¿ç”¨è€…想è¦çš„資料。Query Plan中最難以處ç†çš„æ˜¯ Join 這個動作。Join 這個動作,簡而言之就是把兩個相關的 Table åˆæˆä¸€å¼µå¤§çš„ Table;例如我們有一個 Table 記錄 "人å-å±…ä½åŸŽå¸‚",å¦ä¸€å€‹"人å-喜好"ï¼Œä»Šå¤©å¦‚æžœæˆ‘å€‘è¦æ‰¾å‡º"ä½å°åŒ—ã€åˆå–œæ­¡å¯« Blog"的人,就å¯ä»¥åˆ©ç”¨ Join 這個指令,以人åç•¶ä½œç´¢å¼•å€¼ï¼Œåˆæˆä¸€å¼µåŒæ™‚具有我們所需è¦è³‡æ–™çš„ Table。

Join 有很多種方法å¯ä»¥åšåˆ°ï¼Œæœ€å·®çš„ç‹€æ³å°±æ˜¯æŠŠæ‰€æœ‰çš„å¯èƒ½æ€§éƒ½åˆ—出來,å†åˆªæŽ‰ä¸æ­£ç¢ºçš„。舉例來說,ä½å€ Table 有一åƒç­†ï¼Œå–œå¥½è³‡æ–™ä¹Ÿæœ‰ä¸€åƒç­†ï¼Œé‚£éº¼å°±å…ˆç”¢ç”Ÿä¸€ç™¾è¬ç­†çš„表格,å†ä¸€ä¸€åˆªåŽ»ï¼›ç›¸å°çš„,如果我們知é“人å都沒有é‡è¦†ã€å±…ä½åŸŽå¸‚表格中,åŒä¸€å€‹äººä¹Ÿåªæœƒæœ‰ä¸€ç­†è³‡æ–™ã€æ¯å€‹äººä¹Ÿåªæœ‰ä¸€å€‹å–œå¥½ï¼Œé‚£éº¼ç”šè‡³å¯èƒ½å¹¾åƒç­†å°±åšå‡ºä¾†äº†ã€‚

但䏦䏿˜¯æ¯ä¸€å€‹ Query Plan éƒ½æ˜¯å¦‚æ­¤çš„é¡¯è€Œæ˜“è¦‹ï¼Œç•¶éœ€è¦æ¯”å°çš„ Table 越來越多,到底是先 Join 哪一個 Tableã€å…ˆ Join 哪兩個 Join å®Œçš„çµæžœï¼Œæœƒè®Šæˆä¸€å€‹éœ€è¦æŠŠå…¨éƒ¨çš„å¯èƒ½æ€§éƒ½åˆ—出來,æ‰çŸ¥é“哪個最好的å•題,我們稱這種解法å«åš"窮盡æœ"(Exhaustiive Search)ï¼Œæ„æ€å°±æ˜¯å¾—把所有的組åˆéƒ½æ‰¾å‡ºä¾†æ‰è¡Œã€‚

更慘的是 Query Plan 的數é‡åˆéš¨è‘— Table çš„å¢žåŠ è€Œå¤§å¹…å¢žåŠ ï¼Œç•¶éœ€è¦ Join çš„ Table 由兩個變三個ã€å››å€‹ç”šè‡³åˆ°å幾個時, Query Plan 的總é‡å°±åƒ 1*2*3*4 這樣呈指數æˆé•·ï¼Œåˆ°æœ€å¾Œè¦æ‰¾å‡ºæ‰€æœ‰çš„å¯èƒ½è§£ç­”本身所花的時間,æžä¸å¥½éƒ½æ¯”資料庫查詢時間來得長了。

在德國的 University of Mining and Technology 自動控制學院設計了一個電力控制系統,用 PostgreSQL 來當作決策系統的資料庫,但是因為決策系統需è¦é‹ç”¨å¤§é‡çš„ Join 來進行推ç†çš„é‹ç®—,為了兼顧效率,他們把基因演算法引入資料庫的設計之中,用來快速產生有效率的 Query Plan。

關於基因演算法的基本概念在此略éŽï¼Œè«‹åƒè€ƒæœ¬ç«™ç›¸é—œæ–‡ç« ã€‚

Query Plan 最佳化的作法和著åçš„ Traveling Salesman Problem(TSP) å•題很類似,先將å¯èƒ½çš„è§£æ³•è®Šæˆæ•¸å­—的字串,例如 4-1-3-2 就表示先讓 Table 4 å’Œ Table 1 åš Join,å†å’Œ Table 3ã€2 åš Join。

æ¼”åŒ–æ™‚æŽ¡ç”¨ç©©æ…‹æ¼”åŒ–ï¼Œä¹Ÿå°±æ˜¯æ¯æ¬¡åªæŠŠè¡¨ç¾æœ€å·®çš„一個 Plan 淘汰掉;而å­ä»£çš„產生則是é‹ç”¨ "edge recombination crossover[註二]",而çªè®Šçš„æ©Ÿåˆ¶åœ¨é€™è£¡ä¸¦ä¸ä½¿ç”¨ã€‚

é‹ç”¨åŸºå› æ¼”算法,資料庫å¯ä»¥åœ¨åˆç†çš„æ™‚間中找出有效的 Query Plan來進行 Join 的動作,然而除了找出最好的 Query Plan 之外,電腦的的Computation Time也是一個很é‡è¦çš„因素,ä¸åŒçš„åƒæ•¸å°æ–¼ç³»çµ±ä¹Ÿæœƒæœ‰ä¸åŒçš„影響。

從這個例å­å¯ä»¥çœ‹åˆ°åŸºå› æ¼”算法所é‹ç”¨çš„å ´åˆï¼Œé‚„是脫離ä¸é–‹"在åˆç†çš„æ™‚é–“"ã€"複雜度高的狀æ³ä¸‹"ã€"找到åˆç†å¯æŽ¥å—的解法"的特色。

註一:PostgreSQL 是一個 GPL 的資料庫,最早是由 Berkeley 所發展的,如今和 MySQL åŒç‚ºç¶²è·¯ä¸Šæœ€å—歡迎的 GPL 資料庫軟體,官方網站在 http://www.postgresql.org。

註二:關於 edge recombination crossover 的說明,請åƒè€ƒé€™è£¡ã€‚

åƒè€ƒè³‡æ–™ï¼š
Genetic Query Optimization

相關閱讀:
上å¸çš„éˆè—¥â”€åŸºå› æ¼”算法(一)
上å¸çš„éˆè—¥â”€åŸºå› æ¼”算法(二)

Posted on June 4, 2003 in Genetic Algorithms by pest3 Comments »

è·é›¢ä¸Šæ¬¡ä»‹ç´¹åŸºå› æ¼”ç®—æ³•çš„ç¬¬ä¸€ç¯‡å·²ç¶“å¥½ä¹…äº†ï¼Œé‡æ–°å›žé¡§æ‰ç™¼ç¾ä¸¦æ²’有在技巧上é¢èªªæ˜Žå¾—很清楚,所以打算å†ç¹¼çºŒé€™å€‹ä¸»é¡Œï¼ŒæŠŠåŸºå› æ¼”算法åšä¸€å€‹å®Œæ•´çš„介紹…

如果您ä¸çŸ¥é“基因演算法是什麼,建議您å¯ä»¥å…ˆåƒè€ƒä¸Šä¸€ç¯‡ã€‚

å…ˆå‰æåˆ°åŸºå› æ¼”ç®—æ³•çš„åŸºæœ¬æ¦‚å¿µï¼Œä½†æ˜¯è¦æ€Žéº¼å¯«ç¨‹å¼å‘¢ï¼Ÿé¦–先我們先來探討基因演算法的幾個基本元素。

ç¬¬ä¸€å€‹æ˜¯åŸºå› ï¼›æ²’æœ‰åŸºå› ä¾†ç•¶ä½œåª’ä»‹ï¼Œæˆ‘å€‘æ²’æœ‰è¾¦æ³•é€²è¡ŒåŸºå› æ¼”ç®—æ³•ï¼Œä½†æ˜¯è¦æ€Žéº¼è¡¨ç¾åŸºå› å‘¢ï¼Ÿä»¥é›»è…¦ä¸–界而言,最常見的就是 0 å’Œ 1 的組åˆå½¢æˆçš„"Bit String",例如:0010 就是一個四個ä½å…ƒçš„ bit string。用四個ä½å…ƒå°±å¯ä»¥è¡¨ç¾å‡ºå六種基因組åˆï¼Œè€Œä¸åŒçš„基因組åˆåˆå¯ä»¥å°ç…§åˆ°ä¸åŒçš„"表ç¾åž‹"上,例如第一個 bit 表示é¡è‰²ã€ç¬¬äºŒå€‹ bit 表示長度,第三個 bit 表示色調等等。

除了固定長度的基因之外,也å¯ä»¥æŽ¡ç”¨ä¸å®šé•·åº¦çš„基因;例如,å‡å¦‚è¦ç”¨è‹±æ–‡å­—測試是å¦èƒ½å¤ æ¼”化出一本莎士比亞全集,就å¯ä»¥æŽ¡ç”¨ä¸å®šé•·åº¦çš„åŸºå› ï¼Œè®“èŽŽå£«æ¯”äºžå…¨é›†ç”±æœ€æ—©çš„è‹±æ–‡å–®å­—é€æ¼¸é•·åˆ°åŽšåŽšæ•¸æœ¬æ›¸é€™éº¼å¤§ã€‚

利用é©åˆçš„åŸºå› è¡¨é”æ–¹å¼ï¼Œæ‰èƒ½å¤ è®“å•é¡Œæ›´å®¹æ˜“åˆ©ç”¨æ¼”åŒ–çš„æ–¹å¼æ‰¾åˆ°è§£ç­”。如果å•題本身ä¸é©åˆç”¨å›ºå®šé•·åº¦ä¾†è¡¨é”,就å¯ä»¥è€ƒæ…®ç”¨ä¸å®šé•·åº¦çš„基因;相å°çš„,如果å•題本身ä¸éœ€è¦ä¸å®šé•·åº¦å°±å¯ä»¥è§£æ±ºï¼Œç”¨ä¸å®šé•·åº¦åŸºå› åž‹å而會造æˆç¨‹å¼æ›´æ…¢æ‰¾åˆ°è§£ç­”。

ç¬¬äºŒå€‹æ˜¯é©æ‡‰å‡½å¼(fitness function)ï¼›é©æ‡‰å‡½å¼æ˜¯ç”¨ä¾†æ¸¬è©¦å€‹é«”在ç¾åœ¨çš„ç’°å¢ƒä¸­çš„é©æ‡‰ç¨‹åº¦ï¼Œä¸€èˆ¬è€Œè¨€ï¼Œé©æ‡‰å¾—越好得分越高,也就會給它更高的機會傳éžå®ƒçš„基因給下一代。舉例來說,如果è¦ç¨‹å¼è¦æ‰¾å‡ºåŸºå› ä¸­å…¨éƒ½æ˜¯ 1 沒有 0 çš„å€‹é«”ï¼Œé‚£éº¼é©æ‡‰å‡½å¼å°±å¯ä»¥è¨ˆç®—ç¾åœ¨å€‹é«”的基因中有幾個 1。

驿‡‰å‡½å¼å…¶å¯¦å°±æ˜¯æ‰€è¬‚çš„"環境"ï¼›é©æ‡‰å‡½å¼ä¸ä½†è¦è€ƒæ…®å€‹é«”ç›¸å°æ–¼æ•´é«”的表ç¾ï¼Œé‚„è¦è€ƒæ…®åœ¨ä¸åŒæ™‚期給予個體ä¸åŒçš„壓力。例如,程å¼ä¸å¤ªå¯èƒ½åœ¨ä¸€é–‹å§‹å°±äº‚æ•¸ç”¢ç”Ÿå‡ºè‹±æ–‡ä¸­åˆæ–‡æ³•çš„å¥å­ï¼Œé€™æ™‚å€™å°±è¦æ¯”較寬容一點給分給鬆一點;等到後期程å¼å·²ç¶“抓到語法的訣竅,那麼有一個拼字錯誤,或許就會被扣ä¸å°‘分數。

ç¬¬ä¸‰å€‹æ˜¯é¸æ“‡å‡½å¼(selection function)ï¼›ä¸€èˆ¬ä¾†èªªï¼Œé¸æ“‡å‡½å¼éƒ½æœƒä¾ç…§é©æ‡‰å‡½å¼çš„åˆ†æ•¸ä¾†ä½œç‚ºåˆ¤æ–·ä¾æ“šï¼Œä½†é¸æ“‡æœ‰å¾ˆå¤šæ–¹å¼ï¼Œæœ€ç°¡å–®çš„就是å‰é¢ä¸€åŠå°±æ™‰ç´šï¼Œå¦å¤–也有ä¾ç…§å¾—分多寡加權計算機率的,甚至於ä¿é€åˆ°ä¸‹ä¸€ä»£çš„æ–¹å¼ã€‚鏿“‡å‡½å¼åšçš„就是"天擇"的動作。ä¸åŒçš„鏿“‡å‡½å¼å„有優缺點,也有其é“ç†æ‰€åœ¨ï¼Œè«‹å®¹ä»¥å¾Œå†è©³è¿°ã€‚

ç¬¬å››å€‹æ˜¯äº¤é…æ–¹å¼(crossover)ï¼›ç”±é¸æ“‡å‡½å¼ä¸­é¸å‡ºçš„兩個個體的基因è¦å¦‚何é‡çµ„?在固定的點切開一人一份,還是å¯ä»¥åœ¨ä»»æ„點切開來組åˆï¼Ÿå°ä¸å®šé•·åº¦çš„基因,是用模組/å€å¡Šçš„æ–¹å¼é‡çµ„交é…é‚„æ˜¯åŒæ¨£åœ¨å›ºå®šé»žåˆ‡é–‹ï¼Ÿé€™éƒ½è¦ä¾ç…§ç›®æ¨™çš„ä¸åŒè€Œèª¿æ•´ã€‚

最後是çªè®Šæ–¹å¼(mutation);個體在什麼樣的狀æ³ä¸‹æœƒçªè®Šï¼Ÿçªè®Šçš„åœ°æ–¹åˆæ˜¯åœ¨å“ªè£¡ï¼Ÿçªè®Šä¹‹å¾Œæœƒè®Šæˆä»€éº¼å€¼ï¼Ÿé€™äº›éƒ½æ˜¯å¯ä»¥è€ƒæ…®çš„。

以上五個是基因演算法程å¼è¨­è¨ˆä¸­ï¼Œæœ€é‡è¦çš„幾個架構,至於æ¯å€‹æž¶æ§‹æœ‰ä»€éº¼æ¨£çš„考é‡ï¼Œä¹‹å¾Œå†å°ˆæ–‡èªªæ˜Žã€‚

Posted on May 1, 2003 in Genetic Algorithms by pestNo Comments »

SARS 已經在全çƒå¼•起大家的密切é‡è¦–ï¼Œåœ¨ç¼ºä¹æœ‰æ•ˆæ²»ç™‚方法ã€ç–«è‹—的狀æ³ä¸‹ï¼Œå¼•èµ· SARS 的冠狀病毒究竟會往哪個方å‘ç™¼å±•ï¼Œé—œä¿‚åˆ°æ°‘çœ¾å°æ–¼æœªä¾†çš„ä¿¡å¿ƒï¼Œç•¶ç„¶ï¼Œä¹Ÿè¡æ“Šåˆ°æ•´å€‹ç¤¾æœƒçš„人際關係網絡。

é©é€¢çœ‹åˆ°ä¸­å±±é†«é™¢è‘£äº‹é•·å¯«çš„社論,其中æåˆ°ã€Œç«™åœ¨ç”Ÿç‰©æœ‰å°‹æ±‚生命延續的基本法則,我們å¯ä»¥ç›¸ä¿¡SARS病毒並無殺死其宿主的本æ„ã€ï¼Œä¹Ÿå› æ­¤ï¼Œå¯ä»¥åˆç†çš„æŽ¨è«– SARS 在經éŽä¸€æ®µæ™‚間的演化之後,毒性勢必會大大的é™ä½Žï¼Œæœå‘䏿®ºæ­»å®¿ä¸»çš„æ–¹å‘來發展。

åªæ˜¯é€™æ¨£çš„å‡è¨­å»ºç«‹åœ¨çªè®Šçއã€è¤‡è£½é »çއ以åŠç’°å¢ƒé¸æ“‡ä¸‰å€‹å‰é¡Œä¸‹ã€‚我們å¯ä»¥å¾žåŸºå› æ¼”算法的經驗來推論這三個變因,å„自扮演什麼樣的角色,以åŠäººé¡žçš„å°ç­–會造æˆä»€éº¼æ¨£çš„影響。


首先是çªè®ŠçŽ‡ã€‚çªè®Šåœ¨åŸºå› æ¼”化之中是一個無特定å好的改變,它並ä¸ä»£è¡¨æœƒæœå‘æŸå€‹è¡¨ç¾åž‹æ”¹è®Šï¼Œè€Œåªæ˜¯åŸºå› åž‹çš„變化。舉例來說,å‡å¦‚基因型原本是「1000ã€ï¼Œè€Œçªè®Šæ™‚會將其中任何一個 bit ç”± 0 變 1 或是由 1 變 0,那在這四個 bits 上é¢ç™¼ç”Ÿçªè®Šçš„æ©Ÿæœƒæ˜¯ä¸€æ¨¡ä¸€æ¨£çš„。至於çªè®Šä¹‹å¾Œçš„å€‹é«”æ˜¯å¦æ›´é©åˆç”Ÿå­˜ï¼Œå‰‡è¦ç”±ç’°å¢ƒä¾†æ±ºå®šã€‚çªè®ŠçŽ‡è¶Šé«˜ï¼Œå€‹é«”è¶Šæœ‰æ©Ÿæœƒå¿«é€Ÿæ‰¾åˆ°æ›´é©åˆç”Ÿå­˜çš„組åˆï¼›ä½†éŽé«˜çš„çªè®ŠçŽ‡ä¹Ÿæœƒé€ æˆå·²ç¶“穩定的個體å†é™·å…¥ä¸ç©©å®šæˆ–ä¸é©åˆç”Ÿå­˜çš„基因組åˆã€‚

複製頻率則關係到新一代的個體會多快產生,ç†è«–上複製頻率越高,就越有機會產生çªè®Šï¼Œå› ç‚ºæ¯ä¸€æ¬¡è¤‡è£½çš„éŽç¨‹ä¸­éƒ½æœ‰åŒæ¨£çš„çªè®Šæ©ŸçŽ‡ï¼›ç•¶ç„¶ï¼Œè‹¥æ˜¯å°æ–¼æœ‰äº¤é…行為的個體,因為交é…產生的基因互æ›ä¹Ÿæœƒæ›´ç‚ºé »ç¹ã€‚因此,複製頻率越高,就å¯ä»¥æ¸›å°‘é”到平衡所需è¦çš„æ™‚間。這也是用電腦來進行基因演算法最é‡è¦çš„æƒ³æ³•。

è€Œç’°å¢ƒé¸æ“‡æ±ºå®šå€‹é«”的走å‘;究竟新一代的毒性è¦å¼·ä¸€é»žï¼Œä¾†æŠµæŠ—å…ç–«ç³»çµ±ï¼Œé‚„æ˜¯å‚³æ’­æ€§é«˜ä¸€é»žï¼Œä½†æ¯’æ€§å¼±ä¸€é»žï¼Œéƒ½å–æ±ºæ–¼ç’°å¢ƒã€‚å¦‚æžœæˆ‘å€‘ä¸æ–·æé«˜å¤§å®¶çš„å…疫系統能力,那也有å¯èƒ½æœƒé€ æˆç—…毒æœå‘更強的方å‘走,形æˆã€Œç”Ÿç‰©è»å‚™ç«¶è³½ã€ï¼›åŒæ™‚間,若是能夠製造ä¸åˆ©æ–¼æ¯’性高個體發展的環境,那麼新一代的弱毒性病毒就比較有å¯èƒ½æœƒå–得優勢地ä½ã€‚

åªä¸éŽï¼Œåœ¨è€ƒæ…®åˆ°åŠªåŠ›æ•‘æ´»æ¯ä¸€å€‹æ‚£è€…的狀æ³ä¸‹ï¼Œä¼¼ä¹Žä¸å¤ªå¯èƒ½ä»»ç”±ç—…æ¯’è‡ªè¡Œæ¼”åŒ–ï¼Œå…¶å¯¦é€™ä¹Ÿæ˜¯å¯¦å‹™ä¸Šçš„å›°é›£ä¹‹è™•ã€‚åªæ˜¯ä¸çŸ¥é“,將來的生物資訊發展更為進步之時,有沒有å¯èƒ½åœ¨å¯¦é©—å®¤ä¹‹ä¸­åŠ é€Ÿé€²è¡Œé€™æ¨£çš„ç—…æ¯’æ¼”åŒ–ï¼Œè€ŒæŠŠæœ€å¾Œçš„å¼±æ¯’æ€§ç—…æ¯’ç™¼å±•å‡ºä¾†ï¼Œå†æ”¾åˆ°äººé¡žèº«ä¸Šï¼Œä»¥æŽ’擠較毒的病毒發展空間?或許這也是一種走å‘。

註一:所謂的「生物è»å‚™ç«¶è³½ã€(Biological Arms Race)ï¼Œæ„æŒ‡å…©ç¨®ç‰©ç¨®ç”±æ–¼åœ¨æ¼”化環境中具有å°ç«‹é—œä¿‚,造æˆå…©ç¨®ç‰©ç¨®éƒ½è¶Šæ¼”化越強;例如,羚羊跑得越快,就越ä¸å®¹æ˜“被çµè±¹åƒæŽ‰ï¼Œå› æ­¤ç¾šç¾Šæœå‘跑得快演化,åŒä¸€æ™‚é–“çµè±¹ä¹Ÿæœƒæœ‰å·®ä¸å¤šç¨‹åº¦çš„æ¼”化,因為ä¸èƒ½è·Ÿä¸Šæ–°å“種的羚羊的有較高機會會餓死;而第二代的çµè±¹åˆé€ æˆç¾šç¾Šå¿…é ˆå†æ¼”化,留下跑得更快的å“種。如此一來一往之間,就如åŒäººé¡žä¸–界的è»å‚™ç«¶è³½ä¸€æ¨£ï¼Œä½ æœ‰å½ˆé“飛彈,我就發展å彈é“飛彈;然後你åˆç™¼å±•åå彈é“飛彈,我就發展ååå彈é“飛彈….長此以往,兩國在飛彈的競爭雖然ä»ç¶­æŒå‡å‹¢ï¼Œå»æœƒå½¢æˆå¤§å¹…度的æˆé•·ã€‚

Posted on August 27, 2002 in Genetic Algorithms by pest5 Comments »

如果說上å¸é‰…細彌éºçš„創造了這個世界,那麼當這個上å¸é‚„真的得無所ä¸èƒ½ã€‚幸好é”爾文為我們指出了演化的力é‡ï¼Œé è‘—演化,å³ä½¿æ²’有上å¸ï¼Œé€™å€‹ä¸–界還是有å¯èƒ½ç™¼å±•出來的; 如果真的有上å¸ï¼Œé‚£éº¼æˆ‘相信祂是寫下『基因演算法ã€çš„傑出程å¼è¨­è¨ˆå¸«ã€‚

在這個網站上已經談éŽè¨±å¤šåŸºå› æ¼”算法的應用,但å»é‚„沒為它寫一篇詳細的介紹。究竟基因演算法是什麼呢?

基因演算法(Genetic Algorithm)å…¶å¯¦æ˜¯å–æ³•å¤§è‡ªç„¶çš„ä¸€ç¨®æ¼”ç®—æ³•ï¼Œè—‰è‘—å°æ–¼æ¼”化ç¾è±¡çš„觀察,John H. Holland èªç‚ºå¯ä»¥é€éŽæŠŠå•題轉為基因型(Genotype),利用競爭-生存以åŠåŸºå› äº¤æ›-çªè®Šï¼Œå°‹æ±‚出å•題的正確解答。

é€éŽç«¶çˆ­-ç”Ÿå­˜ï¼Œæ“æœ‰å¥½åŸºå› çš„å“ç¨®æœƒæœ‰è¼ƒé«˜çš„æ©Ÿæœƒç”Ÿå­˜åˆ°ä¸‹ä¸€ä»£ï¼Œè€Œèˆ‡ç”Ÿå­˜è¼ƒç„¡é—œçš„åŸºå› å‰‡æœƒéš¨è‘—æ™‚é–“é€æ¼¸è¢«æ·˜æ±°ï¼Œã€‚åœ¨ç†æƒ³çš„狀態下,競爭-生存會迫使ä¸å…·å„ªå‹¢çš„å“ç¨®é€æ¼¸æ¶ˆå¤±ã€‚

ç„¶è€Œå–®å–®æ“æœ‰ä¸€ç¨®å¥½åŸºå› æ˜¯ä¸å¤ çš„ï¼›é€éŽåŸºå› çš„交é…,ä¸åŒçš„個體å¯ä»¥æŠŠå®ƒå€‘的好基因組åˆèµ·ä¾†ï¼Œè®Šæˆæ›´å…·å„ªå‹¢çš„下一代;而若是組åˆå‡ºä¾†çš„後代ä¸ç†æƒ³ï¼Œä¹ŸåªæœƒåŠ é€Ÿè¢«æ·˜æ±°ã€‚

但交æ›åŸºå› ä¹Ÿä¸èƒ½æ”¹è®Šç¾æœ‰çš„基因狀態,還è¦å†é…åˆçªè®Šï¼Œæ‰èƒ½å¤ ç”¢ç”Ÿé©å‘½æ€§çš„æ”¹è®Šï¼Œé€²è€Œå°æ—群進步有çªç ´æ€§çš„發展。

因此,"生存-競爭"ã€"交é…"ã€"çªè®Š"就是整個基因演算法,也å¯ä»¥èªªæ˜¯æ¼”åŒ–çš„ä¸­å¿ƒæ€æƒ³ã€‚

下一篇將介紹基因演算法的例å­ï¼Œåˆ©ç”¨åŸºå› æ¼”算法來演化出符åˆè¦æ±‚的字串。

Posted on August 19, 2002 in Genetic Algorithms by pestNo Comments »

嫌自己的è²éŸ³ä¸å¤ ç¾Žå¦™ï¼Ÿèªªèµ·è©±ä¾†æ²’æœ‰ç”·å­æ°£æ¦‚?還是害怕自己演講時ä¸å¤ å¨åš´æˆ–感性?ç¾åœ¨ç§‘學家發明出一種新的音訊處ç†ç¨‹å¼ï¼Œè®“您å¯ä»¥éš¨å¿ƒæ‰€æ¬²çš„æ”¹è®Šè‡ªå·±ç™¼å‡ºçš„è²éŸ³ã€‚

當人å°è‘—麥克風說話時,這套系統會把輸入的è²éŸ³è½‰æ›ç‚ºè¨­å®šçš„èªžèª¿ã€‚ç„¶è€Œé€™å¥—ç³»çµ±çš„èªžèª¿ä¸¦ä¸æ˜¯äº‹å…ˆåœ¨å‡ºå» æ™‚設定好,而是é€éŽåŸºå› æ¼”算法來訓練。

首先,系統會隨機產生一些"è²éŸ³åŸºå› ",æ¯ä¸€å€‹çš„語調ã€éŸ³é‡å’Œé€Ÿåº¦å„有ä¸åŒï¼Œä½¿ç”¨è€…å¯ä»¥åœ¨è†è½ä¿®æ”¹çš„çµæžœå¾Œï¼Œå°æ¯ä¸€å€‹åŸºå› é«”作評分,然後å†ç¶“由基因交æ›ã€çªè®Šç­‰éŽç¨‹ç”¢ç”Ÿä¸‹ä¸€ä»£çš„基因。

這套由æ±äº¬ Hosei 大學 Yuji Sato 所發表的系統,目å‰é‚„ä¸èƒ½å°‡è¼¸å…¥çš„è²éŸ³å³æ™‚作轉æ›ï¼ŒSato 表示他將會在這方é¢ç¹¼çºŒåŠªåŠ›ã€‚

æ–°èžä¾†æºï¼š
Genetic algorithm tunes up public speakers

相關連çµï¼š
Yuji Sato, Hosei University, Tokyo