Genetic Algorithm? What is it about? It is a heuristic search that was inspired by the great Charles Darwin theory of evolution. Once again the computer science field has drawn its inspiration from the biological field.

Charles Darwin’s theory of evolution states that evolution happens by natural selection

The genetic Algorithm shows the process of natural selection and how the fittest are chosen for the reproduction of offsprings for the next generation.

Genetic Algorithms are used to provide quality solutions for optimization problems and search problems. In this article, we would demonstrate the use of the genetic algorithm in searching for some strings.

The genetic algorithms simulate the survival of the fittest amongst individuals of consecutive generations to solving a problem. So before we delve in too deep, let us remind ourselves of some key Charles Darwin principles in the theory of natural selection.

Heredity — There is a process that must take place whereby the children inherit some characteristics from their parents.Variation — There must be diversity in the traits of the population or ways variation or diversity can be introduced into the population.Selection — There has to be a way in the population where parents pass down their genetic characteristics to their children and a way where some do not pass down these genetic characteristics.

How are these principles used in the Genetic Algorithm?

There has to be a population that is maintained in a search space. Like in darwin’s theory, each chromosome (individual comprising of several genes) makes a population which are participants in the quest for the survival of the fittest. In the genetic algorithm, we create a search space (i.e population) with each of the points on the space representing a solution of the search space for a given problem. So in this article, we are trying to search for a string ‘My name is Richard’, hence we create a search space ranging from a to z, A to Z and some symbol. It is essential there is a population in place.

The fitness function determines how fit the ability of an individual in the population is to compete with the other individuals. The chromosomes (individuals) with better fitness scores are given more opportunity to reproduce compared to others with bad fitness scores. It is observed that the chromosomes with better fitness scores produce better offsprings by combining chromosomes of the parents. Since the population size is static, existing chromosomes have to die to create spaces for the new generation. For each generation, the cycle continues and each generation that succeeds the previous generation has better genes hence closer to the solution that the previous generations. When there is no significant difference in the offspring produced between the preceding generation and the succeeding generation then it is said that the algorithm is converged to a set of solutions for the problem.

How does evolution take place from generation to generation in the Genetic Algorithm?

Once the population is initialized, there are various operators that ensure that evolution takes place. The selector operator gives preference to the individual or chromosomes with the highest scores and then allows them to pass their genes to the successive generations. The selector operator basically picks those who are fits for reproduction or mating.After selecting the chromosomes (individual) fit for mating, then the crossover operator then begins to pick pairs and performs the mating process. The genes are crossed over and a new offspring is birthed.

Crossover operation

After a new offspring is birthed, one of the principles of darwin in the theory of natural selection is the importance of variation in the population. Hence it is important to mutate the genes of the new offsprings so as to ensure diversity or variation in the population and also to avoid premature convergence. The mutation operator is, therefore, necessary to ensure the above

Mutation in action

In implementing the genetic algorithm for obtaining a target string starting from a random string, the above discussion about the genetic algorithm is implemented.

A population is initializedThe fitness of the population is calculatedParents are selected from the populationCrossover operator generates a new set of populationA mutation is performed on the new set of populationStep 2 is performed again

Steps 3 to 6 performed over and over until convergence is reached.

It is also noteworthy that the fitness score here is the number of characters that differ from characters in the target string at a particular index. Hence, having a low fitness score is required.

