small python script that evolves an equation towards a solution

genetic.py

#    author        : Alex Rozgo
#    date          : Sun Jun 6 2004
#    copyright     : DoWhatEverYouWantWithIt LICENSE
#    email         : [email protected]
#
#    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
#
#
#    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 [email protected]

#
#    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()