Welcome, guest | Sign In | My Account | Store | Cart

This is a solution to the first problem in this tutorial: http://www.ai-junkie.com/ga/intro/gat1.html

I wrote it in about an hour, and tried to keep everything as clear and simple as possible. Please excuse the sparse commenting.

I deviated from the examples in the tutorial in several ways, the most important of which is the way the results are evaluated. In the tutorial it is stated that the equations are solved from left to right, but for expedience I let Python's operator precedence determine the order of evaluation. I'm not sure how close this example is to the example solution provided in the tutorial. I was to lazy to download unzip and decode the C source...

Python, 168 lines
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168``` ```from string import digits from random import randrange, randint try: import psyco psyco.full(memory=100) psyco.profile(0.05, memory=100) psyco.profile(0.2) except: pass operators = "+-*/" genes = { 0:'0', 1:'1', 2:'2', 3:'3', 4:'4', 5:'5', 6:'6', 7:'7', 8:'8', 9:'9', 10:'+', 11:'-', 12:'*', 13:'/' } traits = {} for key, value in enumerate(genes): traits[value] = key def encode(expression): """Takes a mathmatic expression as a string and returns a chromosome.""" output = [] for char in expression: if char in traits.keys(): output.append(traits[char]) return output def decode(chromosome): """Takes a chromosome (list) and returns an expression.""" # this needs to be a mini state machine. # We expect a stream of number + operator pairs terminated with a number output = "" need_op = False for key in chromosome: gene = genes[key] if need_op: if gene in operators: output += gene need_op = False else: continue else: if gene in digits: output += gene need_op = True else: continue if not need_op: # we don't want an op hanging off the end output = output[:len(output)-1] return output def makeChrom(length): """Create a random chromosome length long.""" output = [] for i in range(length): output.append(randrange(14)) return output def sortFitness(chromosomes, target): """Sort the chromosomes so the fitest comes first.""" done = False fittest = [] for chrom in chromosomes: # Decode pheno = decode(chrom) # Try to evaluate try: result = eval(pheno) except ZeroDivisionError: result = 0 # Score based on result fit = abs(target-result) if fit == 0: done = True fit = -1 print "%s =%s : %s" %(pheno.rjust(15), str(result).rjust(10), str(fit).rjust(15)) fittest.append((fit, chrom)) # Once we have a list of (fitness, chrom) pairs we can sort fittest.sort() return done, [item[-1] for item in fittest] def breed(pop, number, mutation): """Breeds a population until there are 'number' of them.""" output = pop[:] # carry over all the breeders while len(output) < number: # Create a new chromosome by crossing two random members child1, child2 = crossover(pop[randint(0, len(pop)-1)], pop[randint(0, len(pop)-1)],) child1 = mutate(child1, mutation) child2 = mutate(child2, mutation) output.extend([child1, child2]) if len(output) > number: output[:number] return output def crossover(chrom1, chrom2): """Cross two chromosomes.""" breakpoint = randint(0, len(chrom1)) return (chrom1[breakpoint:] + chrom2[:breakpoint], chrom2[breakpoint:] + chrom1[:breakpoint]) def mutate(chrom, rate=100): """Randomly mutate a chromosome. Rate is the chance in 100 that mutation will occure.""" for i in range(len(chrom)): chance = randint(0, 100) if chance <= rate: chrom[i] = randint(0, 13) return chrom def findFit(target=42, length=20, pop=20, mutation=1): """Evolve a population of math problems to solve for target.""" population = [makeChrom(length) for i in range(pop)] generations = 0 while True: print "Generation: %s" %generations print "%s%s%s" %("Chromosome".rjust(15), "Result".rjust(15), "Fitness".rjust(15)) done, population = sortFitness(population, target) if not done: # take the first several fittest members fittest = population[:pop/4] # and breed them until you have a new population population = breed(fittest, pop, mutation) else: print "Solution found!" print "%s = %s" %(decode(population[0]), eval(decode(population[0]))), print "is the fitest solution for %s!" %target return generations, decode(population[0]) generations += 1 do_average = False if __name__ == "__main__": number = input("Enter a target number for the calculation: ") if do_average: results = [] for i in range(50): generations, winner = findFit(target=number, pop=30, mutation=20) results.append((generations, winner)) #results.sort() average = 0 for item in results: average += item[0] print item[0], item[1] print "Average generations: %s" %average/50 else: generations, winner = findFit(target=number, pop=30, mutation=20) print "Generations: %s, Winner: %s" %(generations, winner) raw_input("Press enter to continue...") ```

I suppose the neatest thing about this implementation is the use of a dict instead of a binary string to encode the genes. I find binary access painful to accomplish in Python, and even more painful considering the availability of more meaningful data structures ;)

I would call this a fairly lean implementation - I let Python do most of the heavy lifting. Still I think it is a good example of the basics involved with implementing a genetic algorithm solution.

Shortly after finishing this I wrote an object oriented GA system that I think is pretty clever. It used classes for genes and chromosomes, and made gene to data mapping effectively transparent. Unfortunately it ties into a bunch of un-released code that I had written previously. If anyone is interested I can try to pair it down to a stand-alone example to post.

#### 1 comment

David Adler 11 years, 11 months ago

This is a good program but does not use roulette selection or binary chromosomes. The following source code does http://code.activestate.com/recipes/578128-genetic-algorithm-in-python-source-code-httpwwwai-/

 Created by Ed Blake on Thu, 9 Nov 2006 (PSF)