import random

"""
Basic genetic programming code.
@version v0.3

@author Scott Hurring (scott at hurring dot com)
@uri http://hurring.com/code/python/genetic/
@license GPL

This is a basic introduction to building a John Holland style 
genetic algorithm that operates on 'cells' containing 'dna'.

Each 'cell' is evaluted by whatever fitness class you define.

Included with this code are two examples... one evaluating
the decimal representation of a list of bits, and another
evaluating the characters of a string.  Both serve to illustrate
the flexibility and power of genetic programming.

This code is not robust or complete or full-featured.
I hacked the first version out for a class i was taking about
the fundamentals of AI, and i updated it a little more as i
was reading "The Blind Watchmaker" so that i could play with
some examples of my own inspired by the book.

It's meant mostly for play and experimentation, to teach
myself the basics of genetic programming, but i released
it because i figured someone else might find it useful.
"""

class Nature(object):
	"""Nature.  The world of cells."""

	# Mutation probability
	mutation = 0.001
	# Crossover probability
	crossover = 0.5
	# Percent of current generation to select for breeding
	breed_pct = 0.10
	# Current generation
	generation = 0
	# if average fitness gets over this, halt the simulation
	fitness_threshhold = 99.0
	# History of average fitnesses
	fitness_history = []
	
	def __init__(self, judge):
		self.judge = judge
		
	def run(self, population, n):
		"""Run population through 'n' number of generations.
		Replace each parent population with it's children."""
		for i in range(n):
			self.generation = i
			population = self.step(population)
			if self.fitness_history[self.generation] > self.fitness_threshhold:
				print "Hit the fitness threshhold, stopping early."
				return population
		return population
		
	def step(self, p):
		"""Step through a single generation.  Judge fitness and breed."""

		# Evaluate current generation's fitness and sort high>low
		scores = self.evaluate(p)
		
		# Select 'n' top scored cells for breeding
		n = int(len(scores) * self.breed_pct)
		breeders = scores[0:n]
		
		# Breed an equal number of children as there are parents
		children = self.breed(len(p), breeders)
		return children
			
	def evaluate(self, p):
		"""Evaluate fitness of each cell in a population.
		Fitness is some numeric value between 1..100.
		Return sorted array of cells and their scores"""
		
		def score_sort(a,b):
			"""sort the list by 'score'"""
			if a['score'] > b['score']: return -1
			if a['score'] < b['score']: return 1
			return 0
			
		total = 0
		scores = []
		for cell in p:
			score = self.judge.fitness(cell)
			scores.append({'score':score, 'cell':cell})
			total += score
			
		average = (total / len(p))
		self.fitness_history.insert(self.generation, average)
		print self.generation, ":", average
		
		scores.sort(score_sort)
		return scores
		
	def breed(self, n, parents):
		"""Create 'n' children from the cells in the 'parents' list
		to replace the current generation."""
		children = []
		for i in range(n):
			# Choose two random cells to mate
			(a,b) = random.sample(parents, 2)
			child = a['cell'].mate(b['cell'], self.crossover, self.mutation)
			children.insert(i, child)
		return children
			
	def initial_population(self, cell, n):
		"""Create an initial population of 'n' cells w/ random dna"""
		p = []
		for i in xrange(n):
			c = cell()
			c.randomize()
			p.append(c)
		return p
		
	def avg_fitness(self, p):
		"""Determine average fitness of entire population"""	
		total = 0
		for cell in p:
			#print cell, judge.fitness(cell)
			total += self.judge.fitness(cell)
		return (total/ len(p))
	
class Cell(object):
	"""A single cell holding some 'dna'
	Subclass this to create your own cells"""
	dna = None
	length = 0	# the length of the dna
	dad_id = 0	# dad's id
	mom_id = 0	# mom's id
	name = "Cell"
	
	def __init__(self):
		self.init()
	
	def __str__(self):
		return "<%s:%i %s (%i,%i)>" % (self.name, id(self), repr(self.dna), self.dad_id, self.mom_id)
	
	def __repr__(self):
		return "<%s %s>" % (self.name, repr(self.dna))
		
	def mate(self, other, crossover, mutation):
		"""Mate me with 'other', return a single new baby."""
		baby = self.clone()
		
		baby.dad_id = id(self)
		baby.mom_id = id(other)
		
		for i in range(baby.length):
			rand = random.random()
			
			if rand <= crossover:
				bit = self.get(i)
			else:
				bit = other.get(i)
				
			if rand <= mutation:
				bit = baby.mutate(bit)
				
			baby.set(i, bit)
			
		return baby