I'm fairly new to python and the lists and indexing is giving me some trouble.
What I want to do is : ', Get two individuals that represent a RPN expression, individual 1 and individual 2 for axample :
i1=['3', 'x', '*', '3' ,'4' ,'*', '/']
i2=['x', '4', '/', 'x' ,'4' ,'+', '-']
then, get a subset, of them and swap the subset , like so :
from i1 i'd take subset [ '3' ,'4' ,'*'] and from i2 ['4'] (the final 3) then do a crossover producint two outputs :
out1=['3', 'x', '*','4' , '/']
out2=['x', '3' ,'4' ,'*', '/', 'x' ,'6' ,'+', '-']
the codeI've made is the folloing, and it keeps giving me erroneous results, like off by one errors, I dont want to go into the for cycle route, as I bet there is a more pythonesque way to do so. Can any one giceme an hand please ?
def crossover(individual1,individual2,treedepth):
from commonfunctions import getDepth,traverse,get_random_operator
from commonfunctions import isOperator
from generators import generate_RPN_expr
#simple element mutation
cxposindividual1 = random.randint(0, len(individual1) - 1)
cxposindividual2 = random.randint(0, len(individual2) - 1)
subtree1=traverse(individual1,cxposindividual1)
subtree2 = traverse(individual2, cxposindividual2)
individual1depth=getDepth(individual1)
individual2depth = getDepth(individual2)
subtree1depth=getDepth(subtree1)
subtree2depth = getDepth(subtree2)
output1=list()
output1[:]=[]
output2=list()
output2[:]=[]
#todo debug this !!!!
#verificar se ecsolhemos um operador ou um nó terminal
output1 = individual1[:len(individual1)+1-cxposindividual1-len(subtree1)]+subtree2+individual1[len(individual1)-cxposindividual1+1:]
output2 = individual2[:len(individual2) + 1 - cxposindividual2 - len(subtree2)] + subtree1 + individual2[len(individual2) - cxposindividual2 + 1:]
if len(output1) == 2 or len(output2) == 2:
print('argh>>>') # problema !!!!
#print ('CX')
return (output1,output2)
The traverse function returns the subtree in the selected position. getDepth isnt being used as yet.
Thanks
Jorge
New Code
def crossover(individual1,individual2,treedepth):
from commonfunctions import getDepth,traverse,get_random_operator,traverse_with_indexes
from commonfunctions import isOperator
r1 = random.randrange(len(individual1))
r2 = random.randrange(len(individual2))
st1 = traverse(individual1, r1)
st2 = traverse(individual2, r2)
slice1 = slice(r1, r1+len(st1))
slice2 = slice(r2, r2+len(st2))
i1,i2 = individual1[:],individual2[:]
a,b=i1[slice1],i2[slice2]
i1[slice1],i2[slice2] = i2[slice2],i1[slice1]
return i1, i2
Here ,individual 1 equals ['3.8786681846845', 'x', '+'] and st1 = ['x'] the slice is 2,3 where I supose it should be 1,2 but ...
where individual 2 = ['x'] st2 = ['x'] the slice is 0,1 wich is fine !!!
I'm tempted to make some if blocks with the sizesfor exceptions, but I dont like exceptions
Thanks
I suspect your problem comes from the fact that slices in python do not include their final index. That is, [0:1] is a slice with only one element, [0], contained in it.
Your example:
i1=['3', 'x', '*', '3' ,'4' ,'*', '/']
i2=['x', '4', '/', 'x' ,'4' ,'+', '-']
# 0 1 2 3 4 5 6
Then:
temp1 = i1[3:6] # 3,4,*
temp2 = i2[1:2] # 4
Then:
print(i1)
print(i2)
i1[3:6] = temp2
i2[1:2] = temp1
print(i1)
print(i2)
Finally, because awesome, you can do this:
i1[3:6],i2[1:2] = i2[1:2],i1[3:6]
Or this:
A = slice(3,6)
B = slice(1,2)
i1[A],i2[B] = i2[B],i1[A]
Edit
Going farther, you can use random.randrange() to avoid fencepost errors, and do something like:
def crossover(individual1,individual2,treedepth):
r1 = random.randrange(len(individual1))
r2 = random.randrange(len(individual2))
st1 = traverse(individual1, r1)
st2 = traverse(individual2, r2)
slice1 = slice(r1, r1+len(st1))
slice2 = slice(r2, r2+len(st2))
# fazer pseudonimos
i1,i2 = individual1,individual2
# o fazer copias
i1,i2 = individual1[:],individual2[:]
i1[slice1],i2[slice2] = i2[slice2],i1[slice1]
return i1, i2
The purpose of this funtion is to return the 'meaningfull subtree that starts at position start, (since the program is a rpn representation)
def traverse(inputexpr,start):
from copy import copy,deepcopy
components=list()
components[:]=[]
components=inputexpr[0:len(inputexpr)-start+1]
components.reverse()
pos=0
result=list()
result[:]=[]
score=0
if isOperator(components[pos]):
result.append(components[pos])
score=score+getArity(components[pos])
else:
result.append(components[pos])
score=score -1
pos=pos+1
while score>0:
if isOperator(components[pos]):
result.append(components[pos])
score = score + getArity(components[pos])-1
else:
result.append(components[pos])
score = score - 1
pos = pos + 1
result.reverse()
return result
Second Edit
Consider this reimplementation. Does this do what you want?
_Arity = {op:2 for op in '*/+-%'}
def getArity(op):
return _Arity[op] if op in _Arity else 0
def isOperator(op):
return op in _Arity
def traverse(inputexpr, pos):
"""
Return the meaningful subtree of inputexpr that has its upper node
at position pos. Given an input like this:
[ A, B, +, 5, * ]
# 0 1 2 3 4
Here are the expected results:
0: [ A ]
1: [ B ]
2: [ A B + ]
3: [ 5 ]
4: [ A B + 5 * ]
"""
chop = pos + 1
subtree = inputexpr[:chop]
score = 1
while score:
chop -= 1
score += getArity(subtree[chop]) - 1
return subtree[chop:]
i1=['3', 'x', '*', '3' ,'4' ,'*', '/']
i2=['x', '4', '/', 'x' ,'4' ,'+', '-']
for i in range(len(i1)):
print("#: {}, subtree= {}".format(i, traverse(i1, i)))
#output tree
output1=list()
output1[:]=[]
output2=list()
output2[:]=[]
i1p1 = individual1[:len(individual1) - len(subtree1) - cxposindividual1]
i1p2 = subtree2
i1p3 = individual1[len(i1p1) + len(subtree1):]
i2p1 = individual2[:len(individual2) - len(subtree2) - cxposindividual2]
i2p2 = subtree1
i2p3 = individual2[len(i2p1) + len(subtree2):]
output1=i1p1+i1p2+i1p3
output2=i2p1+i2p2+i2p3
Thanks a LOT Austin, thanks to you I found the bug that was bugging my other bugs. After getting it to work, I'll implement it in a more pythonesque way. Right now I'm using this very verbose code soI dont getlots in the language details.
Again Thanks