# Python3 program to create target string, starting from# random string using Genetic Algorithmimport random# Number of individuals in each generationPOPULATION_SIZE = 100# Valid genesGENES = '''abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOP QRSTUVWXYZ 1234567890, .-;:_!"#%&/()=?@${[]}'''# Target string to be generatedTARGET = "My name is Richard"class Individual(object): ''' Class representing individual in population '''def __init__(self, chromosome): self.chromosome = chromosome self.fitness = self.cal_fitness()@classmethod def mutated_genes(self): ''' create random genes for mutation ''' global GENES gene = random.choice(GENES) return gene@classmethod def create_gnome(self): ''' create chromosome or string of genes ''' global TARGET gnome_len = len(TARGET) return [self.mutated_genes() for _ in range(gnome_len)]def mate(self, par2): ''' Perform mating and produce new offspring '''# chromosome for offspring child_chromosome = [] for gp1, gp2 in zip(self.chromosome, par2.chromosome):# random probability prob = random.random()# if prob is less than 0.45, insert gene # from parent 1 if prob < 0.45: child_chromosome.append(gp1)# if prob is between 0.45 and 0.90, insert # gene from parent 2 elif prob < 0.90: child_chromosome.append(gp2)# otherwise insert random gene(mutate), # for maintaining diversity else: child_chromosome.append(self.mutated_genes())# create new Individual(offspring) using # generated chromosome for offspring return Individual(child_chromosome)def cal_fitness(self): ''' Calculate fittness score, it is the number of characters in string which differ from target string. ''' global TARGET fitness = 0 for gs, gt in zip(self.chromosome, TARGET): if gs != gt: fitness += 1 return fitness# Driver codedef main(): global POPULATION_SIZE# current generation generation = 1found = False population = []# create initial population for _ in range(POPULATION_SIZE): gnome = Individual.create_gnome() population.append(Individual(gnome))while not found:# sort the population in increasing order of fitness score population = sorted(population, key=lambda x: x.fitness)# if the individual having lowest fitness score ie. # 0 then we know that we have reached to the target # and break the loop if population[0].fitness <= 0: found = True break# Otherwise generate new offsprings for new generation new_generation = []# Perform Elitism, that mean 10% of fittest population # goes to the next generation s = int((10 * POPULATION_SIZE) / 100) new_generation.extend(population[:s])# From 50% of fittest population, Individuals # will mate to produce offspring s = int((90 * POPULATION_SIZE) / 100) for _ in range(s): parent1 = random.choice(population[:50]) parent2 = random.choice(population[:50]) child = parent1.mate(parent2) new_generation.append(child)population = new_generationprint("Generation: {}\tString: {}\tFitness: {}". \ format(generation, "".join(population[0].chromosome), population[0].fitness))generation += 1print("Generation: {}\tString: {}\tFitness: {}". \ format(generation, "".join(population[0].chromosome), population[0].fitness))if __name__ == '__main__': main()

Output

