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 9 years, 6 months ago  # | flag

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-/