現今充斥於電影或是電玩中的人物或角色，大多都無法避免要走得"像人"；當傳統的方法繁瑣而缺乏彈性，基因演算法再一次為動畫製片指出一條簡單易用的路…。

傳統上，要做出動畫中的人物走路的畫面，通常都需要仔細描述每個畫面怎麼走、或是把真人的動作拍攝下來再輸入進去。然而這種做法太繁瑣也缺乏彈性，所以 Torsten Reil 決定運用基因演算法，來教導他的人物走路。

首先必須建立環境；把重力和人物的肌肉結構都做好關連之後，每一個角色有七百組參數可以調整。他透過類神經網路來控制肌肉的運動，但是由於系統實在太複雜而不可能透過人來調整，所以這時就可以導入基因演算法來訓練。

由於系統中有重力等條件，所以系統評分的方法就採用人物走的步數來評分；走越多步的就越好，直到它跌倒為止。剛開始系統中的人物大都走不了一步，但至少有些會比其他晚一些倒下，這些表現比較好的個體會被複製二十份，再做一些細微的突變放到下一代。同時系統也會再產生八十個新的個體加入賽局。

但是由於評分標準是採用走的步數，所以有些角色就會發展出奇怪的走法，例如仆伏前進或是翻筋斗之類的，所以他再進一步把遊戲規則加入一條，就是重心不能低於某個高度。

經過二十回合，系統已經能夠產生走得非常順暢的角色了；我們不需要知道它內部的類神經網路怎麼排列，但可以確定的是演化的力量再一次的快速替我們找到一個解答。

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

相關網站：
Active Character Technology (有 Demo 短片)
Endorphin, 可以自動產生出動畫人物動作的軟體 (Demo)

今天在看 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

相關閱讀：
上帝的靈藥─基因演算法(一)
上帝的靈藥─基因演算法(二)

距離上次介紹基因演算法的第一篇已經好久了，重新回顧才發現並沒有在技巧上面說明得很清楚，所以打算再繼續這個主題，把基因演算法做一個完整的介紹…

如果您不知道基因演算法是什麼，建議您可以先參考上一篇。

先前提到基因演算法的基本概念，但是要怎麼寫程式呢？首先我們先來探討基因演算法的幾個基本元素。

第一個是基因；沒有基因來當作媒介，我們沒有辦法進行基因演算法，但是要怎麼表現基因呢？以電腦世界而言，最常見的就是 0 和 1 的組合形成的"Bit String"，例如：0010 就是一個四個位元的 bit string。用四個位元就可以表現出十六種基因組合，而不同的基因組合又可以對照到不同的"表現型"上，例如第一個 bit 表示顏色、第二個 bit 表示長度，第三個 bit 表示色調等等。

除了固定長度的基因之外，也可以採用不定長度的基因；例如，假如要用英文字測試是否能夠演化出一本莎士比亞全集，就可以採用不定長度的基因，讓莎士比亞全集由最早的英文單字逐漸長到厚厚數本書這麼大。

利用適合的基因表達方式，才能夠讓問題更容易利用演化的方式找到解答。如果問題本身不適合用固定長度來表達，就可以考慮用不定長度的基因；相對的，如果問題本身不需要不定長度就可以解決，用不定長度基因型反而會造成程式更慢找到解答。

第二個是適應函式(fitness function)；適應函式是用來測試個體在現在的環境中的適應程度，一般而言，適應得越好得分越高，也就會給它更高的機會傳遞它的基因給下一代。舉例來說，如果要程式要找出基因中全都是 1 沒有 0 的個體，那麼適應函式就可以計算現在個體的基因中有幾個 1。

適應函式其實就是所謂的"環境"；適應函式不但要考慮個體相對於整體的表現，還要考慮在不同時期給予個體不同的壓力。例如，程式不太可能在一開始就亂數產生出英文中合文法的句子，這時候就要比較寬容一點給分給鬆一點；等到後期程式已經抓到語法的訣竅，那麼有一個拼字錯誤，或許就會被扣不少分數。

第三個是選擇函式(selection function)；一般來說，選擇函式都會依照適應函式的分數來作為判斷依據，但選擇有很多方式，最簡單的就是前面一半就晉級，另外也有依照得分多寡加權計算機率的，甚至於保送到下一代的方式。選擇函式做的就是"天擇"的動作。不同的選擇函式各有優缺點，也有其道理所在，請容以後再詳述。

第四個是交配方式(crossover)；由選擇函式中選出的兩個個體的基因要如何重組？在固定的點切開一人一份，還是可以在任意點切開來組合？對不定長度的基因，是用模組/區塊的方式重組交配還是同樣在固定點切開？這都要依照目標的不同而調整。

最後是突變方式(mutation)；個體在什麼樣的狀況下會突變？突變的地方又是在哪裡？突變之後會變成什麼值？這些都是可以考慮的。

以上五個是基因演算法程式設計中，最重要的幾個架構，至於每個架構有什麼樣的考量，之後再專文說明。

SARS 已經在全球引起大家的密切重視，在缺乏有效治療方法、疫苗的狀況下，引起 SARS 的冠狀病毒究竟會往哪個方向發展，關係到民眾對於未來的信心，當然，也衝擊到整個社會的人際關係網絡。

適逢看到中山醫院董事長寫的社論，其中提到「站在生物有尋求生命延續的基本法則，我們可以相信SARS病毒並無殺死其宿主的本意」，也因此，可以合理的推論 SARS 在經過一段時間的演化之後，毒性勢必會大大的降低，朝向不殺死宿主的方向來發展。

