import random

class chromosome:
	def __init__(self, alleles):
		self.alleles = alleles
		self._fitness = None
		
	def flip_mutate(self):
		idx = random.randrange(0, len(self.alleles))
		self.alleles[idx] = random.randrange(1, 10)
		
	def swap_mutate(self):
		idx1 = random.randrange(0, len(self.alleles))
		idx2 = random.randrange(0, len(self.alleles))
		while idx2 == idx1:
			idx2 = random.randrange(0, len(self.alleles))
		temp = self.alleles[idx1]
		self.alleles[idx1] = self.alleles[idx2]
		self.alleles[idx2] = temp
		
	def mutate(self):
		self._fitness = None
		return random.choice([self.flip_mutate, self.swap_mutate])()
	
	def fitness(self):
		if self._fitness == None:
			self._fitness = reduce(lambda x,y:x*y, self.alleles[:5], 1.0)/reduce(lambda x,y:x*y, self.alleles[5:], 1.0)
		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):
		return str(self.alleles)
		

class ga:
	def __init__(self, generations=100, size=100, 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 = []
			for i in range(10):
				alleles.append(random.randint(1, 10))
			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)9.2f | %(a)s' % {
				'g':generation,
				'f':fittest.fitness(),
				'a':fittest,
			}
			if fittest.fitness() == 10**5:
				break
			self.population = new_population

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