DNA strand

genalgy

Genetic algorithm example code in Python


A bit of background

genalgy provides a utility class, genetic.py, and an example program, dna.py which together illustrate concepts of genetic algorithms. I originally wrote the programs as an accompaniment to the tutorial on genetic algorithms on the AI Junkie site.

Downloading the program



How it works

If you're unfamiliar with genetic algorithm concepts, the tutorial referenced above is a worthwhile read before continuing. Since the code is based entirely upon the content of the tutorial, it may be worth skimming through even if you are Marvin Minsky :)

That being said, here's a lightning quick summary of how the program works:

Trying out the example program

dna.py, the example application, takes a single argument, the desired target value (see previous section), e.g. -

$ python dna.py 12



An example session

Here's some example output from a typical session, using 4 as a target value:

Initializing genetic algorithm class...
Operator list: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, '+', '-', '*', '/']
Initial chromosome is: ['1', '1', '1', '0', '0', '0', '0', '1', '0', '0', '1', '1', '1', '0', '0', '0', '1', '1', '1', '1', '0', 
'0', '1', '1', '0', '0', '0', '0', '1', '0', '0', '1', '1', '0', '1', '1', '1', '1', '0', '0', '0', '1', '1', '1', '0', '1', '0', 
'0', '0', '0', '0', '1', '1', '1', '0', '0', '1', '1', '1', '0', '0', '1', '0', '0', '1', '0', '0', '0', '0', '0', '1', '1', '0', 
'0', '1', '0', '1', '0', '0', '0', '1']
Building gene map from operator list...
{'01101': {'type': 'operator', 'op': '/'}, '01100': {'type': 'operator', 'op': '*'}, '01011': {'type': 'operator', 'op': '-'}, 
'01010': {'type': 'operator', 'op': '+'}, '01000': {'type': 'int', 'op': '8'}, '01001': {'type': 'int', 'op': '9'}, '00111': 
{'type': 'int', 'op': '7'}, '00110': {'type': 'int', 'op': '6'}, '00001': {'type': 'int', 'op': '1'}, '00000': {'type': 'int', 
'op': '0'}, '00010': {'type': 'int', 'op': '2'}, '00011': {'type': 'int', 'op': '3'}, '00100': {'type': 'int', 'op': '4'}, 
'00101': {'type': 'int', 'op': '5'}}
Running genetic algorithm...
Generation 0
chrom_string: 11100
chrom_string: 00100
chrom_string: 11100
chrom_string: 01111
chrom_string: 00110
chrom_string: 00010
chrom_string: 01101
chrom_string: 11100
chrom_string: 01110
chrom_string: 10000
chrom_string: 01110
chrom_string: 01110
chrom_string: 01001
chrom_string: 00000
chrom_string: 11001
chrom_string: 01000
eval string is: 4/9
chromosome translation: 4/9
result: 0.0
fitness value: 0.25
---
Generation 1
[mutation on 26]
[crossover on 49]
chrom_string: 00111
chrom_string: 00111
chrom_string: 00100
chrom_string: 10000
chrom_string: 01100
chrom_string: 10100
chrom_string: 01111
chrom_string: 00001
chrom_string: 00111
chrom_string: 00011
chrom_string: 11001
chrom_string: 10010
chrom_string: 10011
chrom_string: 01111
chrom_string: 00011
chrom_string: 10100
eval string is: 7*1
chromosome translation: 7*1
result: 7.0
fitness value: -0.333333333333
---
Generation 2
[mutation on 15]
[mutation on 47]
chrom_string: 00111
chrom_string: 00111
chrom_string: 00100
chrom_string: 00000
chrom_string: 01100
chrom_string: 10100
chrom_string: 01111
chrom_string: 00001
chrom_string: 00111
chrom_string: 00111
chrom_string: 11001
chrom_string: 10010
chrom_string: 10011
chrom_string: 01111
chrom_string: 00011
chrom_string: 10100
eval string is: 7*1
chromosome translation: 7*1
result: 7.0
fitness value: -0.333333333333
---
Generation 3
[mutation on 76]
[crossover on 14]
chrom_string: 00000
chrom_string: 00110
chrom_string: 01010
chrom_string: 00111
chrom_string: 10000
chrom_string: 10011
chrom_string: 10011
chrom_string: 11100
chrom_string: 11001
chrom_string: 01001
chrom_string: 10111
chrom_string: 10001
chrom_string: 11110
chrom_string: 00001
chrom_string: 11001
chrom_string: 11001
eval string is: 6+7
chromosome translation: 6+7
result: 13.0
fitness value: -0.111111111111
---
Generation 4
[mutation on 33]
chrom_string: 00000
chrom_string: 00110
chrom_string: 01010
chrom_string: 00111
chrom_string: 10000
chrom_string: 10011
chrom_string: 10001
chrom_string: 11100
chrom_string: 11001
chrom_string: 01001
chrom_string: 10111
chrom_string: 10001
chrom_string: 11110
chrom_string: 00001
chrom_string: 11001
chrom_string: 11001
eval string is: 6+7
chromosome translation: 6+7
result: 13.0
fitness value: -0.111111111111
---
Generation 5
[mutation on 34]
[crossover on 54]
chrom_string: 11000
chrom_string: 11111
chrom_string: 00000
chrom_string: 11100
chrom_string: 11100
chrom_string: 10000
chrom_string: 00001
chrom_string: 10010
chrom_string: 10001
chrom_string: 11100
chrom_string: 00100
chrom_string: 11100
chrom_string: 00111
chrom_string: 00110
chrom_string: 01010
chrom_string: 01101
eval string is: 0
chromosome translation: 0
result: 0.0
fitness value: 0.25
---
Generation 6
[crossover on 60]
chrom_string: 00111
chrom_string: 00110
chrom_string: 01010
chrom_string: 01101
chrom_string: 11100
chrom_string: 01111
chrom_string: 10000
chrom_string: 01110
chrom_string: 01110
chrom_string: 01000
chrom_string: 00000
chrom_string: 11001
chrom_string: 01000
chrom_string: 11110
chrom_string: 00010
chrom_string: 01110
eval string is: 6+8
chromosome translation: 6+8
result: 14.0
fitness value: -0.1
---
Generation 7
[crossover on 65]
chrom_string: 11110
chrom_string: 00010
chrom_string: 01110
chrom_string: 00011
chrom_string: 10011
chrom_string: 00101
chrom_string: 00110
chrom_string: 11110
chrom_string: 00111
chrom_string: 11000
chrom_string: 00111
chrom_string: 00111
chrom_string: 00100
chrom_string: 00000
chrom_string: 01100
chrom_string: 10100
eval string is: 2
chromosome translation: 2
result: 2.0
fitness value: 0.5
---
Generation 8
[crossover on 27]
chrom_string: 10100
chrom_string: 11011
chrom_string: 11000
chrom_string: 11111
chrom_string: 00000
chrom_string: 11100
chrom_string: 11100
chrom_string: 10000
chrom_string: 00001
chrom_string: 10010
chrom_string: 10001
chrom_string: 11100
chrom_string: 00100
chrom_string: 11100
chrom_string: 00111
chrom_string: 00110
eval string is: 0
chromosome translation: 0
result: 0.0
fitness value: 0.25
---
Generation 9
[crossover on 40]
chrom_string: 00001
chrom_string: 10010
chrom_string: 10001
chrom_string: 11100
chrom_string: 00100
chrom_string: 11100
chrom_string: 00111
chrom_string: 00110
chrom_string: 01010
chrom_string: 01101
chrom_string: 11100
chrom_string: 01111
chrom_string: 10000
chrom_string: 01110
chrom_string: 01110
chrom_string: 01000
eval string is: 4+8
chromosome translation: 4+8
result: 12.0
fitness value: -0.125
---
Generation 10
[mutation on 68]
chrom_string: 00001
chrom_string: 10010
chrom_string: 10001
chrom_string: 11100
chrom_string: 00100
chrom_string: 11100
chrom_string: 00111
chrom_string: 00110
chrom_string: 01010
chrom_string: 01101
chrom_string: 11100
chrom_string: 01111
chrom_string: 10000
chrom_string: 01100
chrom_string: 01110
chrom_string: 01000
eval string is: 4+8
chromosome translation: 4+8
result: 12.0
fitness value: -0.125
---
Generation 11
[mutation on 44]
[crossover on 63]
chrom_string: 00011
chrom_string: 00011
chrom_string: 10010
chrom_string: 00000
chrom_string: 00110
chrom_string: 01010
chrom_string: 00111
chrom_string: 10000
chrom_string: 10011
chrom_string: 10000
chrom_string: 11100
chrom_string: 11001
chrom_string: 01101
chrom_string: 10111
chrom_string: 10001
chrom_string: 11110
eval string is: 3+7
chromosome translation: 3+7
result: 10.0
fitness value: -0.166666666667
---
Generation 12
[crossover on 10]
chrom_string: 10010
chrom_string: 00000
chrom_string: 00110
chrom_string: 01010
chrom_string: 00111
chrom_string: 10000
chrom_string: 10011
chrom_string: 10000
chrom_string: 11100
chrom_string: 11001
chrom_string: 01101
chrom_string: 10111
chrom_string: 10001
chrom_string: 11110
chrom_string: 00001
chrom_string: 10001
eval string is: 0+7/1
chromosome translation: 0+7/1
result: 7.0
fitness value: -0.333333333333
---
Generation 13
[mutation on 8]
[mutation on 10]
[mutation on 15]
[crossover on 78]
chrom_string: 01110
chrom_string: 01000
chrom_string: 01010
chrom_string: 11011
chrom_string: 01000
chrom_string: 11110
chrom_string: 00010
chrom_string: 01110
chrom_string: 00011
chrom_string: 10011
chrom_string: 00101
chrom_string: 10110
chrom_string: 11110
chrom_string: 00111
chrom_string: 11000
chrom_string: 00110
eval string is: 8+8
chromosome translation: 8+8
result: 16.0
fitness value: -0.0833333333333
---
Generation 14
[mutation on 32]
[mutation on 75]
[crossover on 4]
chrom_string: 00100
chrom_string: 00101
chrom_string: 01101
chrom_string: 10100
chrom_string: 01111
chrom_string: 00011
chrom_string: 00111
chrom_string: 00001
chrom_string: 11001
chrom_string: 10010
chrom_string: 11011
chrom_string: 01111
chrom_string: 00011
chrom_string: 11100
chrom_string: 01011
chrom_string: 00011
eval string is: 5/3-3
chromosome translation: 5/3-3
result: -2.0
fitness value: 0.166666666667
---
Generation 15
[crossover on 67]
chrom_string: 10001
chrom_string: 01100
chrom_string: 01110
chrom_string: 01000
chrom_string: 01010
chrom_string: 11011
chrom_string: 01000
chrom_string: 11110
chrom_string: 00110
chrom_string: 01110
chrom_string: 00011
chrom_string: 10011
chrom_string: 00101
chrom_string: 10110
chrom_string: 11110
chrom_string: 00111
eval string is: 8+8
chromosome translation: 8+8
result: 16.0
fitness value: -0.0833333333333
---
Generation 16
[crossover on 31]
chrom_string: 10001
chrom_string: 11100
chrom_string: 01100
chrom_string: 11100
chrom_string: 00111
chrom_string: 00110
chrom_string: 01011
chrom_string: 01101
chrom_string: 11100
chrom_string: 01111
chrom_string: 10001
chrom_string: 01100
chrom_string: 01110
chrom_string: 01000
chrom_string: 01010
chrom_string: 11011
eval string is: 7-8
chromosome translation: 7-8
result: -1.0
fitness value: 0.2
---
Generation 17
[mutation on 35]
[mutation on 46]
chrom_string: 10001
chrom_string: 11100
chrom_string: 01100
chrom_string: 11100
chrom_string: 00111
chrom_string: 00110
chrom_string: 01011
chrom_string: 11101
chrom_string: 11100
chrom_string: 00111
chrom_string: 10001
chrom_string: 01100
chrom_string: 01110
chrom_string: 01000
chrom_string: 01010
chrom_string: 11011
eval string is: 7-7*8
chromosome translation: 7-7*8
result: -49.0
fitness value: 0.0188679245283
---
Generation 18
[mutation on 80]
[crossover on 21]
chrom_string: 01110
chrom_string: 01100
chrom_string: 10111
chrom_string: 11011
chrom_string: 11000
chrom_string: 01111
chrom_string: 00010
chrom_string: 11000
chrom_string: 11100
chrom_string: 10000
chrom_string: 10101
chrom_string: 10111
chrom_string: 10001
chrom_string: 11100
chrom_string: 01100
chrom_string: 11100
eval string is: 2
chromosome translation: 2
result: 2.0
fitness value: 0.5
---
Generation 19
[mutation on 7]
[mutation on 19]
chrom_string: 01110
chrom_string: 01000
chrom_string: 10111
chrom_string: 11010
chrom_string: 11000
chrom_string: 01111
chrom_string: 00010
chrom_string: 11000
chrom_string: 11100
chrom_string: 10000
chrom_string: 10101
chrom_string: 10111
chrom_string: 10001
chrom_string: 11100
chrom_string: 01100
chrom_string: 11100
eval string is: 8
chromosome translation: 8
result: 8.0
fitness value: -0.25
---
Generation 20
[mutation on 54]
chrom_string: 01110
chrom_string: 01000
chrom_string: 10111
chrom_string: 11010
chrom_string: 11000
chrom_string: 01111
chrom_string: 00010
chrom_string: 11000
chrom_string: 11100
chrom_string: 10000
chrom_string: 10100
chrom_string: 10111
chrom_string: 10001
chrom_string: 11100
chrom_string: 01100
chrom_string: 11100
eval string is: 8
chromosome translation: 8
result: 8.0
fitness value: -0.25
---
Generation 21
[crossover on 56]
chrom_string: 01111
chrom_string: 00011
chrom_string: 11000
chrom_string: 11001
chrom_string: 11000
chrom_string: 01110
chrom_string: 01000
chrom_string: 10111
chrom_string: 11010
chrom_string: 11000
chrom_string: 01111
chrom_string: 00010
chrom_string: 11000
chrom_string: 11100
chrom_string: 10000
chrom_string: 10100
eval string is: 3
chromosome translation: 3
result: 3.0
fitness value: 1.0
---
Generation 22
[crossover on 20]
chrom_string: 11000
chrom_string: 01110
chrom_string: 01000
chrom_string: 10111
chrom_string: 11010
chrom_string: 11000
chrom_string: 01111
chrom_string: 00010
chrom_string: 11000
chrom_string: 11100
chrom_string: 10000
chrom_string: 10100
chrom_string: 10111
chrom_string: 10001
chrom_string: 11100
chrom_string: 01100
eval string is: 8
chromosome translation: 8
result: 8.0
fitness value: -0.25
---
Generation 23
[crossover on 45]
chrom_string: 11100
chrom_string: 10000
chrom_string: 10100
chrom_string: 10111
chrom_string: 10001
chrom_string: 11100
chrom_string: 01100
chrom_string: 11100
chrom_string: 00111
chrom_string: 00100
chrom_string: 01011
chrom_string: 11101
chrom_string: 01100
chrom_string: 00111
chrom_string: 10001
chrom_string: 01100
eval string is: 7-7
chromosome translation: 7-7
result: 0.0
fitness value: 0.25
---
Generation 24
[mutation on 43]
[crossover on 44]
chrom_string: 10010
chrom_string: 00101
chrom_string: 11110
chrom_string: 10110
chrom_string: 00011
chrom_string: 11000
chrom_string: 10110
chrom_string: 00111
chrom_string: 00100
chrom_string: 00101
chrom_string: 00101
chrom_string: 11100
chrom_string: 01111
chrom_string: 00011
chrom_string: 00111
chrom_string: 00001
eval string is: 5
chromosome translation: 5
result: 5.0
fitness value: -1.0
---
Generation 25
[crossover on 23]
chrom_string: 11110
chrom_string: 00101
chrom_string: 10001
chrom_string: 11001
chrom_string: 00001
chrom_string: 01001
chrom_string: 01111
chrom_string: 00011
chrom_string: 11000
chrom_string: 11001
chrom_string: 11000
chrom_string: 01010
chrom_string: 01000
chrom_string: 10111
chrom_string: 11010
chrom_string: 11000
eval string is: 5+8
chromosome translation: 5+8
result: 13.0
fitness value: -0.111111111111
---
Generation 26
[mutation on 40]
[mutation on 51]
[mutation on 57]
chrom_string: 11110
chrom_string: 00101
chrom_string: 10001
chrom_string: 11001
chrom_string: 00001
chrom_string: 01001
chrom_string: 01111
chrom_string: 00011
chrom_string: 01000
chrom_string: 11001
chrom_string: 10000
chrom_string: 01110
chrom_string: 01000
chrom_string: 10111
chrom_string: 11010
chrom_string: 11000
eval string is: 5
chromosome translation: 5
result: 5.0
fitness value: -1.0
---
Generation 27
[mutation on 17]
[crossover on 18]
chrom_string: 01000
chrom_string: 01010
chrom_string: 01011
chrom_string: 11000
chrom_string: 11010
chrom_string: 00110
chrom_string: 01100
chrom_string: 00011
chrom_string: 10010
chrom_string: 00101
chrom_string: 11110
chrom_string: 10110
chrom_string: 00011
chrom_string: 11000
chrom_string: 10110
chrom_string: 00111
eval string is: 6*3
chromosome translation: 6*3
result: 18.0
fitness value: -0.0714285714286
---
Generation 28
chrom_string: 01000
chrom_string: 01010
chrom_string: 01011
chrom_string: 11000
chrom_string: 11010
chrom_string: 00110
chrom_string: 01100
chrom_string: 00011
chrom_string: 10010
chrom_string: 00101
chrom_string: 11110
chrom_string: 10110
chrom_string: 00011
chrom_string: 11000
chrom_string: 10110
chrom_string: 00111
eval string is: 6*3
chromosome translation: 6*3
result: 18.0
fitness value: -0.0714285714286
---
Generation 29
[mutation on 55]
chrom_string: 01000
chrom_string: 01010
chrom_string: 01011
chrom_string: 11000
chrom_string: 11010
chrom_string: 00110
chrom_string: 01100
chrom_string: 00011
chrom_string: 10010
chrom_string: 00101
chrom_string: 11110
chrom_string: 00110
chrom_string: 00011
chrom_string: 11000
chrom_string: 10110
chrom_string: 00111
eval string is: 6*3
chromosome translation: 6*3
result: 18.0
fitness value: -0.0714285714286
---
Generation 30
[mutation on 8]
[mutation on 23]
chrom_string: 01000
chrom_string: 01000
chrom_string: 01011
chrom_string: 11000
chrom_string: 11000
chrom_string: 00110
chrom_string: 01100
chrom_string: 00011
chrom_string: 10010
chrom_string: 00101
chrom_string: 11110
chrom_string: 00110
chrom_string: 00011
chrom_string: 11000
chrom_string: 10110
chrom_string: 00111
eval string is: 8-6*3
chromosome translation: 8-6*3
result: -10.0
fitness value: 0.0714285714286
---
Generation 31
[crossover on 21]
chrom_string: 10000
chrom_string: 01100
chrom_string: 11000
chrom_string: 00111
chrom_string: 00100
chrom_string: 01011
chrom_string: 11100
chrom_string: 01100
chrom_string: 00111
chrom_string: 10001
chrom_string: 01100
chrom_string: 01111
chrom_string: 01000
chrom_string: 01000
chrom_string: 01011
chrom_string: 11000
eval string is: 7-7*8
chromosome translation: 7-7*8
result: -49.0
fitness value: 0.0188679245283
---
Generation 32
[mutation on 32]
[mutation on 55]
[crossover on 37]
chrom_string: 10000
chrom_string: 11110
chrom_string: 00101
chrom_string: 10011
chrom_string: 11101
chrom_string: 00001
chrom_string: 00001
chrom_string: 01111
chrom_string: 00011
chrom_string: 00000
chrom_string: 11001
chrom_string: 10000
chrom_string: 01110
chrom_string: 01000
chrom_string: 10111
chrom_string: 10000
eval string is: 5
chromosome translation: 5
result: 5.0
fitness value: -1.0
---
Generation 33
[crossover on 11]
chrom_string: 01011
chrom_string: 00111
chrom_string: 11010
chrom_string: 00010
chrom_string: 00010
chrom_string: 11110
chrom_string: 00110
chrom_string: 00001
chrom_string: 10011
chrom_string: 00000
chrom_string: 11100
chrom_string: 10001
chrom_string: 01111
chrom_string: 00001
chrom_string: 10000
chrom_string: 11110
eval string is: 7
chromosome translation: 7
result: 7.0
fitness value: -0.333333333333
---
Generation 34
[mutation on 51]
[mutation on 67]
chrom_string: 01011
chrom_string: 00111
chrom_string: 11010
chrom_string: 00010
chrom_string: 00010
chrom_string: 11110
chrom_string: 00110
chrom_string: 00001
chrom_string: 10011
chrom_string: 00000
chrom_string: 10100
chrom_string: 10001
chrom_string: 01111
chrom_string: 00101
chrom_string: 10000
chrom_string: 11110
eval string is: 7
chromosome translation: 7
result: 7.0
fitness value: -0.333333333333
---
Generation 35
[mutation on 6]
chrom_string: 01011
chrom_string: 01111
chrom_string: 11010
chrom_string: 00010
chrom_string: 00010
chrom_string: 11110
chrom_string: 00110
chrom_string: 00001
chrom_string: 10011
chrom_string: 00000
chrom_string: 10100
chrom_string: 10001
chrom_string: 01111
chrom_string: 00101
chrom_string: 10000
chrom_string: 11110
eval string is: 2
chromosome translation: 2
result: 2.0
fitness value: 0.5
---
Generation 36
[mutation on 61]
chrom_string: 01011
chrom_string: 01111
chrom_string: 11010
chrom_string: 00010
chrom_string: 00010
chrom_string: 11110
chrom_string: 00110
chrom_string: 00001
chrom_string: 10011
chrom_string: 00000
chrom_string: 10100
chrom_string: 10001
chrom_string: 00111
chrom_string: 00101
chrom_string: 10000
chrom_string: 11110
eval string is: 2
chromosome translation: 2
result: 2.0
fitness value: 0.5
---
Generation 37
[crossover on 50]
chrom_string: 10100
chrom_string: 10001
chrom_string: 00111
chrom_string: 00101
chrom_string: 10000
chrom_string: 11110
chrom_string: 00101
chrom_string: 10111
chrom_string: 11101
chrom_string: 00001
chrom_string: 00001
chrom_string: 01111
chrom_string: 00011
chrom_string: 00000
chrom_string: 11001
chrom_string: 10000
eval string is: 7
chromosome translation: 7
result: 7.0
fitness value: -0.333333333333
---
Generation 38
[mutation on 57]
chrom_string: 10100
chrom_string: 10001
chrom_string: 00111
chrom_string: 00101
chrom_string: 10000
chrom_string: 11110
chrom_string: 00101
chrom_string: 10111
chrom_string: 11101
chrom_string: 00001
chrom_string: 00001
chrom_string: 01011
chrom_string: 00011
chrom_string: 00000
chrom_string: 11001
chrom_string: 10000
eval string is: 7-3
chromosome translation: 7-3
result: 4.0
fitness value: None
---
So, after 38 generations, 7-3 is derived as the arithmetic sequence which equals our target value, 4.
Rupert Scammell
Last modified: Fri Feb 25 00:31:47 PST 2005