只是這樣的假設建立在突變率、複製頻率以及環境選擇三個前題下。我們可以從基因演算法的經驗來推論這三個變因，各自扮演什麼樣的角色，以及人類的對策會造成什麼樣的影響。

首先是突變率。突變在基因演化之中是一個無特定偏好的改變，它並不代表會朝向某個表現型改變，而只是基因型的變化。舉例來說，假如基因型原本是「1000」，而突變時會將其中任何一個 bit 由 0 變 1 或是由 1 變 0，那在這四個 bits 上面發生突變的機會是一模一樣的。至於突變之後的個體是否更適合生存，則要由環境來決定。突變率越高，個體越有機會快速找到更適合生存的組合；但過高的突變率也會造成已經穩定的個體再陷入不穩定或不適合生存的基因組合。

複製頻率則關係到新一代的個體會多快產生，理論上複製頻率越高，就越有機會產生突變，因為每一次複製的過程中都有同樣的突變機率；當然，若是對於有交配行為的個體，因為交配產生的基因互換也會更為頻繁。因此，複製頻率越高，就可以減少達到平衡所需要的時間。這也是用電腦來進行基因演算法最重要的想法。

而環境選擇決定個體的走向；究竟新一代的毒性要強一點，來抵抗免疫系統，還是傳播性高一點，但毒性弱一點，都取決於環境。如果我們不斷提高大家的免疫系統能力，那也有可能會造成病毒朝向更強的方向走，形成「生物軍備競賽」；同時間，若是能夠製造不利於毒性高個體發展的環境，那麼新一代的弱毒性病毒就比較有可能會取得優勢地位。

只不過，在考慮到努力救活每一個患者的狀況下，似乎不太可能任由病毒自行演化，其實這也是實務上的困難之處。只是不知道，將來的生物資訊發展更為進步之時，有沒有可能在實驗室之中加速進行這樣的病毒演化，而把最後的弱毒性病毒發展出來，再放到人類身上，以排擠較毒的病毒發展空間？或許這也是一種走向。

註一：所謂的「生物軍備競賽」(Biological Arms Race)，意指兩種物種由於在演化環境中具有對立關係，造成兩種物種都越演化越強；例如，羚羊跑得越快，就越不容易被獵豹吃掉，因此羚羊朝向跑得快演化，同一時間獵豹也會有差不多程度的演化，因為不能跟上新品種的羚羊的有較高機會會餓死；而第二代的獵豹又造成羚羊必須再演化，留下跑得更快的品種。如此一來一往之間，就如同人類世界的軍備競賽一樣，你有彈道飛彈，我就發展反彈道飛彈；然後你又發展反反彈道飛彈，我就發展反反反彈道飛彈….長此以往，兩國在飛彈的競爭雖然仍維持均勢，卻會形成大幅度的成長。

如果說上帝鉅細彌遺的創造了這個世界，那麼當這個上帝還真的得無所不能。幸好達爾文為我們指出了演化的力量，靠著演化，即使沒有上帝，這個世界還是有可能發展出來的； 如果真的有上帝，那麼我相信祂是寫下『基因演算法』的傑出程式設計師。

在這個網站上已經談過許多基因演算法的應用，但卻還沒為它寫一篇詳細的介紹。究竟基因演算法是什麼呢？

基因演算法(Genetic Algorithm)其實是取法大自然的一種演算法，藉著對於演化現象的觀察，John H. Holland 認為可以透過把問題轉為基因型(Genotype)，利用競爭-生存以及基因交換-突變，尋求出問題的正確解答。

透過競爭-生存，擁有好基因的品種會有較高的機會生存到下一代，而與生存較無關的基因則會隨著時間逐漸被淘汰，。在理想的狀態下，競爭-生存會迫使不具優勢的品種逐漸消失。

然而單單擁有一種好基因是不夠的；透過基因的交配，不同的個體可以把它們的好基因組合起來，變成更具優勢的下一代；而若是組合出來的後代不理想，也只會加速被淘汰。

但交換基因也不能改變現有的基因狀態，還要再配合突變，才能夠產生革命性的改變，進而對族群進步有突破性的發展。

因此，"生存-競爭"、"交配"、"突變"就是整個基因演算法，也可以說是演化的中心思想。

下一篇將介紹基因演算法的例子，利用基因演算法來演化出符合要求的字串。

嫌自己的聲音不夠美妙？說起話來沒有男子氣概？還是害怕自己演講時不夠威嚴或感性？現在科學家發明出一種新的音訊處理程式，讓您可以隨心所欲的改變自己發出的聲音。

當人對著麥克風說話時，這套系統會把輸入的聲音轉換為設定的語調。然而這套系統的語調並不是事先在出廠時設定好，而是透過基因演算法來訓練。

首先，系統會隨機產生一些"聲音基因"，每一個的語調、音量和速度各有不同，使用者可以在聆聽修改的結果後，對每一個基因體作評分，然後再經由基因交換、突變等過程產生下一代的基因。

這套由東京 Hosei 大學 Yuji Sato 所發表的系統，目前還不能將輸入的聲音即時作轉換，Sato 表示他將會在這方面繼續努力。

新聞來源：
Genetic algorithm tunes up public speakers

相關連結：
Yuji Sato, Hosei University, Tokyo