#!/usr/bin/env python
"""
Recombination. Individuals in the new population are generated by crossing over
the attributes of two parent individuals from the old population.
The CROSSOVER_PROBABILITY parameter controls the proportion of individuals in the
population that are subject to mating (the rest is copied without changes, but
both groups are later subject to independently applied mutation).
Prints best, worst and median fitness of individuals in the final population.

QUESTION: does it work better now?
QUESTION: what is the minimum number of generations needed to find the TARGET?
QUESTION: does higher or lower probability of crossover work better?
QUESTION: what happens if mutation is not used?

"""
import string
import random

from copy import deepcopy
from operator import attrgetter
from collections import namedtuple

TARGET = "CHARLES DARWIN"
CHARACTERS = string.ascii_uppercase + " "

GENERATIONS = 50
POPULATION_SIZE = 100
TOURNAMENT_SIZE = 5
CROSSOVER_PROBABILITY = 0.5
MUTATION_PROBABILITY = 0.5
MUTATION_CHANCE = 0.1

Individual = namedtuple("Individual", "solution fitness")


def evaluate(solution):
	return sum(1 for s,t in zip(solution, TARGET) if s != t)


def init():
	solution = [random.choice(CHARACTERS) for i in range(len(TARGET))]
	return Individual(solution, evaluate(solution))


def mutate(solution):
	for i in range(len(solution)):
		if random.random() < MUTATION_CHANCE:
			solution[i] = random.choice(CHARACTERS)


def crossover(a, b):
	"""
	One point crossover: AAA|BBBBBBB, BBB|AAAAAAA (in place).

	"""
	point = random.randrange(1, min(len(a), len(b)))
	a[point:], b[point:] = b[point:], a[point:]


def crossover_uniform(a, b, probability=0.5):
	"""
	Uniform crossover: AAABBABBABB, BBBAABAABAA (in place).

	"""
	size = min(len(a), len(b))
	for i in range(size):
		if random.random() < probability:
			a[i], b[i] = b[i], a[i]


def select(population, k, tournament_size):
	chosen = []
	for i in range(k):
		candidates = random.sample(population, tournament_size)
		winner = min(candidates, key=attrgetter("fitness"))
		chosen.append(deepcopy(winner))
	return chosen


def variate(population):
	for i in range(1, len(population), 2):
		if random.random() < CROSSOVER_PROBABILITY:
			crossover(population[i-1].solution, population[i].solution)

	for i in range(len(population)):
		if random.random() < MUTATION_PROBABILITY:
			mutate(population[i].solution)
	return population


population = [init() for i in range(POPULATION_SIZE)]

for i in range(GENERATIONS):
	chosen = select(population, len(population), TOURNAMENT_SIZE)
	population = variate(chosen)

	for i in range(len(population)):
		new_fitness = evaluate(population[i].solution)
		population[i] = population[i]._replace(fitness=new_fitness)

population.sort(key=attrgetter("fitness"))
params = population[0].fitness, population[-1].fitness, population[POPULATION_SIZE / 2].fitness
print("best={0}, worst={1}, median={2}".format(*params))