Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

genetic algorithm
optimization

What is a genetic algorithm?

Sami Muzzamil

Overview

Genetic algorithm (GA) is the name given to the new (rather exotic) class of optimization techniques which were discovered by John Holland in the late 70s.

GAs are similar to conventional evolutionary algorithms. GAs are not concerned with how to solve particular problems, but rather the speed of problem-solving. One of the major contributions of genetic algorithms is the “evolutionary optimization” of problems.

Note: GA is a class of search algorithms that uses a probabilistic approach to find a solution to a problem.

When it comes to the structure of the algorithm, it is divided into the following five phases: initial population, fitness function, selection, crossover, and mutation.

Genetic Algorithm workflow

Let’s try out a very basic example where the initial population is random characters. The algorithm will regenerate the required solution.

Note: Enter your name as an example.

geneSet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!,. ?"
import random
import datetime
def Calculate_Fitness(guess):
    return sum(1 for expected,actual in zip(target,guess) if expected==actual)

def Cross_Over(length):
    genes=[]
    while len(genes)<length:
        sampleSize=min(length-len(genes),len(geneSet))
        genes.extend(random.sample(geneSet,sampleSize))
    return "".join(genes)

def Mutation(parent):
    index=random.randrange(0,len(parent))
    childGenes=list(parent)
    newGene,alternate=random.sample(geneSet,2)
    childGenes[index]=alternate if newGene==childGenes[index] else newGene
    return "".join(childGenes)

def Display(guess, startTime):
    timeDiff=datetime.datetime.now()-startTime
    fitness=Calculate_Fitness(guess)
    print("{}\t{}\t{}".format(guess,fitness,timeDiff))

def run_genetic_algo(target):   
    random.seed()
    startTime=datetime.datetime.now()
    bestParent=Cross_Over(len(target))
    bestFitness=Calculate_Fitness(bestParent)
    Display(bestParent, startTime)
    while True:
        child=Mutation(bestParent)
        childFitness=Calculate_Fitness(child)
        if bestFitness>=childFitness:
            continue
        Display(child, startTime)
        if childFitness>=len(bestParent):
            break
            exit(0)
        bestFitness=childFitness
        bestParent=child
target = input()
run_genetic_algo(target)

Enter the input below

Test the genetic algorithm by entering your name

Code explanation

  • Lines 4–5: We are iterating over both the given target and the population in Calculate_Fitness function. We’ll return 1 when the expected and actual values are equal to one another.

  • Lines 7–12: We are taking a genes list and continue iterating, in the Cross_Over function, until the length of the genes array is greater than the given parameter length. Inside the loop, we first calculate the sampleSize and then extract a sampleSize random sample from the geneSet and add that to the genes array.

  • Lines 14–19: We are creating the Mutation function, where we first use the randrange function to calculate a random index. Next, we extract two random samples from the geneSet and store them in the variables newGene and alternate. After this, we check and see if the newGene is equal to the value of the childGenes present at the specific index. If it is, we store the value of alternate inside childGenes at that specific index. Otherwise, we store newGene.

  • Lines 21–24: We use the Display function for showing the value of the chromosome along with its fitness.

  • Lines 26–42: We are creating the run_genetic_algo function, which takes a target, which will be your name in this case. After this, we set a seed so that we generate the same random fitness values.

  • Line 29: We are calling the Cross_Over function, which generates a new offspring.

  • Line 30: We are calling the Calculate_Fitness function defined above to calculate the bestFitness value. We display the value of the chromosome along with its fitness.

  • We call the Mutation function to get a population of genetic diversified chromosomes, inside the while loop. Next, we call the Calculate_Fitness function, this time on the mutated chromosome. We then compare the fitness values of the old chromosome and the mutated chromosome. We also have set up a condition, which checks if the fitness of the mutated chromosome is greater than the length of our old chromosome. If this happens, we simply exit the loop and stop the process.

  • Lines 41–42: We are replacing the chromosome with the mutated chromosome along with its fitness value, if neither of our terminating conditions is met.

  • This entire process continues until either of the terminating conditions is met.

RELATED TAGS

genetic algorithm
optimization

CONTRIBUTOR

Sami Muzzamil
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring