very simple Genetic Algorithm completed
Matthew_WARREN at bnpparibas.com
Matthew_WARREN at bnpparibas.com
Thu Jan 31 11:43:38 EST 2008
Hi,
I got some help with this from here, and there's been a little bit of
discussion around GA's recently, so thought I'd post up my likey slow and
clunky version of a GA that in essence just 'evolves' a solution to 'make a
sum that evaluates to n using */+-0123456789' it's a really simple GA that
would be useful for someone who doesn't quite get GA's to look at.
I think it's simple enough to be fairly self explanatory.
to see it come up with evolved solutions to n=1000
>>>from quickga import *
>>>evolve()
I like playing with stuff like this. I'm going to use this little toy to
investigate how mutation rates/crossover gene length, pop size etc.. etc..
interact with each other. All completely unscientifically and for my own
bemusement.
One point, it's a good idea to keep mutationrate around 1000 - 10000 with
genome and population sizes of say 50 - 100. Too low and you get no
solution as the mutations mix up the genome too much for selection
pressure to work.
...as this actually does need to go as quick as it can, and if anyone feels
like it, I'd really appreciate picking it over on the list for
optimization. I'm not too familiar with Pthon internals, nor programming
for speed in general.
<pre>
from random import randint
from operator import itemgetter
genes=['+','-','*','/','0','1','2','3','4','5','6','7','8','9']
signs=['+','-','*','/']
digits=['1','2','3','4','5','6','7','8','9']
table = {"++": "+", "+-": "-", "+*": "+", "+/": "+",
"-+": "-", "--": "+", "-*": "-", "-/": "-",
"*+": "*", "**": "*", "*/": "*",
"/+": "/", "/*": "/", "//": "/",
"+0":"+","*0":"*","-0":"-","/0":"/"} # keep out octal literals
def rationalise_signs(s):
"""Takes the genome string and twiddles it so eval() will work as
expected
"""
prev = ''
while s != prev:
prev=s
for z in ['+','-','*','/']:
s=s.replace(z+'0',z)
for key, value in table.items():
s = s.replace(key, value)
s=s.lstrip('0')
s=s.strip('+-*/')
return s
def generate(number,length):
"""Generate the initial population of genome strings
"""
population=[]
for i in range(number):
s=rationalise_signs(''.join([
genes[randint(0,len(genes))-1] for n in range(length) ]))
population.append(s)
return population
def floatify(intstring):#So eval() be floating point.
"""kludge to ensure eval() does floating point math
"""
prev=''
while intstring != prev:
prev=intstring
for sign in signs:
for digit in digits:
intstring=intstring.replace(digit+sign,digit+'.0'+sign)
return intstring
def express(population):
"""Get the 'expression' of the genome.
"""
expressed_population=[]
for individual in population:
s=floatify(individual)
expressed_population.append((individual,eval(s)))
return expressed_population
def fitness(expressed_population,fitvalue,tolerance):
"""Test the expressed genome for fitness
"""
population_fitness=[]
sumfitness=0
for expressed_individual in expressed_population:
individual,expression=expressed_individual
fitness=abs(fitvalue-expression)
sumfitness=sumfitness+fitness
population_fitness.append((individual,expression,fitness))
avgfitness=sumfitness/len(expressed_population)
return (population_fitness,avgfitness)
def get_fittest(population_fitness,pct,full=False):
"""Quick n dirty way of selecting - top n% fittest individuals
"""
population_fitness.sort(key=itemgetter(2))#sort on fitness
npct=(len(population_fitness)/100.0)*pct
if not full:
return [ n[0] for n in population_fitness[0:int(npct)] ]
else:
return population_fitness[0:int(npct)]
def mutate(individual,rate):
"""Does what it says on the tin. Mutates per gene
if rate is 10000 mutatuion rate is 1 in 10000 on avg
"""
newindividual=''
for gene in individual:
if randint(0,rate)==1:
newgene=genes[randint(0,14)-1]
newindividual=newindividual+newgene
else:
newindividual=newindividual+gene
return newindividual
def breed_new(individuals,number,mutationrate):#crossover with mutation
"""simple crossover of the two genomes around a point, then mutate
"""
newpopulation=[]
num_individuals=len(individuals)
while len(newpopulation)<=number:
lady=individuals[randint(0,num_individuals-1)]
man=individuals[randint(0,num_individuals-1)]
xpoint=randint(0,100)
xlady=(len(lady)/100.0)*xpoint
xman=(len(man)/100.0)*xpoint
leftxlady=lady[:int(xlady)]
rightxlady=lady[int(xlady):]
leftxman=man[:int(xman)]
rightxman=man[int(xman):]
new1=rationalise_signs(mutate(leftxlady+rightxman,mutationrate))
new2=rationalise_signs(mutate(leftxman+rightxlady,mutationrate))
newpopulation.append(new1)
newpopulation.append(new2)
return newpopulation
def
evolve(popsize=50,genomelength=100,mutationrate=10000,fitcullpct=10,numsolutions=5,target=1000,tolerance=1):
"""Controls the whole process.
"""
pop=generate(popsize,genomelength)
fitgens=[]
generation=1
while len(fitgens)<numsolutions:
epop=express(pop)
fpop,avg=fitness(epop,target,tolerance)
print "Average fitness",avg
if avg>tolerance:
pop=breed_new(get_fittest(fpop,fitcullpct),popsize,mutationrate)
generation=generation+1
else:
print "Pop avg fitness within tolerance"
print "********************************"
fitgens.append((fpop[0:],generation))
pop=generate(popsize,genomelength)
generation=1
outlist=[]
for fitpop,generation in fitgens:
bestfitpop=get_fittest(fitpop,20,full=True)
for fitgeneinfo in bestfitpop:
genome,number,avgfit=fitgeneinfo
prev=''
s=floatify(genome)
outlist.append(genome+" in "+str(generation)+"
generations got "+str(number)+" avg fit ="+str(avgfit))
for line in set(outlist):
print line
</pre>
Matt. (Apologies for any disclaimers)
This message and any attachments (the "message") is
intended solely for the addressees and is confidential.
If you receive this message in error, please delete it and
immediately notify the sender. Any use not in accord with
its purpose, any dissemination or disclosure, either whole
or partial, is prohibited except formal approval. The internet
can not guarantee the integrity of this message.
BNP PARIBAS (and its subsidiaries) shall (will) not
therefore be liable for the message if modified.
Do not print this message unless it is necessary,
consider the environment.
---------------------------------------------
Ce message et toutes les pieces jointes (ci-apres le
"message") sont etablis a l'intention exclusive de ses
destinataires et sont confidentiels. Si vous recevez ce
message par erreur, merci de le detruire et d'en avertir
immediatement l'expediteur. Toute utilisation de ce
message non conforme a sa destination, toute diffusion
ou toute publication, totale ou partielle, est interdite, sauf
autorisation expresse. L'internet ne permettant pas
d'assurer l'integrite de ce message, BNP PARIBAS (et ses
filiales) decline(nt) toute responsabilite au titre de ce
message, dans l'hypothese ou il aurait ete modifie.
N'imprimez ce message que si necessaire,
pensez a l'environnement.
More information about the Python-list
mailing list