Created
April 28, 2012 10:48
-
-
Save kristacc/2517911 to your computer and use it in GitHub Desktop.
Genetic algorithms example
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #!/usr/bin/env python | |
| # this is a genetic algorithms tutorial by krista <3 | |
| # <[email protected]> | |
| # Richard Dawkins is the inventor of this example ("METHINKS IT IS LIKE A WEASEL.") | |
| # example is done with Python (works with versions 2.6 and 2.7) | |
| # and to be more specific, we'll use elitistic evolution | |
| # (== only fittest 10% will survive to the next population and rest will die. | |
| # 50% of the best creatures will mate and make pretty babies to the next population <3 ) | |
| # 26.11.2011 | |
| # PS. even this is a really simple example, this works just as fine to more complex problems. | |
| # But the problem must have well defined fittness function (== what means that the solutions is good?) | |
| # All you need to do, is figure out what kind of genes your problem has ;) | |
| # PPS. this may not find the ultimately best solution but at least the best solution in certain area. | |
| # And remember, the program is just as good as you make it... | |
| # PPPS. evolution, it works bitches! | |
| import random | |
| # let's create different options / genes == letters | |
| GENES = 'abcdefghijlkmopqrstyvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ 1234567890,.-;:_!"#%&/()=?@${[]}' | |
| # what we want from the animal == sentence we want to create | |
| TARGET = 'METHINKS IT IS LIKE A WEASEL.' | |
| # creates a random gene == takes a random letter | |
| def mutated_gene(): | |
| global GENES | |
| return random.choice( GENES ) | |
| # creates random genome == creates "sentence" from random letters (may not have any real words / meaning ) | |
| def generate_genome(): | |
| global TARGET | |
| # length of sentence == how many letters we want | |
| N = len( TARGET ) | |
| return [ mutated_gene() for x in range( N ) ] | |
| # what kind of features an animal has: | |
| class Animal(object): | |
| # "gives birth" to an animal with wanted genes and it's initial fitness value | |
| def __init__( self, genes = [] ): | |
| self.genes = genes | |
| self.Q = 1e99 | |
| # mates two animals.... == mixes their genes to create babies | |
| def mate( self, other ): | |
| new_genes = [] | |
| # evolution! mutation! heritance :) | |
| for (gA, gB) in zip( self.genes, other.genes ): | |
| p = random.random() | |
| # if random number (between 0-1) is less than 0,45 | |
| # then we choose _A_ gene from animal A | |
| if p < 0.45: | |
| new_genes.append( gA ) | |
| # if number between 0,45 - 0,899999.... then we take a gene from animal B | |
| elif p < 0.90: | |
| new_genes.append( gB ) | |
| # otherwise we just take random gene (=10% chance) | |
| else: | |
| new_genes.append( mutated_gene() ) | |
| # we have created a new animal | |
| return Animal( new_genes ) | |
| # compute fittness of an animal (= can it survive how well?) | |
| def compute_q( self ): | |
| global TARGET | |
| out = 0.0 | |
| # compares each gene == letter with target sentence and sums all errors | |
| # == if it is really close what we want, | |
| # it is really fit and good with surviving | |
| for (gA, T) in zip( self.genes, TARGET ): | |
| if gA != T: | |
| out += 1 | |
| self.Q = out | |
| # let's create a population... | |
| population = [] | |
| # ... of 100 animals <3 | |
| for i in range( 100 ): | |
| population.append( Animal( generate_genome() ) ) | |
| done = False | |
| generation = 1 | |
| # as long as the sentence is not found (== our animals don't look like the target sentence | |
| # == animals have different genes than we hope) | |
| while not done: | |
| for p in population: | |
| p.compute_q() | |
| # sorts animals by their fittness | |
| population = sorted( population, key = lambda x: x.Q ) | |
| # if best animal in population is the target sentence than we are done | |
| if population[0].Q < 1: | |
| done = True | |
| # printing.... | |
| print generation, ''.join( population[0].genes ) | |
| # time to create next generation of animals (and use evolution :) ) | |
| new_population = [] | |
| # the most fittest ones will survive to the next generation (10% of animals) others "die" | |
| new_population.extend( population[:10] ) | |
| # rest of the population will be made of the babies of the better half of the old populations | |
| for i in range( 90 ): | |
| # lets select two animals to be mated (from better half of population) | |
| Animal_1 = random.choice( population[:50] ) | |
| Animal_2 = random.choice( population[:50] ) | |
| # then we create a baby of the selected two | |
| baby_animal = Animal_1.mate( Animal_2 ) | |
| # and put the baby into the next population | |
| new_population.append( baby_animal ) | |
| population = new_population | |
| generation += 1 | |
| print "After %i generations: "%generation, ''.join( population[0].genes ) | |
So I am trying your good, and I am trying to get my head around it. Suppose we have your target: 'METHINKS IT IS LIKE A WEASEL.' running this code would return the solution after relatively low number of generations but if you change the target to lower case, namely 'methinks it is like a weasel.' the code takes time forever, why is this so? I have tried it with different examples and it seems lower case or upper case can change the timing a lot!!
because in the GENES string there is not any 'n' letter!
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
So I am trying your good, and I am trying to get my head around it. Suppose we have your target: 'METHINKS IT IS LIKE A WEASEL.' running this code would return the solution after relatively low number of generations but if you change the target to lower case, namely 'methinks it is like a weasel.' the code takes time forever, why is this so? I have tried it with different examples and it seems lower case or upper case can change the timing a lot!!