Genetic Algorithm Tutorial
I wrote this a long time ago, the code might show this.
# author : Alexander Orozco
# copyright : DoWhatEverYouWantWithIt LICENSE
# email : alex@rozgo.com
# language : Python script
#
# This is a simple demostration of genetic algorithms.
# Given these digits: '0,1,2,3,4,5,6,7,8,9' the algorithm
# must combine them with these operators '+,-,*,/' and
# find an equation that can evaluate to a given target.
# I'll be using binary encoded genes to represent
# chromosomes.
#
# Example:
# 6*8+4+9-5
#
# Other resources:
# I find A-Depot very helpfull - http://ai-depot.com/
# And here (http://www.ai-junkie.com/gat1.htm) is the
# tutorial I used to write this script
#
# A WORD ABOUT GENETIC ALGORITHMS (extracted from www.geneticalgo.com)
# Most Genetic Algorithms work with a constant population
# size. As the computation progresses from one generation
# to the other, the weaker individuals gradually pave way
# for the stronger ones, corresponding to some improved
# solutions. Comparisons between members are made based on
# what is called the fitness value acquired directly or
# indirectly from the system.
import sys
import random
# GENE TYPE ENCODING
# We need a way to encode any potential solution into a
# chromosome
gene_t = {}
gene_t['0'] = ['0','0','0','0']
gene_t['1'] = ['0','0','0','1']
gene_t['2'] = ['0','0','1','0']
gene_t['3'] = ['0','0','1','1']
gene_t['4'] = ['0','1','0','0']
gene_t['5'] = ['0','1','0','1']
gene_t['6'] = ['0','1','1','0']
gene_t['7'] = ['0','1','1','1']
gene_t['8'] = ['1','0','0','0']
gene_t['9'] = ['1','0','0','1']
gene_t['+'] = ['1','0','1','0']
gene_t['-'] = ['1','0','1','1']
gene_t['*'] = ['1','1','0','0']
gene_t['/'] = ['1','1','0','1']
#
# ENCODE A SOLUTION
# This will encode a potential solution into a binary
# representation of a chromosome
#
# Example:
# Given solution: 2+5*8/5
# Encodes to: 0010 1010 0101 1100 1000 1101 0101
#
def encode(solution):
chromosome = []
for char in solution:
if gene_t.has_key(char):
chromosome.extend(gene_t[char])
return chromosome
#
# DECODE A CHROMOSOME
# This will reverse a binary representation of a
# chromosome into a string representation of an
# equation. The reverse of the above function.
#
def decode(chromosome):
solution = []
for gene in range(0,len(chromosome),4):
for key in gene_t.keys():
if gene_t[key] == chromosome[gene:gene+4]:
solution.append(key)
return solution
#
# PARSE A SOLUTION
# This will parse a solution into a valid equation.
# Following the pattern:
# digit-operand-digit-operand-...
#
# Example:
# Solution: 2+/4*3/+4-5
# Parsed: 2+4*3/4-5
#
def parse(solution):
# generate valid expression
expression = ''
for i in range(0,len(solution)):
s = solution[i]
if s.isdigit():
if int(s) == 0 and (len(expression) == 0 or not expression[-1:].isdigit()):
pass
else:
expression += s
elif len(expression) > 1 and expression[-1:].isdigit():
expression += s
# last character must be digit
if len(expression) > 0 and not expression[-1:].isdigit():
expression = expression[:-1]
return expression
#
# SOLVE A PARSED SOLUTION
# This will evaluate the parsed solution.
#
def solve(parsed):
return int(eval(parsed))
#
# FITNESS OF CHROMOSOME
# This will return a fitness score that's inversely
# proportional to the difference between the target
# and the value a chromosome represents.
#
def fitness(chromosome,target):
fit = abs(target-solve(parse(decode(chromosome))))
if fit == 0:
return 0
return 1/float(fit)
#
# ROULETTE SELECTION OF CHROMOSOME
# Randomly choose a chromosome from the population
# proportionally to its fitness.
#
def roulette(population,target,maxfitness):
pick = random.random() * maxfitness
totalfitness = 0
for chromosome in population:
totalfitness += fitness(chromosome,target)
if totalfitness > pick:
return chromosome
#
# CROSSOVER OF CHROMOSOMES
# Given two chromosomes the rate will decide the
# chance that these chromosomes will swap their genes.
# A random gene is selected and crossover is performed
# swapping all genes from that point on.
#
def crossover(chromosome_a,chromosome_b,rate):
if random.random() < rate:
start_gene = random.randint(0,len(chromosome_a)-1)
for gene in range(start_gene,len(chromosome_a)):
swap = chromosome_a[gene]
chromosome_a[gene] = chromosome_b[gene]
chromosome_b[gene] = swap
#
# MUTATE CHROMOSOME
# Given a chromosome the rate will decide the chance
# of a gene being flipped (bit 0 to 1 or 1 to 0)
#
def mutate(chromosome,rate):
for gene in range(0,len(chromosome)):
if random.random() < rate:
if chromosome[gene]=='0':
chromosome[gene]='1'
else:
chromosome[gene]='0' # fix by Lon Barfield lonwen@hotmail.com
#
# SPAWN A CHROMOSOME TO LIFE
# Generate a chromosome with randomly generated
# genes.
#
def spawn(size):
chromosome=[]
for gene in range(0,size):
if random.random() < 0.5:
chromosome.append('0')
else:
chromosome.append('1')
return chromosome
#
# MAIN EXECUTION FUNCTION
# Get some user input, generate an initial population,
# roulette select chromosomes by fitness, and
# crossover/mute them into a new population of the same
# size. Each chromosome of the population is decoded into
# a potential solution, then evaluated to check if target
# is met. Keep on going generation to generation.
#
def main():
# settings
POPULATION_SIZE = 10
CHROMOSOME_SIZE = 100
TARGET = 25
CROSSOVER_RATE = 0.7
MUTATE_RATE = 0.01
user_input = raw_input('TARGET=(25)')
if len(user_input)>0:
TARGET = int(user_input)
user_input = raw_input('CHROMOSOME_SIZE=(100)')
if len(user_input)>0:
CHROMOSOME_SIZE = int(user_input)
user_input = raw_input('POPULATION_SIZE=(10)')
if len(user_input)>0:
POPULATION_SIZE = int(user_input)
user_input = raw_input('CROSSOVER_RATE=(0.7)')
if len(user_input)>0:
CROSSOVER_RATE = float(user_input)
user_input = raw_input('MUTATE_RATE=(0.01)')
if len(user_input)>0:
MUTATE_RATE = float(user_input)
# create population
finished = False
generations = 0
population = []
for i in range(0,POPULATION_SIZE):
population.append(spawn(CHROMOSOME_SIZE))
while finished==False:
# test if target met
for chromosome in population:
parsed = parse(decode(chromosome))
result = solve(parsed)
print result,'\t=','\t',parsed,'\t'#,''.join(decode(chromosome))
if result == TARGET:
print 'SOLVED !!!!!!'
print 'Generations required:',generations
print 'Expression:',parse(decode(chromosome)),'=',result
finished = True
break
#sys.exit()
#if finished==True:
# break
# create new population by mating
totalfitness = 0
for chromosome in population:
totalfitness += fitness(chromosome,TARGET)
next_generation=[]
for i in range(0,POPULATION_SIZE/2):
# roulette parents
chromosome_a = roulette(population,TARGET,totalfitness)[:]
chromosome_b = roulette(population,TARGET,totalfitness)[:]
# crossover
crossover(chromosome_a,chromosome_b,CROSSOVER_RATE)
# mutate
mutate(chromosome_a,MUTATE_RATE)
mutate(chromosome_b,MUTATE_RATE)
next_generation.append(chromosome_a)
next_generation.append(chromosome_b)
population = next_generation
generations += 1
print '----------------------------- Generation #',generations,'-----------------------------'
user_input = raw_input('Again? (y/n)')
if user_input != 'n':
main()
main()