# 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