基因程式设计(

1、基因程式設計( Genetic Programming)很多使用在電腦世界中的技巧、演算法，都是由自然界中的定律，或者是由生物的演化以及人體中的某些器官運作而得到的靈感。例如，類神經網路，它就是一個實際的例子，在研究人類腦部的學習方式之後，進而應用在類神經網路的學習上。而也有某些方法是來自於生物學界中達爾文的演化論與物競天擇。像是基因演算法 (Genetic algorithm)，它就是把生物演化的方式應用在解決問題中。在生物界，生物由低等便由高等生物，是經由長久的演化、交配、突變而造成的。而在基因演算法中，我們也有一群由不同狀態的個體組合成的群體，我門使用fitness function 去

2、挑選出比較優良的個體進行交配與突變，反覆的進行之後，會得到我們想要的解答。這就是基因演算法的大致流程。而它可以應用在很多地方，例如八皇后問題，那麼棋盤上擺上了8個皇后，這樣就是一個狀態。會有很多狀態，而在這裡fitness function也就是用來計算狀態的總衝突數的函式，利用這個函式去挑選出衝突數比較少的狀態進行交配及突變而得到結果，這就是他的應用之一。那GP又是什麼呢？GP事項是automatic programming，絕大部分的人看到這個可能會誤以為會自動的產生出一個 完整的程式碼。但是並不盡然，絕大部份產生的只是個形式(form)，那他到底有什麼用處呢？GP通常使用在softwar

3、e-reengineering與quantum computing。而什麼是software-rerngineering與quantum computing呢?在接下來的內容會有比較詳細的說明。先來提到Alan Turing這個人，他所提出的理論耳熟能詳的就是Turing test了，但是除了Turing test之外，他還提出一個藉由任意的組件組合成所提供計算的機器去探索未知的領域。他指出這個機器可以循著規則去找出結果，並會自己修改程式碼，也可以使始機器本身的知識增，藉由一些外界的資料。他指出機器一開始是child machine，他會經由學習進行知識的增長。不久後，有個R.M. Fried

4、berg 提出了一個叫做Herman 的系統，他是透過random variations 進行學習。此系統本身也定義了一個虛擬的組合語言空間在這些variation的took place裡面。而Evaluting programs 是一個接個一個執行，因此測量他的效能是非常的低的。進入到 artificial evolution。在現在的環境中很多問題無法使用傳統的方法去解決，而artificial evolution 是去合併多樣的最佳化的問題，照出方法或規則去解決目前的問題。現在是二十一世紀，那他我們脫離了中古時期了嗎?再這提到了一個有趣的問題，在中古世紀的時候 因為紙張的發明而讓大家開始

5、有紙張可以記錄知識，因此大量的紙張被製造了出來，然後指的價格下滑，而接著印刷術的出現，加速的知識的紀錄，而大家有的大量而快速的紀錄知識的方法。而現在CPU的 cycle time也樣當時的紙張一樣 大量的囤積，而工作也逐漸的轉移到電腦上。GP到最後將不會只剩下一種方法去產生程式，因為我們已經應用了模擬退火與啟發式搜尋方法。為了使GP所產生的程式可使用，因次我們必須訂定一些規則讓它去遵守，而GP循著規則已經可以達到我們所預期的目標，使其效能效率能達到人類的水平。而GP已經可以達到如此的水準，在以下的6的方面：control、design、classification、pattern recogn

6、ition、game playing、algorithm design。說了這摩多GP的好處與應用，那麼接著來簡單的說明GP是如何運作的。GP一開始是隨機的產生電腦程式，接著挑選出一對對的程式，並計算那些對於目前要解決的問題是比較優良的，接著會進行交配(crossover)、突變(mutation)與architecture-altering operation。Architecture-altering operation會自動的去增加或刪除一些子條件(應該是指判斷句)、參數、迴圈、遞迴和記憶體的配置。GP有時候也會被稱為automatic program。他由一個需求必須去解決而開始執行，

7、接著他會告訴我們該如何去做，然後產生一個電腦程式。接著他會自動去決定執行的步驟，他支援程式碼、參數、程式結構中的各種型態(迴圈、遞迴與判斷句等) 重複使用(reuse)，也可重複使用以執行過或執行中並存在記憶體中的結果。並且會自動的決定條件句、遞迴、迴圈、記憶體等的階層式結構。也廣泛的支援各類有用的programming construct。並且它產生的語意清楚，而且問題與問題間是互相獨立不會有互相干擾的狀況。可以應用在多樣的問題上。他是scalable。可以產生出可與人類競爭(較競)的結果。以上就是GP會去做的動作與結果。GP與其他AI的方法或machine learning是不同的。第一個

8、不同是，他的表示方法與其他的方法不同。GP是很明顯的引道它去搜尋可以解決某問題的結果。第二個不同在於GP不需要建立一個很明確很清楚的knowledge base。第三點是他不使用formal logic的inference methods。第四點是他並不是只針對某個點去做搜尋，而是對於一個set去搜尋，範圍比較大，因此可以獲得的資訊也會比較多。第五點，他不依賴greedy hill climbing去搜尋而取得結果。GP只是一個工具，並不是用來取代人類的。GP不是fully automatic programming system，他所產生的對人來而言只是個大略的描述，不是一個可以執行的程式。

9、GP是一個優良的問題解決者，它可以使用有效率的工具去撰寫出函式去解決問題。但是他還是無法去代程式設計師，因為判斷他所產生出來的函式好壞的fitness function還是必須由程式設計師去撰寫，無法讓GP自動產生。因此一個GP system的好壞，還是在於fitness function，所以程式設計師還是必須可以很明確的了解問題的涵義。那GP還可以應用在software maintain上，例如使用者想改變程式碼的結構，像是想把GOTOs的語法使用別的方式取代他，因為GOTOs會降低程式的可讀性。或者像是一個貨幣轉換系統，想把現在所在地的貨幣轉換成歐元。或者是解決類似Y2K 的問題，原本電

10、腦都是以兩個數字來記錄年代，而遇到了Y2K的問題，那我們也可以使用它來把年代轉換成4個數字，這也可以稱做為software-reengineering。在傳統上的方法我們可能會認為GP可以指出必須修改改寫的的部份程式碼。但是事實上GP是去evolve 一個程式的函式，然後去取代原有的函式。他是使用原來的函式經由fitness function，計算出一個新的更適合的程式碼。但是某些主流的程式設計師認為此一作法可能會在這個程式上加上了許多隱藏在看不到的地方的危險。而另一個問題是GP把大部分的時候都花在fitness function的計算上，如果reengineered code 正在消耗特別的

11、時間，那他可能是不可能達成的。GP適合去產生平行的程式碼，因為它為了reengineering渴望去擁抱the maze of transformations是必須的 。再者，其他lateral 方法為了平行程式設計也是必要的，雖然一個外來的方法對於眾多的程式，是tailor made為了GP的 bottom-up 的方法。所有的transformations GP使用者僱用使一個標準的平行型態和語法伴隨著一個警告-這個程式的區域，這個區域是一個transformation 的影響不包含資料的相依性。如果transformation損毀了，那模那些條件將會被應用，那他將可能會去改變他的語義和會

12、去執行可以降低風險的個體的fitness function。然而他的一個最主要的優點是我們可以依序著調查這個transformation employed和證明它去維護這個程式的正當性。並且當程式設計師可以看到並取得這個程式的全部的架構與程式碼的時候，GP並不是只能spot和exploit程式碼裡的任何的pattern而且可以使用它bottom-up方法的優點。GP可以移動附近的程式碼，改變loop的位置，甚至是把之前的loop結合在一起，但是這是程式設計師不喜歡的方式。由於在GP中他使用隨心所欲的方式去cut 和divides程式碼，實際上，在迴圈中，我們無法保證被修改過的程式碼的可讀性。T

13、ransformation-based GP 與傳統的差別在於假設the existence if some sort of embryonic structure ，它會日益漸增的修改到更多可接受的狀態中。GP maintain GA演法算：搜尋process proceedes藉著迴圈的方式 一值反覆的執行群體裡面的個體的fitness function，然後再使用genetic operation像是交配(crossover)、突變(mutation)，使得個體改變以達到比較高的fitness以進行接下來的動作，就是以利去探索問題所在的領域。近來使用GP的工作大部分都在探討所有的elem

14、ents如何才能帶來evolutionary control。Automatically defined functions 是讓evolving programs 定義一些規則，讓GP去尋著規則尋找出結果。Architecture altering operations是讓evolutionary process 動態的探索不同程式的結構。Automatically defined macros 是讓evolving program定義新的迴圈、條件控制在maner analogous to ADFs。其他的工作是展示出CP如何去此用rich type system。接著簡單的介紹一下qua

15、ntum computer。Quantum computer是使用dynamics of atomic-scale objects to store 並且運用資訊的設備。因為實際上的quantum computer 硬體是不可得的，因此我們要測試evolving quantum 演算法的fitness必須在傳統的電腦上跑quantum computer的模擬器。在這裡所使用的模擬器是QGAME(quantum gate and measurement emulator)，表示quantum algorithms 是使用quantum gate array formalism。在使用這種形式(formalism)中，計算時是使用quantum bit (qubit)為單位，所以他很類似Boolean logic networks。主要的差別在於，在任何時間裡quantum system的state可以當成對應的Boolean system的所有可能的states的重疊。對於每個典型的state，我們會把它儲存成一個複雜的值，這個值稱為probability amplitude，如果我們去測量他，那我們可以使用那他決定我們將尋找的系統的機率。QGAME 是跟隨著所有的分支(branch 也就是像if else之類的)，collasing the superpositions