That is a very informative answer, thanks!

I seem to have forgotten that __init__ is an actual function that can do things.

This is really for a module that is will attempt to find the sequence function for a given number sequence using a genetic algorithm.

While refactoring I thought it would be nice if I had my own datatype from a class called Expression so started fiddling with __repr__ and such but not sure yet.

When I was testing the original code it seemed too slow so I thought it must be because of all the recursion going on and I heard it's not good to use recursion with python because function calls are expensive. But I'll stick with it if an iterative solution is going to be slower.

This is my old code.

- Code: Select all
`from random import choice, random`

class ExpressionFormConstructor(object):

"""

BNF specificaton:

<expr_form> ::= (<operator>, <operand>, <operand>)

<operator> ::= "+" | "-" | "*" | "/" | "^"

<operand> ::= "e" | "c" | "x"

"e" ::= <expr_form>

"c" ::= int

"x" ::= x

"""

non_terminating_expr_forms = (

('+', 'x', 'e'),

('-', 'x', 'e'),

('*', 'x', 'e'),

('/', 'x', 'e'))

terminating_expr_forms = (

('+', 'x', 'c'),

('-', 'x', 'c'),

('*', 'x', 'c'),

('/', 'x', 'c'),

('^', 'x', 'c'))

all_expr_forms = non_terminating_expr_forms + terminating_expr_forms

def rand_form(self, depth=0):

"""

rand_form() -> tuple(expr_form), list(constants)

depth refers to maximum nested depth of expr_form

"""

constants = []

if depth is 0:

expr_form = list(choice(self.terminating_expr_forms))

else:

expr_form = list(choice(self.all_expr_forms))

if expr_form[1] is 'c':

constants.append(0)

elif expr_form[1] is 'e':

expr_form[1], con = self.rand_form(depth - 1)

constants.extend(con)

else:

pass

if expr_form[2] is 'c':

constants.append(0)

elif expr_form[2] is 'e':

expr_form[2], con = self.rand_form(depth - 1)

constants.extend(con)

else:

pass

return tuple(expr_form), constants

class ExpressionForm(object):

symb_to_op = {'+':lambda a, b: a + b,

'-':lambda a, b: a - b,

'*':lambda a, b: a * b,

'/':lambda a, b: float(a) / b,

'^':pow}

def __init__(self, expr_form, constants):

self.expr_form = expr_form

self.constants = constants # number of constants.

self.population = [] # each individual is a unique tuple of constants.

self.graveyard = set() # contains hash values for failed individuals.

def __str__(self, expr_form=None, root=True):

expr_form = self.expr_form if expr_form is None else expr_form

symb, A, B = expr_form

A = A if A in 'cx' else self.__str__(A, False)

B = B if B in 'cx' else self.__str__(B, False)

return ('%s %s %s' if root else '(%s %s %s)') % (A, symb, B)

def evaluate(self, x, ind, expr=None, c=0):

"""

x -> int, ind -> from self.population

"""

symb, A, B = expr if expr else self.expr_form

op = self.symb_to_op[symb]

root = True if expr is None else False

if A is 'c':

A = ind[c]

c += 1

elif A is 'x':

A = x

else: # A is an expr_form

A, c = self.evaluate(x=x, ind=ind, expr=A, c=c)

if B is 'c':

B = ind[c]

c += 1

elif B is 'x':

B = x

else: # B is an expr_form

B, c = self.evaluate(x=x, ind=ind, expr=B, c=c)

return op(A, B) if root else (op(A, B), c)

# ---------- testing ---------->

##from random import randint

##

##Constructor = ExpressionFormConstructor()

##

##def test():

## Expr = ExpressionForm(*Constructor.rand_form(3))

##

## # populate

## for ind in range(100):

## Expr.population.append(tuple([randint(1, 10) for constant in Expr.constants]))

##

## # test and remove error prone individuals

## for ind in range(len(Expr.population)):

## try:

## print [Expr.evaluate(x, Expr.population[ind]) for x in range(10)]

## except (OverflowError, ZeroDivisionError, ValueError) as err:

## print err

## Expr.population[ind] = False

## Expr.population = [ind for ind in Expr.population if ind]

## print "lost:", 100 - len(Expr.population), "individuals"

##

##while True:

## raw_input()

## test()

I'm not sure if this is a good design but this is what it's supposed to do.

I delegated the task of generating random expression forms to a class on it's own because if you do it completely randomly there's a few errors that occur as some forms are error prone or just not valid. like (x ^ e) where e is another expression form itself or (c / x) where c is some constant and x can be 0.

ExpressionForm instances will contain a form attribute like (x + (c * x)), and a constants attribute which should be a list of integers for all the constants in the form. Constants are kept separate from the form because I thought it would be simpler and more efficient when making changes to the constants.

A third class called GA or something will will handle the main algorithm.

procedure:

- The third class which I haven't yet made called GA will create a population of unique ExpressionForm instances.

- ExpressionForm instances will have a method optimize(seq, runtime) which will apply a simple stochastic optimization algorithm to find the best set of constants to use with the expression form for the given sequence. This is why constants are kept in a separate list from the form.

- ExpressionForm instances will have a fitness rank which is determined after the simple optimization is done.

- Some selection takes place

- Crossover/mutation

- etc

I really don't know yet. Can you suggest a better layout?