# IMPORTANT: This is NOT a full GA program.
# This program contains a collection of functions namely init(), evaluate(), select(),
# recombine() and mutate() that you can use as TEMPLATES in your assignments.
# The function-implementations here are only EXAMPLES. However, under each function,
# notes are included that provide pointers as to how you may modify these functions
# to work out your assignment problems. Further, note that a full GA uses the outputs
# from these functions and uses them in a variety of ways to solve a problem.

import random, string, numpy

# EXAMPLE init() function
# Initialize the population with random individuals
def init(): 
   
    # Create an empty population
    pop = []
   
    for i in range(pop_size):
        genotype = ''.join(random.choice(string.ascii_letters) for x in range(genotype_size))
        pop.append(genotype)
   
    return(pop)
    
    # NOTES:
    # This is an EXAMPLE population made up of strings of English characters of both cases.
    # You can also use random.choice() to select from a list you provide. For example,
    # if you want to randomly choose only from a list of the following symbols: 'F', '+', 'A',
    # you can say >>>random.choice(['F', '+', 'A'])

# EXAMPLE evaluate() function
# Go through the population list, pick each genotype, evaluate it, and record its fitness score
def evaluate(pop):
    
    # Create an empty list of fitness values
    fitness = []
    for i in range(pop_size):
        genotype = pop[i]
        fitness_value = sum(ord(i) for i in genotype)  #sums up the ascii values of the characters
        fitness.append(fitness_value)
    
    # Normalize fitness. IMPORTANT: If you don't multiple by 1.0, you will get all zeros
    fitness = [f * 1.0/sum(fitness) for f in fitness]
    
    return(fitness)
    
    # NOTES:
    # This is an EXAMPLE fitness function, where each genotype is evaluated as the sum of the
    # ascii values of the characters of the genotype. For Q1b in your assignment, you should write
    # a fitness function that counts the number of lower case letters in your genotype.
    # For Q1c, your fitness function will be quite different: you should first interpret the genotype
    # as an L-system production rule, generate the L-system strings upto a maximum of n iterations
    # and then evaluate only the string in the last iteration in some fashion (details in the question).

# Select two parents using roulette wheel method, also known as 'fitness proportionate' selection
# Reference: http://en.wikipedia.org/wiki/Fitness_proportionate_selection
def select(fitness, pop):
    
    # Select first parent
    parent_1_index = -9999  #indicates that parent_1 is yet to be chosen
    cumulated_fitness = 0
    roulette_marker = random.random()  #indicates that the 'roulette wheel' has settled on a random number
    for i in range(pop_size):
        cumulated_fitness += fitness[i]
        if cumulated_fitness >= roulette_marker:
            parent_1_index = i
            break
    
    # Select second parent different from the first parent
    parent_2_index = parent_1_index  #indicates that parent_2 is yet to be chosen
    while parent_2_index == parent_1_index:  #this ensures that the two parents chosen are distinct
        cumulated_fitness = 0
        roulette_marker = random.random()  #indicates that the 'roulette wheel' has settled on a random number
        for i in range(pop_size):
            cumulated_fitness += fitness[i]
            if cumulated_fitness >= roulette_marker:
                parent_2_index = i
                break
    
    return([pop[parent_1_index], pop[parent_2_index]])
    
    # NOTES:
    # It is possible but rare that in the entire population only one individual has a non-zero fitness. In such cases,
    # the part of the code above that selects parent_2 will wait forever. Take care of such situations -- you can simply
    # randomly select another individual with a 0-fitness.

# Recombine two parents to produce two offsprings, with a certain probability
# specified by recombination_rate
def recombine(parent_1, parent_2, recombination_rate):
   
    r = random.random()
   
    if r <= recombination_rate:  #recombination_rate is a value between 0 and 1
        #recombine
        slice_point = random.randint(0, genotype_size-1)
        offspring_1 = parent_1[0 : slice_point] + parent_2[slice_point : genotype_size]
        offspring_2 = parent_2[0 : slice_point] + parent_1[slice_point : genotype_size]
        return([offspring_1, offspring_2])
   
    else:  #don't recombine
        return([parent_1, parent_2])

# EXAMPLE mutation method
# Mutate a genotype with a certain probability of mutation per-symbol specified by 'mutation_rate'.
# A mutation typically adds a small amount of 'shift' to a genotype letter.
def mutate(genotype, mutation_rate):
   
    mutated_genotype = genotype  #indicates that the genotype is yet to be mutated
   
    for i in range(genotype_size):
   
        r = random.random()
   
        if r <= mutation_rate:  #rate is a value between 0 and 1
            # then mutate this symbol by a small shift on the alphabet scale, else proceed to the next symbol
            
            # 'numpy.random.poisson' draws a random integer from a bell shaped distribution centered at 'lam',
            # where 'lam' is short for 'lambda' that represents the mean of the distribution.
            # So 'numpy.random.poisson(lam = 2)' typically returns the number 2, occasionally 1 and 3, even more
            # rarely 0 and 4.
            
            mutation_magnitude = numpy.random.poisson(lam = 2)  
            mutation_direction = random.choice([-1, 1])
            mutation = mutation_direction * mutation_magnitude
            
            present_symbol_ascii = ord(genotype[i])
            
            mutated_symbol_ascii = present_symbol_ascii + mutation
            
            if (mutated_symbol_ascii < ord('A')): mutated_symbol_ascii = ord('A')
            if (mutated_symbol_ascii > ord('z')): mutated_symbol_ascii = ord('z')

            new_symbol = chr(mutated_symbol_ascii)
            
            mutated_genotype = mutated_genotype[0 : i] + new_symbol + mutated_genotype[(i+1) : genotype_size]

    return(mutated_genotype)
    
    # NOTES:
    # This is an EXAMPLE mutation method that replaces a character with another that is a small distance away from it.
    # For Q1c of your assignment, you will have to randomly choose another symbol from the
    # list of L-system symbols you used to initialize the genotypes originally, using, for example,
    # mutated_symbol = random.choice(['F', 'B', '+', '-'])

# EXAMPLE GA parameers
pop_size = 20  #population size
num_generations = 100
genotype_size = 10
recombination_rate = 0.2
mutation_rate = 0.2

# Main GA loop.
# This is NOT the full GA. A full GA may do other things in between the lines below.

pop = init()

for gen in range(num_generations):

	fitness = evaluate(pop)
	
	# create a new population that will hold the next generation of genotypes
	# if you are using 'elite' selection, then simply copy the top x% of individuals from pop to new_pop
	new_pop = []  

	while (len(new_pop) < pop_size):  # continue loop until new_pop has pop_size number of individuals

		[parent_1, parent_2] = select(fitness, pop)

		[offspring_1, offspring_2] = recombine(parent_1, parent_2, recombination_rate)

		mutated_genotype_1 = mutate(offspring_1, mutation_rate)
		mutated_genotype_2 = mutate(offspring_2, mutation_rate)
		
		new_pop.append(mutated_genotype_1)
		new_pop.append(mutated_genotype_2)
		
		# continue loop until new_pop has pop_size number of individuals

	pop = new_pop  #replace current population with new population

	# print best genotype and its fitness score of current generation
	# continue loop to create next generation

# print overall best genotype and its fitness score at the end of num_generations