Generation: 1 String: j#uq dMm5 0F latd Fitness: 15Generation: 2 String: ?#/qSduGs eG latd Fitness: 14Generation: 3 String: ?#/qSduGs eG latd Fitness: 14Generation: 4 String: ?#/qSduGs eG latd Fitness: 14Generation: 5 String: 7yycqbe_i5 hd }Std Fitness: 13Generation: 6 String: 7yycqbe_i5 hd }Std Fitness: 13Generation: 7 String: 7yycqbe_i5 hd }Std Fitness: 13Generation: 8 String: Rd uVTcMt} Ri(}atd Fitness: 12Generation: 9 String: ;? ufWdM!s Ri(xaRd Fitness: 11Generation: 10 String: ;? ufWdM!s Ri(xaRd Fitness: 11Generation: 11 String: )0}cX=e is Rirja2d Fitness: 9Generation: 12 String: #? usWe is Ri(4a)d Fitness: 8Generation: 13 String: #? usWe is Ri(4a)d Fitness: 8Generation: 14 String: #? usWe is Ri(4a)d Fitness: 8Generation: 15 String: #? usWe is Ri(4a)d Fitness: 8Generation: 16 String: #? usWe is Ri(4a)d Fitness: 8Generation: 17 String: ;y8n0Ee is RiK}a)d Fitness: 7Generation: 18 String: ;y8n0Ee is RiK}a)d Fitness: 7Generation: 19 String: MB ns4e is R-Kha)d Fitness: 6Generation: 20 String: MB ns4e is R-Kha)d Fitness: 6Generation: 21 String: MB ns4e is R-Kha)d Fitness: 6Generation: 22 String: MB ns4e is R-Kha)d Fitness: 6Generation: 23 String: My nPEe is Jwhard Fitness: 5Generation: 24 String: My nPEe is Jwhard Fitness: 5Generation: 25 String: My nPEe is Jwhard Fitness: 5Generation: 26 String: My nPEe is Jwhard Fitness: 5Generation: 27 String: My n7=e is RLKhard Fitness: 4Generation: 28 String: My n7=e is RLKhard Fitness: 4Generation: 29 String: My nTpe is Rizhard Fitness: 3Generation: 30 String: My nTpe is Rizhard Fitness: 3Generation: 31 String: My nTpe is Rizhard Fitness: 3Generation: 32 String: My nTpe is Rizhard Fitness: 3Generation: 33 String: My nTpe is Rizhard Fitness: 3Generation: 34 String: My nTpe is Rizhard Fitness: 3Generation: 35 String: My nTpe is Rizhard Fitness: 3Generation: 36 String: My nTpe is Rizhard Fitness: 3Generation: 37 String: My nTpe is Rizhard Fitness: 3Generation: 38 String: My nTpe is Rizhard Fitness: 3Generation: 39 String: My nTpe is Rizhard Fitness: 3Generation: 40 String: My nTpe is Rizhard Fitness: 3Generation: 41 String: My nTpe is Rizhard Fitness: 3Generation: 42 String: My nTpe is Rizhard Fitness: 3Generation: 43 String: My nTpe is Rizhard Fitness: 3Generation: 44 String: My nTpe is Rizhard Fitness: 3Generation: 45 String: My n7#e is Richard Fitness: 2Generation: 46 String: My n7#e is Richard Fitness: 2Generation: 47 String: My n7#e is Richard Fitness: 2Generation: 48 String: My n7#e is Richard Fitness: 2Generation: 49 String: My n7#e is Richard Fitness: 2Generation: 50 String: My n7#e is Richard Fitness: 2Generation: 51 String: My n7#e is Richard Fitness: 2Generation: 52 String: My n7#e is Richard Fitness: 2Generation: 53 String: My n7#e is Richard Fitness: 2Generation: 54 String: My n7#e is Richard Fitness: 2Generation: 55 String: My n7#e is Richard Fitness: 2Generation: 56 String: My na#e is Richard Fitness: 1Generation: 57 String: My na#e is Richard Fitness: 1Generation: 58 String: My na#e is Richard Fitness: 1Generation: 59 String: My na#e is Richard Fitness: 1Generation: 60 String: My na#e is Richard Fitness: 1Generation: 61 String: My na#e is Richard Fitness: 1Generation: 62 String: My na#e is Richard Fitness: 1Generation: 63 String: My na#e is Richard Fitness: 1Generation: 64 String: My na#e is Richard Fitness: 1Generation: 65 String: My na#e is Richard Fitness: 1Generation: 66 String: My na#e is Richard Fitness: 1Generation: 67 String: My na#e is Richard Fitness: 1Generation: 68 String: My na#e is Richard Fitness: 1Generation: 69 String: My na#e is Richard Fitness: 1Generation: 70 String: My na#e is Richard Fitness: 1Generation: 71 String: My na#e is Richard Fitness: 1Generation: 72 String: My na#e is Richard Fitness: 1Generation: 73 String: My na#e is Richard Fitness: 1Generation: 74 String: My na#e is Richard Fitness: 1Generation: 75 String: My na#e is Richard Fitness: 1Generation: 76 String: My na#e is Richard Fitness: 1Generation: 77 String: My na#e is Richard Fitness: 1Generation: 78 String: My na#e is Richard Fitness: 1Generation: 79 String: My na#e is Richard Fitness: 1Generation: 80 String: My na#e is Richard Fitness: 1Generation: 81 String: My na#e is Richard Fitness: 1Generation: 82 String: My na#e is Richard Fitness: 1Generation: 83 String: My na#e is Richard Fitness: 1Generation: 84 String: My na#e is Richard Fitness: 1Generation: 85 String: My na#e is Richard Fitness: 1Generation: 86 String: My na#e is Richard Fitness: 1Generation: 87 String: My na#e is Richard Fitness: 1Generation: 88 String: My na#e is Richard Fitness: 1Generation: 89 String: My na#e is Richard Fitness: 1Generation: 90 String: My na#e is Richard Fitness: 1Generation: 91 String: My na#e is Richard Fitness: 1Generation: 92 String: My na#e is Richard Fitness: 1Generation: 93 String: My na#e is Richard Fitness: 1Generation: 94 String: My na#e is Richard Fitness: 1Generation: 95 String: My na#e is Richard Fitness: 1Generation: 96 String: My na#e is Richard Fitness: 1Generation: 97 String: My na#e is Richard Fitness: 1Generation: 98 String: My na#e is Richard Fitness: 1Generation: 99 String: My na#e is Richard Fitness: 1Generation: 100 String: My name is Richard Fitness: 0

From the above, it can be seen that it took up to a hundred generations to be able to match the target string. The whole genetic algorithm process can be observed from the output of the program. It is seen that all the Charles Darwin principle of Natural Selection was obeyed. For further reading check out Genetic Algorithm and Machine Learning for Programmers.

📝 Read this story later in Journal.

👩‍💻 Wake up every Sunday morning to the week’s most noteworthy stories in Tech waiting in your inbox. Read the Noteworthy in Tech newsletter.

Understanding the Genetic Algorithm was originally published in Noteworthy – The Journal Blog on Medium, where people are continuing the conversation by highlighting and responding to this story.

Read more: blog.usejournal.com