#!/usr/bin/python
# -*- coding: iso-8859-15 -*-

#### TODO ####
# Nuevo diagrama de flujo:
# 1. Crear población inicial de longitud L y bases las dadas (Generación = 0)
# 2. Si se cumple algún criterio de parada ir a 10
# 3. Evaluar los individuos
# 4. Individuos = 0
# 5. Si Individuos >= M ir a 8
# 6. Seleccionar:
# 6.1. Copia de un individuo a la nueva generación (Individuos + 1)
# 6.2. Cruce entre dos individuos para generar 2 nuevos (Individuos + 2)
# 6.3. Seleccionar y cruzar un individuo (Individuos + 1)
# 7. Ir a 5
# 8. Generación + 1
# 9. Ir a 2
# 10. Mostrar resultado y parar.

import random, copy

class Individual:

	def __init__ (self, bases = ['b'], N = 4):
		self.bases = bases
		self.N = N
		self.basesLen = len (bases)
		self.chromo = []
		self.fitness = None
		for i in xrange (N):
			self.chromo.append (bases [random.randrange (self.basesLen)])
	
	def __str__ (self):
		return '%s -> %s' % (str (self.chromo), str (self.fitness))

	def evaluate (self, fitness):
		self.fitness = fitness (self.chromo)

	def mutate (self):
		base = random.randrange (self.N)
		self.chromo [base] = self.bases [random.randrange (self.basesLen)]

	def breed (self, x, y):
		point = random.randrange (self.N - 1)
		self.chromo = []
		for i in range (self.N):
			if i <= point:
				self.chromo.append (x.chromo [i])
			else:
				self.chromo.append (y.chromo [i])

class Population:

	def __init__ (self):
		self.population = []
		self.len = 0
		self.totalFitness = 0
		self.bestI = None
	
	def __len__ (self):
		return self.len

	def __str__ (self):
		return '\n'.join (['%3d %s' % (i + 1, str (x)) for i, x in enumerate (self.population)])

	def evaluate (self, fitness):
		self.totalFitness = 0
		self.bestI = None
		self.bestV = None
		for x in self.population:
			x.evaluate (fitness)
			self.totalFitness += x.fitness
			if x.fitness > self.bestV:
				self.bestV = x.fitness
				self.bestI = x
	
	def addIndividual (self, individual):
		self.population.append (individual)
		self.len += 1
	
	def selectIndividual (self):
		sel = self.population [0]
		del self.population [0]
		return sel
		# Addapt for float fitness
		select = random.randrange (int (self.totalFitness * 1000))
		for x in self.population:
			try:
				select -= x.fitness * 1000
			except ValueError:
				return self.population [0]
			if select < 0:
				return x
	
	def mean (self):
		return 1.0 * self.totalFitness / self.len

	def bestIndividual (self):
		return self.bestI.chromo

	def bestValue (self):
		return self.bestV

class Genyal:

	def __init__ (self, M = 10, bases = [], N = 4,
			fitness = None, historics = False, probs = [0.1, 0.8]):
		self.pop = Population ()
		self.M = M
		self.bases = bases
		self.N = N
		for i in range (self.M):
			self.pop.addIndividual (Individual (self.bases, self.N))
		self.fitness = fitness
		self.probs = probs
		self.generation = 0
		self.pop.evaluate (self.fitness)
		self.historics = historics
		self.hmean = []
		self.hbest = []
	
	def __str__ (self):
		return 'Generation %d:\n%s\n' % (self.generation, str (self.pop))

	def nextGen (self):
		self.pop.population.sort (lambda x, y: int (y.fitness * 100) - int (x.fitness * 100))
		newPop = Population ()
		newPop.addIndividual (self.pop.population [0])
		newPop.addIndividual (self.pop.population [1])
		while len (newPop) < self.M - 2:
			individual = self.pop.selectIndividual ()
			select = random.random ()
			if select < self.probs [0]:
				newPop.addIndividual (individual)
			elif select < self.probs [1]:
				otherIndividual = self.pop.selectIndividual ()
				newIndividual1 = Individual (self.bases, self.N)
				newIndividual2 = Individual (self.bases, self.N)
				newIndividual1.breed (individual, otherIndividual)
				newIndividual2.breed (otherIndividual, individual)
				newPop.addIndividual (newIndividual1)
				newPop.addIndividual (newIndividual2)
			else:
				newIndividual = copy.deepcopy (individual)
				newIndividual.mutate ()
				newPop.addIndividual (newIndividual)
		self.pop = newPop
		self.generation += 1
		self.pop.evaluate (self.fitness)
		if self.historics:
			self.hmean.append (self.pop.mean ())
			self.hbest.append (self.pop.bestValue ())
	
	def statics (self):
		return (self.generation, self.pop.mean (), self.pop.bestValue ())

	def bestIndividual (self):
		return self.pop.bestIndividual ()

	def histoDump (self, file):
		fd = open (file, 'w')
		print >> fd, 'f1 = %s;' % str (self.hmean)
		print >> fd, 'f2 = %s;' % str (self.hbest)
		print >> fd, 't = [0 : 1 : %d];' % (self.generation - 1)
		print >> fd, 'plot (t, f1, t, f2);'
		print >> fd, 'grid on;'
		print >> fd, 'pause;'

if __name__ == '__main__':
	ga = Genyal (bases = range (10), fitness = sum, historics = True)
	n = 100
	for i in range (n):
		ga.nextGen ()

	ga.histoDump ('test')