今天在看 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)；個體在什麼樣的狀況下會突變？突變的地方又是在哪裡？突變之後會變成什麼值？這些都是可以考慮的。

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