基因程式設(shè)計(

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

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

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

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

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

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

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

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

9、GP是一個優(yōu)良的問題解決者，它可以使用有效率的工具去撰寫出函式去解決問題。但是他還是無法去代程式設(shè)計師，因為判斷他所產(chǎn)生出來的函式好壞的fitness function還是必須由程式設(shè)計師去撰寫，無法讓GP自動產(chǎn)生。因此一個GP system的好壞，還是在於fitness function，所以程式設(shè)計師還是必須可以很明確的了解問題的涵義。那GP還可以應(yīng)用在software maintain上，例如使用者想改變程式碼的結(jié)構(gòu)，像是想把GOTOs的語法使用別的方式取代他，因為GOTOs會降低程式的可讀性?；蛘呦袷且粋€貨幣轉(zhuǎn)換系統(tǒng)，想把現(xiàn)在所在地的貨幣轉(zhuǎn)換成歐元。或者是解決類似Y2K 的問題，原本電

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

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

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

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

14、ents如何才能帶來evolutionary control。Automatically defined functions 是讓evolving programs 定義一些規(guī)則，讓GP去尋著規(guī)則尋找出結(jié)果。Architecture altering operations是讓evolutionary process 動態(tài)的探索不同程式的結(jié)構(gòu)。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 並且運用資訊的設(shè)備。因為實際上的quantum computer 硬體是不可得的，因此我們要測試evolving quantum 演算法的fitness必須在傳統(tǒng)的電腦上跑quantum computer的模擬器。在這裡所使用的模擬器是QGAME(quantum gate and measurement emulator)，表示quantum algorithms 是使用quantum gate array formalism。在使用這種形式(formalism)中，計算時是使用quantum bit (qubit)為單位，所以他很類似Boolean logic networks。主要的差別在於，在任何時間裡quantum system的state可以當(dāng)成對應(yīng)的Boolean system的所有可能的states的重疊。對於每個典型的state，我們會把它儲存成一個複雜的值，這個值稱為probability amplitude，如果我們?nèi)y量他，那我們可以使用那他決定我們將尋找的系統(tǒng)的機(jī)率。QGAME 是跟隨著所有的分支(branch 也就是像if else之類的)，collasing the superpositions