今天收到一�廣告信，是 iRobot 公�出的 Roomba 智慧�塵機器的廣告。先�讀到一些這方�的產�，就�這個機會介紹一下好了，希望�於懶得打掃家裡地�的人有幫助 :p

Roomba 和一般的智慧å�¸å¡µæ©Ÿå™¨ä¸€æ¨£ï¼Œéƒ½æ˜¯å�šæˆ�圓餅的形狀，主è¦�還是為了在探索地型時撞到牆ä»�能順利轉彎。這類產å“�最基本的技術還是在於如何建立環境地圖，以å�Šé�¿é–‹å�±éšªçš„地形；更進階的是è¦�辨èª�什麼是需è¦�清潔的，而什麼å�ˆæ˜¯ä¸�能清ç�†çš„(試想家中的å�šç¾Žç‹—被å�¸å¡µå™¨æŠ“ä½�的樣å­�…)

Roomba 用的概念很單純；它會先利用螺旋狀的路徑擴大自己的虛擬視野，試著找出房間的邊界在哪裡，�時記�自己走�的�離。當撞到�西時，它會先�後退一點點，轉一點點彎，���進。找到邊界之後，它會開始利用直線�進，並清掃記憶中還沒有打掃的�域。

在 Roomba 中比較有趣的是它還�供一個"虛擬牆"(Virtual Wall)的�置；由於 Roomba 會儘�找出牆的範�，所以如果門開著它��好就會跑出去了，若是我們希望門�以��關，���它跑出房間，就�以把 Virtual Wall 放在門�，這樣它就�會跑出去了。Virtual Wall 其實是一個會發出��見光的�置，Roomba 感應到它的光線，就會當作那是��而轉彎了。

Roomba 這å�°èƒ½å¤ æ„Ÿæ¸¬åˆ°æ¨“梯之類的å�±éšªå�€åŸŸï¼Œè€Œä¸�會摔下去；當它在進行清掃的時候，會放音樂來é™�低它的噪音(還真貼心啊…-_-)，它的è�²éŸ³å¤§ç´„是 80dBå·¦å�³ã€‚

�樣的智慧型�塵器是瑞典的 Electrolux 公�所�的 trilobite；這�紅色的�圓餅功能和 Roomba 類似，��它�會�樓梯，而需�用鋪在地上�毯來畫出��。��它有個有趣的功能，就是會自己跑回去固定的"家"充電，真是很�愛的功能 :p

<>

<>

<>

<>

Trilobite	Roomba

�考資料：
http://www.roombavac.com
http://trilobite.electrolux.co.uk

相關連�：
管家婆科技： Roomba News

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

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

在å�¦ä¸€å€‹blog寫文章時，都會有一種脫力的感覺。ä¸�知é�“是ä¸�是寫文章太用力的關係，大概是覺得有讀者壓力就會很大å�§…

相信大家都有��電腦的經驗，�次������了�先把自己的檔案備份一下。習慣好的人就算了，�是平常就沒有特定的習慣，把文件檔案擺得到處都是，那備份還真是一件麻煩的事。那，有沒有�能弄一個�以記錄什麼檔案�備份而什麼��的檔案系統呢？

基本的想法是這樣的：就��在Windows的檔案都有個唯讀�隱���存的�項，�加一個備份好了，這樣就�以寫一個備份的程�，自動把硬碟中的這類檔案都找出來，然後通通燒�光碟或移到備份的資料夾之類的。

好處其實��是備份文件而已；�如�個程�有一些�版也�太會改變的設定值，�次��都��新設定也很麻煩，那麼這樣的設定也�以設定為需�備份，當使用者��完就�用�自己一個一個設定了。

總之覺得是個�以�的�西，既然也�是什麼神秘的點�，就發表在這邊與大家分享�� :p

以å‰�一直ä¸�懂為什麼有人會用公餘的時間來æ�ž open-source/GPL 之類的事情，ä¸�é�Žé€™ç¨®äº‹æƒ…真的是時候到了就會瞭解的 — 完全是白天為公å�¸ä½œæƒ¡å¤ªå¤šã€�罪孽深é‡�，晚上(æ�žä¸�好上ç�­æ™‚?)寫寫 GPL çš„æ�±è¥¿ä¾†æ´—清自己的罪惡啊….。

嗚嗚，Stallman，我有罪 :~ 請讓我用我的 GPL source 來洗刷我的罪惡� :~

