1
# This file is part of EAP.
3
# EAP is free software: you can redistribute it and/or modify
4
# it under the terms of the GNU Lesser General Public License as
5
# published by the Free Software Foundation, either version 3 of
6
# the License, or (at your option) any later version.
8
# EAP is distributed in the hope that it will be useful,
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11
# GNU Lesser General Public License for more details.
13
# You should have received a copy of the GNU Lesser General Public
14
# License along with EAP. If not, see <http://www.gnu.org/licenses/>.
16
"""The :mod:`gp` module provides the methods and classes to perform
17
Genetic Programming with EAP. It essentially contains the classes to
18
build a Genetic Program Tree, and the functions to evaluate it.
20
This module support both strongly and loosely typed GP.
29
from itertools import repeat
30
from collections import defaultdict
32
# Define the name of type for any types.
35
## GP Tree utility functions
37
def evaluate(expr, pset=None):
38
"""Evaluate the expression expr into a string if pset is None
39
or into Python code is pset is not None.
44
return str(func(*[_stringify(value) for value in expr[1:]]))
48
return eval(_stringify(expr), pset.func_dict)
50
return _stringify(expr)
53
"""Evaluate a list of ADF and return a dict mapping the ADF name with its
57
for i, expr in enumerate(reversed(seq[1:])):
58
func = lambdify(expr.pset, expr)
59
adfdict.update({expr.pset.__name__ : func})
60
for expr2 in reversed(seq[1:i+1]):
61
expr2.pset.func_dict.update(adfdict)
65
def lambdify(pset, expr):
66
"""Return a lambda function of the expression.
69
This function is a stripped version of the lambdify
70
function of sympy0.6.6.
73
args = ",".join(a for a in pset.arguments)
74
lstr = "lambda %s: %s" % (args, expr)
75
return eval(lstr, dict(pset.func_dict))
77
def lambdifyList(expr):
78
"""Return a lambda function created from a list of trees. The first
79
element of the list is the main tree, and the following elements are
80
automatically defined functions (ADF) that can be called by the first
83
adfdict = evaluateADF(expr)
84
expr[0].pset.func_dict.update(adfdict)
85
return lambdify(expr[0].pset, expr[0])
87
## Loosely + Strongly Typed GP
89
class Primitive(object):
90
"""Class that encapsulates a primitive and when called with arguments it
91
returns the Python code to call the primitive with the arguments.
94
>>> pr = Primitive(operator.mul, (int, int), int)
99
def __init__(self, primitive, args, ret = __type__):
100
self.name = primitive.__name__
101
self.arity = len(args)
104
args = ", ".join(repeat("%s", self.arity))
105
self.seq = "%s(%s)" % (self.name, args)
106
def __call__(self, *args):
107
return self.seq % args
111
class Operator(Primitive):
112
"""Class that encapsulates an operator and when called with arguments it
113
returns the Python code to call the operator with the arguments. It acts
114
as the Primitive class, but instead of returning a function and its
115
arguments, it returns an operator and its operands.
118
>>> op = Operator(operator.mul, (int, int), int)
121
>>> op2 = Operator(operator.neg, (int,), int)
126
symbols = {"add" : "+", "sub" : "-", "mul" : "*", "div" : "/", "neg" : "-",
127
"and_" : "and", "or_" : "or", "not_" : "not",
128
"lt" : "<", "eq" : "==", "gt" : ">", "geq" : ">=", "leq" : "<="}
129
def __init__(self, operator, args, ret = __type__):
130
Primitive.__init__(self, operator, args, ret)
132
self.seq = "%s(%s)" % (self.symbols[self.name], "%s")
134
self.seq = "(%s %s %s)" % ("%s", self.symbols[self.name], "%s")
136
raise ValueError("Operator arity can be either 1 or 2.")
138
class Terminal(object):
139
"""Class that encapsulates terminal primitive in expression. Terminals can
140
be symbols, values, or 0-arity functions.
142
def __init__(self, terminal, ret = __type__):
145
self.value = terminal.__name__
146
except AttributeError:
147
self.value = terminal
151
return str(self.value)
153
class Ephemeral(Terminal):
154
"""Class that encapsulates a terminal which value is set at run-time.
155
The value of the `Ephemeral` can be regenerated with the method `regen`.
157
def __init__(self, func, ret = __type__):
159
Terminal.__init__(self, self.func(), ret)
161
self.value = self.func()
163
class EphemeralGenerator(object):
164
"""Class that generates `Ephemeral` to be added to an expression."""
165
def __init__(self, ephemeral, ret = __type__):
167
self.name = ephemeral.__name__
168
self.func = ephemeral
170
return Ephemeral(self.func, self.ret)
174
class PrimitiveSetTyped(object):
175
"""Class that contains the primitives that can be used to solve a
176
Strongly Typed GP problem. The set also defined the researched
177
function return type, and input arguments type and number.
179
def __init__(self, name, in_types, ret_type, prefix = "ARG"):
180
self.terminals = defaultdict(list)
181
self.primitives = defaultdict(list)
183
self.func_dict = dict()
191
for i, type_ in enumerate(in_types):
192
self.arguments.append(prefix + ("%s" % i))
193
PrimitiveSetTyped.addTerminal(self, self.arguments[-1], type_)
195
def renameArguments(self, new_args):
196
"""Rename function arguments with new arguments name *new_args*.
198
for i, argument in enumerate(self.arguments):
199
if new_args.has_key(argument):
200
self.arguments[i] = new_args[argument]
201
for terminals in self.terminals.values():
202
for terminal in terminals:
203
if ( isinstance(terminal, Terminal) and
204
new_args.has_key(terminal.value) ):
205
terminal.value = new_args[terminal.value]
207
def addPrimitive(self, primitive, in_types, ret_type):
208
"""Add a primitive to the set.
210
*primitive* is a callable object or a function.
211
*in_types* is a list of argument's types the primitive takes.
212
*ret_type* is the type returned by the primitive.
215
prim = Operator(primitive, in_types, ret_type)
216
except (KeyError, ValueError):
217
prim = Primitive(primitive, in_types, ret_type)
218
self.primitives[ret_type].append(prim)
219
self.func_dict[primitive.__name__] = primitive
220
self.prims_count += 1
222
def addTerminal(self, terminal, ret_type):
223
"""Add a terminal to the set.
225
*terminal* is an object, or a function with no arguments.
226
*ret_type* is the type of the terminal.
228
if callable(terminal):
229
self.func_dict[terminal.__name__] = terminal
230
prim = Terminal(terminal, ret_type)
231
self.terminals[ret_type].append(prim)
232
self.terms_count += 1
234
def addEphemeralConstant(self, ephemeral, ret_type):
235
"""Add an ephemeral constant to the set. An ephemeral constant
236
is a no argument function that returns a random value. The value
237
of the constant is constant for a Tree, but may differ from one
240
*ephemeral* function with no arguments that returns a random value.
241
*ret_type* is the type of the object returned by the function.
243
prim = EphemeralGenerator(ephemeral, ret_type)
244
self.terminals[ret_type].append(prim)
245
self.terms_count += 1
247
def addADF(self, adfset):
248
"""Add an Automatically Defined Function (ADF) to the set.
250
*adfset* is a PrimitiveSetTyped containing the primitives with which
251
the ADF can be built.
253
prim = Primitive(adfset, adfset.ins, adfset.ret)
254
self.primitives[adfset.ret].append(prim)
255
self.prims_count += 1
258
def terminalRatio(self):
259
"""Return the ratio of the number of terminals on the number of all
262
return self.terms_count / float(self.terms_count + self.prims_count)
264
class PrimitiveSet(PrimitiveSetTyped):
265
"""Class same as PrimitiveSetTyped, except there is no
268
def __init__(self, name, arity, prefix="ARG"):
269
args = [__type__]*arity
270
PrimitiveSetTyped.__init__(self, name, args, __type__, prefix)
272
def addPrimitive(self, primitive, arity):
273
"""Add primitive *primitive* with arity *arity* to the set."""
274
assert arity > 0, "arity should be >= 1"
275
args = [__type__] * arity
276
PrimitiveSetTyped.addPrimitive(self, primitive, args, __type__)
278
def addTerminal(self, terminal):
279
"""Add a terminal to the set."""
280
PrimitiveSetTyped.addTerminal(self, terminal, __type__)
282
def addEphemeralConstant(self, ephemeral):
283
"""Add an ephemeral constant to the set."""
284
PrimitiveSetTyped.addEphemeralConstant(self, ephemeral, __type__)
286
class PrimitiveTree(base.Tree):
287
"""Tree class faster than base Tree, optimized for Primitives."""
294
state.append(elem._getstate())
295
except AttributeError:
299
def __deepcopy__(self, memo):
300
"""Deepcopy a Tree by first converting it back to a list of list.
302
This deepcopy is faster than the default implementation. From
303
quick testing, up to 1.6 times faster, and at least 2 times less
306
new = self.__class__(self._getstate())
307
new.__dict__.update(copy.deepcopy(self.__dict__, memo))
310
# Expression generation functions
312
def generateRamped(pset, min_, max_, type_=__type__):
313
"""Generate an expression with a PrimitiveSet *pset*.
314
Half the time, the expression is generated with generateGrow,
315
the other half, the expression is generated with generateFull.
317
method = random.choice((generateGrow, generateFull))
318
return method(pset, min_, max_, type_)
320
def generateFull(pset, min_, max_, type_=__type__):
321
"""Generate an expression where each leaf has a the same depth
322
between *min* and *max*.
324
def condition(max_depth):
325
return max_depth == 0
326
return _generate(pset, min_, max_, condition, type_)
328
def generateGrow(pset, min_, max_, type_=__type__):
329
"""Generate an expression where each leaf might have a different depth
330
between *min* and *max*.
332
def condition(max_depth):
333
return max_depth == 0 or random.random() < pset.terminalRatio
334
return _generate(pset, min_, max_, condition, type_)
336
def _generate(pset, min_, max_, condition, type_=__type__):
337
def genExpr(max_depth, type_):
338
if condition(max_depth):
339
term = random.choice(pset.terminals[type_])
342
prim = random.choice(pset.primitives[type_])
344
args = (genExpr(max_depth-1, arg) for arg in prim.args)
347
max_depth = random.randint(min_, max_)
348
expr = genExpr(max_depth, type_)
349
if not isinstance(expr, list):
353
if __name__ == "__main__":
added
removed
eap/gp.py
