import solution
import termNodes
import setNodes
import alterNodes
import selectNodes
import evalNodes
import listComp
import re
import random
import copy
allNodes = []
allNodes.extend(setNodes.setNodes)
allNodes.extend(evalNodes.evalNodes)
allNodes.extend(alterNodes.alterNodes)
allNodes.extend(selectNodes.selectNodes)
#allNodes.extend(listComp.listCompNodes)
[docs]def popNodes(node,a):
"""
This function is used to create a list of all nodes in a given bbsa. The list will be in pre order.
"""
a.append(node)
for x in node.down:
popNodes(x,a)
[docs]class bbsa:
"""
This class is the black box search algorithm. It contains the parse tree which is used to
evaluate the bbsa.
"""
def __init__(self,settings):
"""
Constructor for the bbsa
defaults all of the values and sets the values that are contained in the settings file
"""
self.root = None
self.runs = []
self.depth = 0
self.aveOps = 0.0
self.maxDepth = settings.maxDepth
self.maxIterations = settings.maxIterations
self.fitness = 0
self.converge = settings.converge
self.initPop = random.randint(0,settings.initPop)
self.size = 0
self.sets = {'last':[],'empty':[],'pers':{}}
self.settings = settings
self.logs = {}
self.numRuns = settings.numRuns
self.aveBest = 0.0
self.aveEval = 0.0
self.createRandom()
self.name = "bbsa"
[docs] def makeProg(self):
"""
This function generates the code that is used for external verification. It generates code in a post-order fashion.
This functions assumes that the structure of the algorithm has already been created
"""
tab = " "
indent = tab*2
prog = "import solution \nimport random\nimport settings\nimport logger\n"
prog+="from funcs import *\n"
prog+="""def kTourn(pop,k):
best = None
for i in xrange(k):
obj = random.choice(pop)
if not best or obj>best:
best = obj
return best"""+"\n\n"
prog+= "\"\"\""+str(self.toDict())+"\"\"\"\n\n"
prog+="\"\"\""+str(self.aveBest)+" "+str(self.aveEval)+"\"\"\"\n\n"
prog+="\"\"\""+str(self.settings.seed)+"\"\"\"\n"
prog += "def run(name=\""+self.name+"\",numRuns=10):\n\n"+tab
prog += "l = logger.logger(name)\n"+tab
prog += "curRun = 0\n"+tab
prog += "for w in xrange(numRuns):\n"+indent
prog += "s = settings.settings()\n"+indent
if self.settings.problemType:
prog += "s.problemType = \""+self.settings.problemType+"\"\n"+indent
else:
prog += "s.problemType = \"allOnes\"\n"+indent
prog += "s.maxEvals = "+str(self.settings.maxEvals)+"\n"+indent
prog += "s.maxIterations = "+str(self.settings.maxIterations)+"\n"+indent
prog += "s.converge = "+str(self.settings.converge)+"\n"+indent
prog += "s.numRuns = "+str(self.settings.numRuns)+"\n"+indent
prog += "s.solSet[\'length\'] = "+str(self.settings.solSet['length'])+"\n"+indent
prog += "s.initPop = "+str(self.initPop)+"\n"+indent
prog += "s.curEvals = 0"+"\n"+indent
prog += "last = [solution.solution(s) for x in xrange(s.initPop)]\n"+indent
prog += "for d in last:\n"+indent+tab
prog += "d.evaluate()\n"+indent
for key in self.sets['pers']:
prog+= key+"=[]\n"+indent
prog+="for it in xrange(s.maxIterations):\n"+indent+tab
prog+=self.root.makeProg(3,"0")
prog+="last=x0\n"+indent+tab
prog+="l.newIter(last,s.curEvals)\n"+indent+tab
prog+="if s.curEvals>=s.maxEvals:\n"+indent+tab+tab
prog+="break\n"+indent
prog+="for d in last:\n"+indent+tab
prog+="d.evaluate()\n"+indent
prog+="l.newIter(last,s.curEvals)\n"+indent
prog+="l.newRun()\n"+tab
prog+="l.log()\n"+tab
returnList = ""
for key in self.sets['pers']:
returnList+=","+key
prog+="\n"+tab+"return {\'sets\':[last"+returnList+"],\'settings\':s}"
return prog
[docs] def load(self,prog,parent=None,i=0):
"""
This function loads a bbsa into the parse tree structure from a dictionary that can be generated by the toDict() function.
"""
key =None
if type(prog) is not str:
key = prog.keys()[0]
else:
key = prog
cur = None
if key[:5]=='evalu':
if not parent:
self.root = evalNodes.eval(parent)
cur = self.root
else:
parent.down[i] = evalNodes.eval(parent)
cur = parent.down[i]
self.load(prog[key][0],cur,0)
elif key[:5]=='addSe':
if not parent:
self.root = setNodes.addSet(parent)
cur = self.root
else:
parent.down[i] = setNodes.addSet(parent)
cur = parent.down[i]
self.load(prog[key][0],cur,0)
self.load(prog[key][1],cur,1)
elif key[:5]=='makeS':
name = re.match('.*\{(.*)\}.*',key).group(1)
if not parent:
self.root = setNodes.makeSet(parent)
self.root.name = name
cur = self.root
else:
parent.down[i] = setNodes.makeSet(parent)
parent.down[i].name = name
cur = parent.down[i]
self.load(prog[key][0],cur,0)
elif key[:5]=='mutat':
rate = float(re.match('.*\((.*)\).*',key).group(1))
if not parent:
self.root = alterNodes.mutate(parent)
self.root.rate = rate
cur = self.root
else:
parent.down[i] = alterNodes.mutate(parent)
parent.down[i].rate = rate
cur = parent.down[i]
self.load(prog[key][0],cur,0)
elif key[:5]=='uniRe':
num = int(re.match('.*count\=([0-9]*).*',key).group(1))
if not parent:
self.root = alterNodes.uniRecomb(parent)
self.root.num = num
cur = self.root
else:
parent.down[i] = alterNodes.uniRecomb(parent)
parent.down[i].num = num
cur = parent.down[i]
self.load(prog[key][0],cur,0)
elif key[:5]=='diago':
n = int(re.match('.*n\=([0-9]*).*',key).group(1))
if not parent:
self.root = alterNodes.diagRecomb(parent)
self.root.num = n
cur = self.root
else:
parent.down[i] = alterNodes.diagRecomb(parent)
parent.down[i].n = n
cur = parent.down[i]
self.load(prog[key][0],cur,0)
elif key[:5]=='tweak':
num = float(re.match('.*\((.*)\).*',key).group(1))
if not parent:
self.root = alterNodes.tweak(parent)
self.root.rate = rate
cur = self.root
else:
parent.down[i] = alterNodes.tweak(parent)
parent.down[i].rate = rate
cur = parent.down[i]
self.load(prog[key][0],cur,0)
elif key[:5]=='kTour':
num = int(re.match('.*count=([0-9]*).*',key).group(1))
k = int(re.match('.*k=([0-9]*).*',key).group(1))
if not parent:
self.root = selectNodes.kTourn(parent)
self.root.num = num
self.root.k = k
cur = self.root
else:
parent.down[i] = selectNodes.kTourn(parent)
parent.down[i].num = num
parent.down[i].k = k
cur = parent.down[i]
self.load(prog[key][0],cur,0)
elif key[:5]=='trunc':
num = int(re.match('.*count=([0-9]*).*',key).group(1))
if not parent:
self.root = selectNodes.trunc(parent)
self.root.num = num
cur = self.root
else:
parent.down[i] = selectNodes.trunc(parent)
parent.down[i].num = num
cur = parent.down[i]
self.load(prog[key][0],cur,0)
elif key[:5]=='[Last':
if not parent:
self.root = termNodes.lastSet(parent)
else:
parent.down[i] = termNodes.lastSet(parent)
else:
name = re.match('\[(.*)\]',key).group(1)
if not parent:
self.root = termNodes.persSet(parent)
self.root.name = name
else:
parent.down[i] = termNodes.persSet(parent)
parent.down[i].name = name
if not parent:
self.update()
self.count()
[docs] def update(self):
"""
This function updates all of the nodes with the correct pointers to the settings and the persistant and 'last' sets.
"""
self.root.update(0,self.sets,self.settings)
[docs] def count(self):
"""
This function counts the number of nodes in the bbsa
"""
self.size = self.root.count()
[docs] def duplicate(self):
"""
This function creates a copy of itself and updates the newly created object.
"""
x = copy.deepcopy(self)
x.aveBest = 0.0
x.aveEval = 0.0
x.aveOps = 0.0
x.logs = {}
x.sets['last'] = []
x.sets['empty'] = []
x.sets['pers'] = {key:[] for key in self.sets['pers']}
x.runs = []
x.settings.curEvals = 0
x.settings.curOp = 0
x.fitness = 0
x.update()
return x
[docs] def randomNode(self):
"""
This function returns a random node in the parse tree.
"""
z = []
popNodes(self.root,z)
n = random.choice(z)
return n
[docs] def altMutate(self):
"""
This is a mutation that selects a random node and randomizes the parameters of that node.
Note: not all nodes have parameters that can be altered.
"""
x = self.duplicate()
n = x.randomNode()
n.randomize(self.sets,self.settings)
return x
[docs] def mate(self,other):
x = self.duplicate()
y = other.duplicate()
xn = x.randomNode()
yn = y.randomNode()
xp = xn.parent
yp = yn.parent
if yp is not None:
if yn==yp.down[0]:
yp.down[0] = xn
else:
yp.down[1] = xn
else:
y.root = xn
if xp is not None:
if xn==xp.down[0]:
xp.down[0] = yn
else:
xp.down[1] = yn
else:
x.root = yn
xn.parent = yp
yn.parent = xp
x.update()
y.update()
x.count()
y.count()
return x,y
[docs] def mutate(self):
x = self.duplicate()
n = x.randomNode()
self.createRandom(n)
x.update()
x.count()
return x
def __str__(self):
string = ""
string += self.root.toString()
return string
[docs] def toDict(self):
return self.root.toDict()
[docs] def createRandom(self,start = None):
d = 0
size = random.randint(1,2**(self.maxDepth))
if start==None:
start = self.root
else:
size= random.randint(1,self.maxDepth)
for i in xrange(size):
node = random.choice(allNodes)
if not start:
start = node(None)
start.randomize(self.sets,self.settings)
continue
last = None
cur = start
while cur:
last = cur
if not cur.down:
break
cur = random.choice(cur.down)
if cur==last:
continue
cur = last
n = 0
if len(cur.down)>1:
if cur.down[0]==cur.down[1]:
n = random.choice([0,1])
elif not cur.down[0]:
n = 0
else:
n = 1
if n==None:
continue
#eventually need checks here to make sure valid children
#and values get set right in the children
t = node(cur)
if 2 not in cur.take:
if 1 in t.give:
t.count = 1
t.randomize(self.sets,self.settings)
t.count = 1
cur.down[n] = t
else:
continue
else:
cur.down[n] = t
cur.down[n].randomize(self.sets,self.settings)
start.fillTerms(self.sets,self.settings)
self.depth = start.update(0,self.sets,self.settings)
if self.root == None:
self.root = start
self.root.settings = self.settings
self.count()
return
[docs] def evaluate(self):
self.logs = {key:[] for key in self.sets['pers'].keys()}
self.logs['last'] = []
self.sets['last'] = [solution.solution(self.settings)for i in xrange(self.initPop)]
for d in self.sets['last']:
d.evaluate()
self.settings.curOp = 0
self.settings.curEvals = 0
for i in xrange(self.maxIterations):
gMax = -1.0
temp = self.root.evaluate(self.sets)
if temp:
self.sets['last'] = temp
for key in self.logs:
if key is 'last':
continue
s = 0.0
m = 0.0
for x in self.sets['pers'][key]:
s+=x.fitness
if m<x.fitness:
m = x.fitness
if len(self.sets['pers'][key])>0:
s/=len(self.sets['pers'][key])
if self.sets['pers'][key]:
self.logs[key].append((i,self.settings.curEvals,m,s))
if m>gMax:
gMax = m
s = 0.0
m = 0.0
for x in self.sets['last']:
s+=x.fitness
if m<x.fitness:
m = x.fitness
if len(self.sets['last'])>0:
s/=len(self.sets['last'])
if self.sets['last']:
if m>gMax:
gMax = m
self.logs['last'].append((i,int(self.settings.curEvals),m,s,self.settings.curOp))
if i>self.converge and gMax==0:
break
if self.settings.curEvals>=self.settings.maxEvals:
break
if self.settings.curOp>=self.settings.maxOp:
break
gMax = -1
for key in self.logs:
if key is 'last':
continue
s = 0.0
m = 0.0
for x in self.sets['pers'][key]:
s+=x.fitness
if m<x.fitness:
m = x.fitness
if len(self.sets['pers'][key])>0:
s/=len(self.sets['pers'][key])
self.logs[key].append((i,self.settings.curEvals,m,s))
if m>gMax:
gMax = m
s = 0.0
m = 0.0
it = 0
k = 0
for x in self.sets['last']:
x.evaluate()
s+=x.fitness
if m<x.fitness:
m = x.fitness
it = k
k+=1
if len(self.sets['last'])>0:
s/=len(self.sets['last'])
if m>gMax:
gMax = m
self.logs['last'].append((i,int(self.settings.curEvals),m,s,self.settings.curOp))
self.settings.curEvals = 0
return self.settings.curOp
[docs] def run(self):
for i in xrange(self.numRuns):
self.aveOps += self.evaluate()
self.runs.append({'logs':self.logs,'analyze':self.analyze(self.logs)})
for key in self.sets['pers']:
self.sets['pers'][key] = []
self.sets['last'] = []
#generalize how good the runs were
#give it a fitness here
self.aveOps /=self.numRuns
self.aveBest = 0.0
self.aveEval = 0.0
for run in self.runs:
b = None
k = None
for key in run['analyze']['finalBest']:
if not b or run['analyze']['finalBest'][key]>b:
b = run['analyze']['finalBest'][key]
k = key
self.aveBest+=b
self.aveEval+=run['analyze']['converge'][k]
self.aveBest/=len(self.runs)
self.aveEval/=len(self.runs)
self.runs = []
self.fitness = self.aveBest
[docs] def analyze(self,logs):
#extract important information out of a run here
allBest = None
finalBest = {}
finalAverage = {}
evalConv = {}
for key in logs:
counter = 0
rb = None
for gen in logs[key]:
if not rb or gen[2]!=rb[2]:
rb = gen
counter+=1
if counter>=self.converge:
evalConv[key] = gen[1]
break
if not allBest or gen[2]>allBest[2]:
allBest = gen
finalBest[key] = logs[key][-1][2]
finalAverage[key] = logs[key][-1][3]
if key not in evalConv:
evalConv[key] = logs[key][-1][1]
ret = {}
ret['allBest'] = allBest
ret['finalBest'] = finalBest
ret['finalAverage'] = finalAverage
ret['converge'] = evalConv
return ret
def printLogs(self):
print self.logs.keys()
opt = raw_input("Which logs?")
for x in self.logs[opt]:
print x[0],x[1],x[2],x[3]
def __gt__(self,other):
mf = self.aveBest-self.size*self.settings.parsimony
yf = other.aveBest-other.size*self.settings.parsimony
if mf>yf:
return True
elif mf<yf:
return False
else:
return self.aveEval<other.aveEval
[docs] def dominate(self,other):
if self.aveBest> other.aveBest and self.aveEval<=other.aveEval:
return True
if self.aveBest>=other.aveBest and self.aveEval<=other.aveEval:
return True
return False