very simple Genetic Algorithm completed

Matthew_WARREN at bnpparibas.com Matthew_WARREN at bnpparibas.com
Thu Jan 31 17:43:38 CET 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