(五) 遺傳程序設(shè)計(Genetic Programming)
GP是演化計算中的一個特殊領(lǐng)域守呜，它主要針對自動構(gòu)建程序去獨立解決問題(。躬翁。焦蘑。)。盡管有一些其它形式去完成進化盒发，但最主要的形式是語法樹(下面用表達式樹代替)例嘱。
例如狡逢，上面的圖是一個用于表示max(x+3*y, y+x)的程序。對于這個樹和其它例子拼卵，樹的葉子結(jié)點是綠色的奢浑，它們被叫做“終止符”；紅色的節(jié)點叫做“符號集”腋腮。終止集被分成了兩類——常數(shù)(數(shù)字)和參數(shù)(x,y,z...)雀彼。這些常數(shù)在整個進化過程中保持不變(why)，而參數(shù)是由程序輸入的即寡。在之前提出的樹中徊哑，參數(shù)是變量x和y，而常數(shù)是3聪富。
在DEAP中莺丑，用戶定義的符號集和終止集都被定義在primitive set中。現(xiàn)在善涨，有兩種型號的primitive set：寬松式和健壯式窒盐。(loosely & strongly)
- Loosely Typed GP(LTGP)
LTGP不會在結(jié)點間強制明確類型(草则？钢拧？)。更多可以確定的是炕横，primitive集合的參數(shù)可以是任意的運算符或者終止節(jié)點源内。
下面的代碼定義了一個寬松的primitiveSet
import operator
from deap import base,creator,gp,tools
pset = gp.PrimitiveSet('MAIN', 2)
pset.addPrimitive(max, 2)
pset.addPrimitive(operator.add, 2)
pset.addPrimitive(operator.mul, 2)
pset.addTerminal(3)
第一行創(chuàng)建了primitive set(pset)。它的參數(shù)是通過("MAIN")產(chǎn)生的份殿，并且數(shù)目為2膜钓。后面的三行是添加符號集的函數(shù)，第一個參數(shù)是函數(shù)名稱卿嘲，第二個是函數(shù)的運算符目數(shù)(就是完成這個運算需要幾個變量)颂斜。最后一行是向終止集中添加常數(shù)。現(xiàn)在拾枣，這些參數(shù)的默認名稱為"ARG0"和"ARG1"沃疮，為了將它們改為"x","y"，可以使用下面的命令
#change the name of arguemnts from ARG0/ARG1 to x/y
pset.renameArguments(ARG0 = 'x')
pset.renameArguments(ARG1 = 'y')
在這個例子中梅肤，所有的函數(shù)都有兩個參數(shù)司蔬。例如，可以用一個參數(shù)的函數(shù)進行否定(??)
pset.addPrimitive(operator.neg, 1)
現(xiàn)在我們的primitive set就已經(jīng)可以產(chǎn)生一系列的樹了姨蝴。gp模塊包含了三種詞頭去表達產(chǎn)生的函數(shù)）——genFull(), genGrow()和genHalfAndHalf()俊啼。它們的第一個參數(shù)是primitive set，它們會通過一個primitive list返回一個有效的詞頭表達左医。list中的這些內(nèi)容可以被PrimitiveTree類讀取并且創(chuàng)建一個樹授帕。
expr = gp.genFull(pset, min_ = 1, max_ =3)
tree = gp.PrimitiveTree(expr)
- Strongly Typed GP(STGP)
在STGP中同木，每一個運算符和終止符都會被明確類型。運算符類型的輸出必須與輸入類型一致才可以被連接跛十。例如泉手，如果一個primitive返回了一個布爾變量，它會保證這個值在進行乘法運算后不是一個浮點數(shù)類型偶器，如果這個乘法運算只可以在float上進行操作的話斩萌。
def if_then_else(input, output1, output2):
return output1 if input else output2
pset = gp.PrimitiveSetTyped('main', [bool, float], float)
pset.addPrimitive(operator.xor, [bool, bool], bool)
pset.addPrimitive(operator.mul, [bool, bool], bool)
pset.addPrimitive(if_then_else, [bool, float, float], float)
pset.addTerminal(3.0, float)
pset.addTerminal(1, bool)
pset.renameArguments(ARG0 = 'x')
pset.renameArguments(ARG1 = 'y')
在上面的代碼中，我們首先定義了if_then_else函數(shù)屏轰，如果input為TRUE它會返回output1颊郎，否則返回output2。然后我們調(diào)用gp中的PrimitiveSetTyped對pset進行定義霎苗。再一次的姆吭，這個過程被命名為"main"，第二個元素定義了輸入到程序的類型唁盏。這里的'x'是一個布爾變量内狸，'y'是一個浮點型變量。第三個元素定義了程序的輸出類型是一個float類型±謇蓿現(xiàn)在昆淡，在向primitive(pset)中加入操作運算符時要考慮輸入和輸出的數(shù)據(jù)類型以及終止結(jié)點的數(shù)據(jù)類型。例如刽严，我們定義的"if_then_else"函數(shù)的第一個元素是布爾變量昂灵，第二個和第三個元素被定義為返回一個float型變量。這個函數(shù)就被定義為返回一個float型變量舞萄。我們現(xiàn)在了解到了乘法運算只可以使用3.0眨补，if_then_else函數(shù)或者輸入的'y'。
上面的代碼可以產(chǎn)生左邊樣子的樹倒脓，但是不能產(chǎn)生右邊這種撑螺，這是因為類型限制。(xor是bool類型的輸入輸出崎弃，因此不能使用y和3.0)
注意：每一代的樹是隨機生成的甘晤，同時確保遵守類型約束。如果任何的運算符有一種輸入類型是沒有運算符和終止點可以提供的話吊履，則它很有可能會被放置在樹中安皱，由于生成器的限制會導致不可能生成這些樹。例如艇炎，當產(chǎn)生一個高度為二的完全二叉樹時酌伊，假設(shè)''op'采取一個布爾變量和一個浮點型變量進行計算，"and"采取兩個布爾變量，"neg"則采用一個浮點型變量居砖，沒有終止結(jié)點被定義虹脯，同時也沒有元素是布爾型。如果沒有終止結(jié)點放置在neg下面的話奏候，這種情況將會發(fā)生
在這個例子中循集，DEAP會產(chǎn)生一個IndexError，"The gp.generate function tried to add a terminal of type float, but there is none available"蔗草。
上面這個例子說的大概就是在使用STGP時咒彤，必須要將所有類型的常量定義完整，這樣才可以保證在初始化生成樹結(jié)構(gòu)時候不會出錯咒精。
- Ephemeral Constants
一個臨時常量指的是封裝在終止集的一個值镶柱，這個值通過給定的函數(shù)在運行過程中產(chǎn)生。臨時常量允許終止集有不一樣的值模叙。例如歇拆，為了創(chuàng)建一個[-1,1]的臨時常量，我們可以使用
pset.addEphemeralConstant('m1',lambda: random.uniform(-1, 1), float)
臨時常量一旦輸入到樹中就不會被更改范咨，除非它被另一個臨時常量替代故觅。由于它是一個終止結(jié)點，臨時常量可以被限制類型(這個是必須的,名字+數(shù)據(jù)類型)
pset.addEphemeralConstant('m1',lambda: random.uniform(-10, 10), int)
- Generation of Tree Individuals
上兩節(jié)提出的代碼產(chǎn)生了有效地樹渠啊。然而输吏，在操作和算法教程中，這些樹還沒有成為一個有效的個體昭抒。creator和toolbox是一定要聯(lián)合起來的评也，我們需要創(chuàng)造一個Fitness類和一個Individual類炼杖。除了適應(yīng)度之外灭返，還要在Individual()中加入primitive set。這將會通過使用一些gp操作符對個體進行修改實現(xiàn)坤邪。
#creating fitness function and individual
creator.create('FitnessMin', base.Fitness, weights=(-1.0,))
creator.create('Individual', gp.PrimitiveTree, fitness = creator.FitnessMin,
pset = pset)
#register them
toolbox = base.Toolbox()
toolbox.register('expr', gp.genFull, pset = pset, min_=1, max_ = 3)
toolbox.register('individual', tools.initRepeat, creator.Individual,
toolbox.expr)
toolbox.individual(n=1)
- Evaluation of Trees
在DEAP中熙含，樹可以轉(zhuǎn)化為可讀的Python代碼并且可以通過gp模塊中的函數(shù)編輯為Python編碼的對象。第一個函數(shù)為str()艇纺，它可以對表達式樹和表達式進行轉(zhuǎn)化怎静。例如，下面的例子將會產(chǎn)生一個樹并且從第一個primitive例子中輸出一個代碼：
>>> expr = genFull(pset, min_=1, max_=3)
>>> tree = PrimitiveTree(expr)
>>> str(tree)
'mul(add(x, x), max(y, x))'
現(xiàn)在黔衡，代表這個程序的字符串就被創(chuàng)建了蚓聘，但它并不可以被處理。為了讓它能夠被處理盟劫，我們不得不使用Python代碼編輯一個表達式夜牡。由于這個函數(shù)有兩個輸入，我們希望去編輯一個可調(diào)用的對象侣签。這可以通過compile()實現(xiàn)塘装，這個函數(shù)有兩個參數(shù)：要去編輯的表達式以及其相關(guān)的primitive set急迂。下面的例子編輯了之前的樹，并且計算了它們在x=1蹦肴，y=2時的結(jié)果
toolbox.register("compile", gp.compile, pset=pset)
function = toolbox.compile(tree)
function(1,2) # x = 1, y = 2
當產(chǎn)生一個沒有任何輸入的程序時僚碎，compile也可以使用byte code進行表達，一個這樣的例子在AAP(Artificial Ant Problem)算法中有介紹阴幌。
- Tree Size Limit and Bloat Control
由于DEAP使用的是Python解析器去編寫代碼并表達樹勺阐，它繼承了py的一些限制。最常見的限制是解析堆棧限制矛双。Python編譯器的堆棧限制通常固定在92到99之間皆看，這就意味著最多只有91個運算符可以實施，換句話說背零，一個樹的最大深度為91腰吟，當超出這個限制時，Python會報錯
s_push: parser stack overflow
Traceback (most recent call last):
[...]
MemoryError
由于限制時在編譯器中是硬編碼的徙瓶，去提升這個限制是比較困難的毛雇。除此之外，這些錯誤通常源于GP中的“膨脹”現(xiàn)象侦镇，也就是說灵疮，產(chǎn)生的個體包含了太多的運算符，這個問題常常會導致進化的停滯壳繁。為了避免這種情況的發(fā)生震捣，DEAP提供了不同的功能去限制樹的大小和高度，這些函數(shù)也會在Operator中介紹闹炉。
- Plotting Trees
函數(shù)deap.gp.graph()可以返回必要的元素去將樹結(jié)構(gòu)繪制出來蒿赢，它使用的是NetworX和pygraphviz。這個圖像函數(shù)使用有效地PrimitiveTree對象并且返回一個結(jié)點列表渣触，列表的邊緣和字典通過每個結(jié)點的標簽相連羡棵。它可以像如下一樣進行使用
from deap import base, creator, gp
pset = gp.PrimitiveSet("MAIN", 1)
pset.addPrimitive(operator.add, 2)
pset.addPrimitive(operator.sub, 2)
pset.addPrimitive(operator.mul, 2)
pset.renameArguments(ARG0='x')
creator.create("Individual", gp.PrimitiveTree)
toolbox = base.Toolbox()
toolbox.register("expr", gp.genHalfAndHalf, pset=pset, min_=1, max_=2)
toolbox.register("individual", tools.initIterate, creator.Individual, toolbox.expr)
expr = toolbox.individual()
nodes, edges, labels = gp.graph(expr)
### Graphviz Section ###
import pygraphviz as pgv
g = pgv.AGraph()
g.add_nodes_from(nodes)
g.add_edges_from(edges)
g.layout(prog="dot")
for i in nodes:
n = g.get_node(i)
n.attr["label"] = labels[i]
g.draw("tree.pdf")
- 總結(jié)
這一節(jié)主要講的是如何通過gp模塊的一些操作，對樹結(jié)構(gòu)進行初始化以及通過str嗅钻、toolbox.compie等方法實現(xiàn)字符串與樹之間的相互轉(zhuǎn)化皂冰。大致流程為
1、pset的創(chuàng)建养篓，使用pset = gp.PrimitiveSet('MAIN', 2)進行創(chuàng)建秃流，main固定，大小寫不限柳弄。2為樹內(nèi)變量的個數(shù)舶胀，可更改，但在后面的聲明中都要提到。
2峻贮、pset添加運算符席怪，添加函數(shù)"pset.addPrimitive(function, number)"，function指的是函數(shù)名稱纤控，number指的是該函數(shù)包含的運算符目數(shù)挂捻。
3、pset添加終止結(jié)點船万，"pset.addTerminal(3, dtype)"刻撒，3指的是常量，必須與dtype類型一致耿导。同時也可以用臨時常量隨機生成：pset.addEphemeralConstant('m12',lambda: random.uniform(-1, 1), float)
4声怔、pset更改變量名：pset.renameArguments(ARG0="x")
將ARG0改為x，更改的數(shù)目與step1中創(chuàng)建的數(shù)目保持一致舱呻。
5醋火、得到表達式expr = genFull(pset, min_=1, max_=3)
，pset為先前創(chuàng)建好的符號集箱吕，min_與max_分別表示每一個個體中表達式樹數(shù)目的范圍芥驳，這里是13,堂鲤，但生成的數(shù)目為04逮光，這應(yīng)該與Python的索引從0開始有關(guān)冒签。樹結(jié)構(gòu)為tree = PrimitiveTree(expr)坐求。
5、樹結(jié)構(gòu)的轉(zhuǎn)化需要先tree轉(zhuǎn)化為字符串俱饿，命令為str(tree)柴梆，接下來是將字符串轉(zhuǎn)化為函數(shù)胀瞪，首先對compile進行register:toolbox.register("compile", gp.compile, pset=pset)熏瞄，接下來再進行轉(zhuǎn)化function = toolbox.compile(tree)脚祟，數(shù)值求解則根據(jù)設(shè)定的變量數(shù)目進行，function(x1,x2,x3...)巴刻。
上述步驟為GP乃至GEP所需的關(guān)鍵步驟愚铡，這也是它們與GA和其它基于list進行演化的演化算法的最大區(qū)別。下一節(jié)將會通過書寫GP算法進行一個簡單的函數(shù)發(fā)現(xiàn)問題求解胡陪。
