本文最早發(fā)表本人博客:http://www.gotoli.us/?p=1773
遺傳編程是遺傳算法另一個(gè)重要的后續(xù)工作。顧名思義，遺傳編程中的一個(gè)個(gè)體代表了解決某個(gè)問題的候選程序，遺傳編程模擬自然選擇挑選出正確的程序。遺傳編程是人類追求自動(dòng)編程的一次嘗試。遺傳編程的兩個(gè)重要概念是基因型和表現(xiàn)型?；蛐途褪欠N群個(gè)體的編碼；表現(xiàn)型是種群個(gè)體所表示的程序片段。其實(shí)遺傳算法就有這兩個(gè)概念的萌芽。遺傳編程之所以會(huì)強(qiáng)調(diào)這兩個(gè)概念，因?yàn)檫z傳編程很難直接處理程序片段（表現(xiàn)型），反而容易處理程序片段的內(nèi)在結(jié)構(gòu)（基因型）。根據(jù)基因型形態(tài)的不同，遺傳編程方法可以分為三種：線性遺傳編程、基于樹的遺傳編程和基于圖的遺傳編程。
1 . 線性遺傳編程
線性遺傳編程有廣義和狹義之分。廣義線性遺傳編程將候選程序編碼進(jìn)定長(zhǎng)或者變長(zhǎng)的字符串，即基因型是線性字符串。狹義線性遺傳編程中的候選程序是匯編語(yǔ)言或者高級(jí)編程語(yǔ)言程序。一個(gè)狹義線性遺傳編程的個(gè)體可以是一段簡(jiǎn)單 C 語(yǔ)言指令。這些指令作用在一個(gè)或者兩個(gè)預(yù)習(xí)定義的變量或者常量上（變量數(shù)量一般為指令個(gè)數(shù)的4倍）。下圖是一個(gè)狹義線性遺傳編程候選程序的示例。
除了狹義線性遺傳編程之外，廣義線性遺傳編程還包括：Multi-Expression Programming (MEP), Grammatical Evolution (GE), Gene Expression Programming (GEP), Cartesian Genetic Programming (CGP)，和 Genetic Algorithm for Deriving Software (GADS)。其中我們就介紹一下適合電路設(shè)計(jì)的笛卡爾遺傳編程 (Cartesian Genetic Programming, CGP)。比如我們要用兩個(gè)加操作兩個(gè)減操作和兩個(gè)乘操作得到如下運(yùn)算。
笛卡爾遺傳編程將下面的一個(gè)候選程序編寫進(jìn)字符串"001 100 131 201 044 254 2573"。字符串中的三位數(shù)字“xyz"表示x操作的輸入是y和z兩個(gè)連線，字符串中最后的四位數(shù)字"opqr"表示輸出opqr四個(gè)連線。笛卡爾遺傳編程只用變異操作，而不用交叉操作。
對(duì)線性遺傳編程感興趣的同學(xué)可以閱讀論文 Oltean et al. (2003)。
2 . 基于樹的遺傳編程。
基于樹的遺傳編程的基因型是樹結(jié)構(gòu)。基于樹的遺傳編程是遺傳編程最早的形態(tài)，也是遺傳編程的主流方法。在之前的博客“欺騙”深度學(xué)習(xí)的遺傳算法中正則表達(dá)式生成問題用的就是基于樹的遺傳編程?；跇涞倪z傳編程的交叉操作如下所示，兩個(gè)顆樹之間隨機(jī)交換子樹。
基于樹的遺傳編程的變異操作有兩種：一種是隨機(jī)變換樹中的符號(hào)或者操作符，另一種是隨機(jī)變換子樹。下圖左下角是變換符號(hào)或者操作符的結(jié)果，右下角是變換子樹的結(jié)果。
上面的樹結(jié)構(gòu)（基因型）都是表達(dá)了一個(gè)數(shù)學(xué)公式，我們?cè)跇浣Y(jié)構(gòu)上定義一下語(yǔ)法操作符，便可以表達(dá)一段程序了。比如，下圖是定義了CL操作符之后，F(xiàn)or循環(huán)的樹結(jié)構(gòu)。
3 .基于圖的遺傳編程。
樹是一種特殊的圖，因此人們很自然地想到將基于樹的遺傳編程擴(kuò)展到基于圖的遺傳編程。下圖就是基于圖的遺傳編程的基因型的一個(gè)示例。
也有人將笛卡爾遺傳編程歸入基于圖的遺傳編程，這里，我們將所有基因型是線性字符串的遺傳編程歸入線性遺傳編程類別。
遺傳編程是人類實(shí)現(xiàn)“程序編寫程序”的一次嘗試。但到目前為止，遺傳編程大體上依然只是實(shí)驗(yàn)室里好玩的 toy system。
參考文獻(xiàn)
Oltean, Mihai, and Crina Grosan. "A comparison of several linear genetic programming techniques." Complex Systems 14.4 (2003): 285-314.
