import random

class chromosome:
	def __init__(self, alleles):
		self.alleles = alleles
		self._fitness = None
		
	def mutate(self):
		self._fitness = None
		idx = random.randrange(0, len(self.alleles))
		self.alleles[idx] = not self.alleles[idx]
	
	def fitness(self):
		if self._fitness == None:
			self._fitness = self.alleles.count(True)
		return self._fitness
		
	def __cmp__(self, other):
		return other.fitness() - self.fitness()
			
	def crossover(self, other):
		xover_pt = random.randrange(0, len(self.alleles))
		c1_alleles = self.alleles[ : xover_pt] + other.alleles[xover_pt : len(self.alleles)]
		c2_alleles = other.alleles[ : xover_pt] + self.alleles[xover_pt : len(self.alleles)]
		return chromosome(c1_alleles), chromosome(c2_alleles)
		
	def __str__(self):
		sr = str(self.fitness()) + ': '
		for allele in self.alleles:
			if allele:
				sr += '1'
			else:
				sr += '0'
		return sr
		

class ga:
	def __init__(self, generations=100, size=100, length=50, pr_mutation=0.2, pr_crossover=0.8):
		self.generations = generations
		self.size = size
		self.pr_mutation = pr_mutation
		self.pr_crossover = pr_crossover
		
		self.population = []
		for i in range(self.size):
			alleles = [False] * length
			#ones = random.randrange(0, length)
			#alleles = [True] * ones + [False] * (length - ones)
			#random.shuffle(alleles)
			for j in range(length):
				if random.randint(0,1) == 1:
					alleles[j] = True
			#print alleles
			self.population.append(chromosome(alleles))
			
	def __get_population(self):
		return self.population
	
	population = property(fget=__get_population)
	
	def probabilities(self):
		self.population.sort()

		total_fitness = reduce(lambda x, y:x + y.fitness(), self.population, 0.0)

		probabilities = [0.0] * len(self.population)
		pr_sum = 0.0

		for i in range(len(self.population)):
			prob = self.population[i].fitness()/total_fitness
			probabilities[i] = pr_sum + prob
			pr_sum += prob

		return probabilities
		
	def select(self, probabilities):
		r = random.random()
		for i in range(len(probabilities)):
			if r <= probabilities[i]:
				return self.population[i]
		return self.population[-1]
		
		
	def evaluate(self):
		#for generation in range(self.generations):
		generation = 0
		while True:
			new_population = []
			probabilities = self.probabilities()
			fittest = None
			while len(new_population) < len(self.population):
				parent1 = self.select(probabilities)
				parent2 = self.select(probabilities)
				cross = random.random()
				if cross <= self.pr_crossover:
					child1,child2 = parent1.crossover(parent2)
				else:
					child1,child2 = parent1,parent2
				
				# mutate child1 with Pr(mutate)
				mut = random.random()
				if mut <= self.pr_mutation:
					child1.mutate()
				# remember the fittest
				if fittest is None or child1.fitness() > fittest.fitness():
					fittest = child1
				
				# mutate child2 with Pr(mutate)
				mut = random.random()
				if mut <= self.pr_mutation:
					child2.mutate()
				# remember the fittest
				if fittest is None or child2.fitness() > fittest.fitness():
					fittest = child2
				
				new_population.append(child1)
				new_population.append(child2)
			generation += 1
			print 'Generation: %(g)4d | Fitness: %(f)5.2f | %(a)s' % {
				'g':generation,
				'f':fittest.fitness(),
				'a':fittest,
			}
			if fittest.fitness() == 50:
				break
			self.population = new_population

def main():
	g=ga()
	g.evaluate()
	
if __name__ == '__main__':
	main()