I was writing a Python script that starts with a random string and then using Genetic Algorithm tries to find the target string. Although I have successfully implemented the algorithm but it's taking too much time to execute, even for a string of length 21 it took around 2mins.
# A utility function that decide which two parents two select for crossover.
# based on Roulette Wheel Sampling
def select_parent():
# totalFitness is sum of fitness of all the organism of the current generation
pick = random.randint(0, totalFitness)
current = 0
# Roulette Wheel Sampling implementation
# populationSize = 10 * length(targetString)
for index in range(populationSize):
current += fitness_all[index]
if current >= pick:
return index
# A utility function to perform crossover.
def produce_next_generation():
for organism in nextGeneration:
# select two parents using Roulette Wheel Sampling
parent_first = currentGeneration[select_parent()]
parent_second = currentGeneration[select_parent()]
cross_over_point = random.randint(0, targetLength - 1)
new_genes = [''] * targetLength
for i in range(targetLength):
# mutation rate is set to 0.001
mutate_this_gene = random.randint(0, int(1 / mutationRate))
# target string contains upper and lower case chars only
if mutate_this_gene == 0:
new_genes[i] = random.choice(string.ascii_uppercase + string.ascii_lowercase) # target string is combination of upper and lower case
elif i <= cross_over_point:
new_genes[i] = parent_first.genes[i]
else:
new_genes[i] = parent_second.genes[i]
organism.genes = ''.join(new_genes)
global currentGeneration
currentGeneration = [organism for organism in nextGeneration]
Here are the two functions, that I feel can be optimized further(rest of the code just defines the fitness function and a loop that runs endlessly unless target string is found.)
I took inspiration from a similar code written in C.
Rest of the code:
import random, datetime, string
# Define some global variables here
target = 'Brevityisthesoulofwit'
targetLength = len(target)
populationSize = 10 * targetLength
currentGeneration = [] # the
# this will store the generation created due to cross-over, will finally be copied into current generation
nextGeneration = []
totalFitness = 0 # this for the simulation of Roullete Wheel Sampling
idealOrganism = None
mutationRate = 0.001
# The Chromosome class
class Chromosome:
def __init__(self, genes):
self.genes = genes
def get_fitness(self, ideal):
ideal_genes = ideal.genes
return sum(1 for i in range(targetLength) if self.genes[i] == ideal_genes[i])
@staticmethod
def get_new_random_genes():
return ''.join(random.choice(string.ascii_uppercase + string.ascii_lowercase) for i in range(targetLength))
def create_initial_generation():
global idealOrganism
idealOrganism = Chromosome(target)
for i in range(populationSize):
currentGeneration.append(Chromosome(Chromosome.get_new_random_genes()))
nextGeneration.append(Chromosome(Chromosome.get_new_random_genes()))
def evaluate_organism():
fitness_all_new = [organism.get_fitness(idealOrganism) for organism in currentGeneration]
global totalFitness
totalFitness = sum(fitness_all_new)
return fitness_all_new
def is_generation_perfect():
for organism in currentGeneration:
if organism.genes == target:
return True
return False
if __name__ == '__main__':
create_initial_generation()
generation = 1
fitness_all = None
start_time = datetime.datetime.now()
while True:
if is_generation_perfect():
break
fitness_all = evaluate_organism()
produce_next_generation()
generation += 1
finish_time = datetime.datetime.now()
print('Program terminated after {} generations.\nTime Taken : {} seconds'.format(generation, finish_time-start_time))