註一：Richard Stallman(�查‧始脫男 自由軟體�會創始人，GPL 教主/精神領袖，教主的網�在此；如果需�教主加�您的電腦請按此。

註二：關於 GPL 請�考 談 GNU General Public License

一點也沒有高興的感覺。��感�王文�，我知�我屬於加�。

�考： 《好男人都死到哪去了？》

è·�離上次介紹基因演算法的第一篇已經好久了，é‡�新回顧æ‰�發ç�¾ä¸¦æ²’有在技巧上é�¢èªªæ˜Žå¾—很清楚，所以打算å†�繼續這個主題，把基因演算法å�šä¸€å€‹å®Œæ•´çš„介紹…

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

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

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

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

利用��的基因表�方�，�能夠讓�題更容易利用演化的方�找到解答。如果�題本身���用固定長度來表�，就�以考慮用�定長度的基因；相�的，如果�題本身�需��定長度就�以解決，用�定長度基因型�而會造�程�更慢找到解答。

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

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

第三個是�擇函�(selection function)；一般來說，�擇函�都會�照�應函�的分數來作為判斷�據，但�擇有很多方�，最簡單的就是��一�就晉級，�外也有�照得分多寡加權計算機率的，甚至於��到下一代的方�。�擇函��的就是"天擇"的動作。��的�擇函��有優缺點，也有其��所在，請容以後�詳述。

第四個是交�方�(crossover)；由�擇函�中�出的兩個個體的基因�如何�組？在固定的點切開一人一份，還是�以在任�點切開來組�？��定長度的基因，是用模組/�塊的方��組交�還是�樣在固定點切開？這都��照目標的��而調整。

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

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

上週一開始�上��的日�，在決定上�之�爸爸找我談了一下；在長輩的心中，能夠唸書總是好的，家裡也�急著�我賺錢，人生很長，早點投資一點在自己身上，�長輩們來說，似乎比進入社會見識�來得�險一些。
�是從上大學之後，已經走了調的生活，開始�我進行最嚴厲的�擊；申請學校的�順利，歸咎到最後，除了時�之外，自己的�績太難看也是�點。有能力/潛力�沒有辦法表�在具體的事例上�，洋洋��的履歷表�無法彌補學術方�的失敗。混�了大五，忙�了畢業之後的這八個月，�知如何��自己的壓力，已經排山倒海而來。

五月完全ä¸�是我的幸é�‹æœˆï¼›åŽŸæœ¬ä»¥ç‚ºç©©ä¸Šçš„學校也沒有著è�½ï¼Œè²·è‚¡ç¥¨å› ç‚º SARS 套牢ã€�å�‘國外訂 Notebook 也沒辦法如期交貨ã€�和朋å�‹å�µæž¶…等等，一點點å°�事情就會讓我覺得é�žå¸¸æ²®å–ªï¼›æˆ‘開始懷疑自己是ä¸�是è¦�垮了，所以我和爸爸說，我沒辦法å†�待在家中無所事事了，找個事å�šï¼Œå†�看看將來è¦�怎麼走å�§….。

昨天看到這期讀者文摘的æ�Žå®‰å°ˆè¨ªï¼›ä»–在 1984 年從 NYU 的電影研究所畢業之後，一直到 1990 年《推手》以å�Šã€Šå›�宴》的劇本得ç�Žé–‹æ‹�之間，一直處在這樣的低點中；平常在家幫忙帶帶å°�å­©ã€�勉強去æ‹�戲ç�¾å ´å�šé»žé›œå‹™ï¼Œç”šè‡³åŽ»å¹«å¿™çœ‹å®ˆå™¨æ��。他說：「畢業快六年，一事無æˆ�，剛開始還能談談ç�†æƒ³ï¼›ä¸‰å››å¹´å¾Œï¼Œäººå¾€å››å��歲走，也ä¸�好æ„�æ€�å†�說什麼ç�†æƒ³ï¼Œé–‹å§‹æœ‰é»žè‡ªé–‰ã€‚ã€�…..「許多人奇怪我怎麼敖é�Žé‚£æ®µå¿ƒæƒ…鬱悶的日å­�。當年我沒辦法跟命é�‹æŠ—衡，但我死皮賴臉帶在電影圈，繼續從事這一行，時機來了，就迎上å‰�去。ã€�

我�知�在我��還有多少個低點�走，但希望我�我的夢想，有�安的堅�和勇氣。