DEAP1.2.2(五) 遗传程序设计(Genetic Prog

(五) 遗传程序设计(Genetic Programming)
GP是演化计算中的一个特殊领域，它主要针对自动构建程序去独立解决问题(。。。)。尽管有一些其它形式去完成进化，但最主要的形式是语法树(下面用表达式树代替)。

gptree.png

例如，上面的图是一个用于表示max(x+3*y, y+x)的程序。对于这个树和其它例子，树的叶子结点是绿色的，它们被叫做“终止符”；红色的节点叫做“符号集”。终止集被分成了两类——常数(数字)和参数(x,y,z...)。这些常数在整个进化过程中保持不变(why)，而参数是由程序输入的。在之前提出的树中，参数是变量x和y，而常数是3。

在DEAP中，用户定义的符号集和终止集都被定义在primitive set中。现在，有两种型号的primitive set：宽松式和健壮式。(loosely & strongly)

1. Loosely Typed GP(LTGP)
   LTGP不会在结点间强制明确类型(？？)。更多可以确定的是，primitive集合的参数可以是任意的运算符或者终止节点。

下面的代码定义了一个宽松的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)

第一行创建了primitive set(pset)。它的参数是通过("MAIN")产生的，并且数目为2。后面的三行是添加符号集的函数，第一个参数是函数名称，第二个是函数的运算符目数(就是完成这个运算需要几个变量)。最后一行是向终止集中添加常数。现在，这些参数的默认名称为"ARG0"和"ARG1"，为了将它们改为"x","y"，可以使用下面的命令

#change the name of arguemnts from ARG0/ARG1 to x/y
pset.renameArguments(ARG0 = 'x')
pset.renameArguments(ARG1 = 'y')

在这个例子中，所有的函数都有两个参数。例如，可以用一个参数的函数进行否定(??)

pset.addPrimitive(operator.neg, 1)

现在我们的primitive set就已经可以产生一系列的树了。gp模块包含了三种词头去表达产生的函数）——genFull(), genGrow()和genHalfAndHalf()。它们的第一个参数是primitive set，它们会通过一个primitive list返回一个有效的词头表达。list中的这些内容可以被PrimitiveTree类读取并且创建一个树。

expr = gp.genFull(pset, min_ = 1, max_ =3)
tree = gp.PrimitiveTree(expr)

2. Strongly Typed GP(STGP)
   在STGP中，每一个运算符和终止符都会被明确类型。运算符类型的输出必须与输入类型一致才可以被连接。例如，如果一个primitive返回了一个布尔变量，它会保证这个值在进行乘法运算后不是一个浮点数类型，如果这个乘法运算只可以在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函数，如果input为TRUE它会返回output1，否则返回output2。然后我们调用gp中的PrimitiveSetTyped对pset进行定义。再一次的，这个过程被命名为"main"，第二个元素定义了输入到程序的类型。这里的'x'是一个布尔变量，'y'是一个浮点型变量。第三个元素定义了程序的输出类型是一个float类型。现在，在向primitive(pset)中加入操作运算符时要考虑输入和输出的数据类型以及终止结点的数据类型。例如，我们定义的"if_then_else"函数的第一个元素是布尔变量，第二个和第三个元素被定义为返回一个float型变量。这个函数就被定义为返回一个float型变量。我们现在了解到了乘法运算只可以使用3.0，if_then_else函数或者输入的'y'。

上面的代码可以产生左边样子的树，但是不能产生右边这种，这是因为类型限制。(xor是bool类型的输入输出，因此不能使用y和3.0)

gptypedtrees.png

注意：每一代的树是随机生成的，同时确保遵守类型约束。如果任何的运算符有一种输入类型是没有运算符和终止点可以提供的话，则它很有可能会被放置在树中，由于生成器的限制会导致不可能生成这些树。例如，当产生一个高度为二的完全二叉树时，假设''op'采取一个布尔变量和一个浮点型变量进行计算，"and"采取两个布尔变量，"neg"则采用一个浮点型变量，没有终止结点被定义，同时也没有元素是布尔型。如果没有终止结点放置在neg下面的话，这种情况将会发生

gptypederrtree.png

在这个例子中，DEAP会产生一个IndexError，"The gp.generate function tried to add a terminal of type float, but there is none available"。

上面这个例子说的大概就是在使用STGP时，必须要将所有类型的常量定义完整，这样才可以保证在初始化生成树结构时候不会出错。

