本文最早發(fā)表本人博客:http://www.gotoli.us/?p=1773
遺傳編程是遺傳算法另一個(gè)重要的后續(xù)工作。顧名思義旁涤，遺傳編程中的一個(gè)個(gè)體代表了解決某個(gè)問題的候選程序，遺傳編程模擬自然選擇挑選出正確的程序敷存。遺傳編程是人類追求自動(dòng)編程的一次嘗試萝嘁。遺傳編程的兩個(gè)重要概念是基因型和表現(xià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)的字符串学赛，即基因型是線性字符串。狹義線性遺傳編程中的候選程序是匯編語言或者高級(jí)編程語言程序吞杭。一個(gè)狹義線性遺傳編程的個(gè)體可以是一段簡(jiǎn)單 C 語言指令盏浇。這些指令作用在一個(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á)式生成問題用的就是基于樹的遺傳編程∮へ基于樹的遺傳編程的交叉操作如下所示擎场，兩個(gè)顆樹之間隨機(jī)交換子樹羽德。
基于樹的遺傳編程的變異操作有兩種：一種是隨機(jī)變換樹中的符號(hào)或者操作符，另一種是隨機(jī)變換子樹迅办。下圖左下角是變換符號(hào)或者操作符的結(jié)果宅静，右下角是變換子樹的結(jié)果。
上面的樹結(jié)構(gòu)（基因型）都是表達(dá)了一個(gè)數(shù)學(xué)公式站欺，我們?cè)跇浣Y(jié)構(gòu)上定義一下語法操作符姨夹，便可以表達(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.