3. Ephemeral Constants
   一个临时常量指的是封装在终止集的一个值，这个值通过给定的函数在运行过程中产生。临时常量允许终止集有不一样的值。例如，为了创建一个[-1,1]的临时常量，我们可以使用

pset.addEphemeralConstant('m1',lambda: random.uniform(-1, 1), float)

临时常量一旦输入到树中就不会被更改，除非它被另一个临时常量替代。由于它是一个终止结点，临时常量可以被限制类型(这个是必须的,名字+数据类型)

pset.addEphemeralConstant('m1',lambda: random.uniform(-10, 10), int)

4. Generation of Tree Individuals
   上两节提出的代码产生了有效地树。然而，在操作和算法教程中，这些树还没有成为一个有效的个体。creator和toolbox是一定要联合起来的，我们需要创造一个Fitness类和一个Individual类。除了适应度之外，还要在Individual()中加入primitive set。这将会通过使用一些gp操作符对个体进行修改实现。

#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)

5. Evaluation of Trees
   在DEAP中，树可以转化为可读的Python代码并且可以通过gp模块中的函数编辑为Python编码的对象。第一个函数为str()，它可以对表达式树和表达式进行转化。例如，下面的例子将会产生一个树并且从第一个primitive例子中输出一个代码：

>>> expr = genFull(pset, min_=1, max_=3)
>>> tree = PrimitiveTree(expr)
>>> str(tree)
'mul(add(x, x), max(y, x))'

现在，代表这个程序的字符串就被创建了，但它并不可以被处理。为了让它能够被处理，我们不得不使用Python代码编辑一个表达式。由于这个函数有两个输入，我们希望去编辑一个可调用的对象。这可以通过compile()实现，这个函数有两个参数：要去编辑的表达式以及其相关的primitive set。下面的例子编辑了之前的树，并且计算了它们在x=1，y=2时的结果

toolbox.register("compile", gp.compile, pset=pset)

function = toolbox.compile(tree)

function(1,2) # x = 1, y = 2

当产生一个没有任何输入的程序时，compile也可以使用byte code进行表达，一个这样的例子在AAP(Artificial Ant Problem)算法中有介绍。

6. 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中的“膨胀”现象，也就是说，产生的个体包含了太多的运算符，这个问题常常会导致进化的停滞。为了避免这种情况的发生，DEAP提供了不同的功能去限制树的大小和高度，这些函数也会在Operator中介绍。

7. Plotting Trees
   函数deap.gp.graph()可以返回必要的元素去将树结构绘制出来，它使用的是NetworX和pygraphviz。这个图像函数使用有效地PrimitiveTree对象并且返回一个结点列表，列表的边缘和字典通过每个结点的标签相连。它可以像如下一样进行使用

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")

8. 总结
   这一节主要讲的是如何通过gp模块的一些操作，对树结构进行初始化以及通过str、toolbox.compie等方法实现字符串与树之间的相互转化。大致流程为
   1、pset的创建，使用pset = gp.PrimitiveSet('MAIN', 2)进行创建，main固定，大小写不限。2为树内变量的个数，可更改，但在后面的声明中都要提到。
   2、pset添加运算符，添加函数"pset.addPrimitive(function, number)"，function指的是函数名称，number指的是该函数包含的运算符目数。
   3、pset添加终止结点，"pset.addTerminal(3, dtype)"，3指的是常量，必须与dtype类型一致。同时也可以用临时常量随机生成：pset.addEphemeralConstant('m12',lambda: random.uniform(-1, 1), float)
   4、pset更改变量名：pset.renameArguments(ARG0="x")
   将ARG0改为x，更改的数目与step1中创建的数目保持一致。
   5、得到表达式expr = genFull(pset, min_=1, max_=3)
   ，pset为先前创建好的符号集，min_与max_分别表示每一个个体中表达式树数目的范围，这里是1_{3,，但生成的数目为0}4，这应该与Python的索引从0开始有关。树结构为tree = PrimitiveTree(expr)。
   5、树结构的转化需要先tree转化为字符串，命令为str(tree)，接下来是将字符串转化为函数，首先对compile进行register:toolbox.register("compile", gp.compile, pset=pset)，接下来再进行转化function = toolbox.compile(tree)，数值求解则根据设定的变量数目进行，function(x1,x2,x3...)。

上述步骤为GP乃至GEP所需的关键步骤，这也是它们与GA和其它基于list进行演化的演化算法的最大区别。下一节将会通过书写GP算法进行一个简单的函数发现问题求解。