Python Genetic Algorithms With Artificial Intelligence

In our last Python AI tutorial, we discussed AI Python Logic Programming. Today, we will see AI Python Genetic Algorithms. In this Python Genetic Algorithms tutorial, we will learn the actual meaning of the Genetic Algorithm.

Also, we will look at the benefits, limitations, and applications of Genetic Algorithms with Python. At last, we will see Python Genetic Algorithm example.

So, let’s start the Python Genetic Algorithms tutorial.

Python Genetic Algorithms With AI

What are Genetic Algorithms With Python?

A Genetic Algorithm (GA) is a metaheuristic inspired by natural selection and is a part of the class of Evolutionary Algorithms (EA). We use these to generate high-quality solutions to optimization and search problems, for which, these use bio-inspired operators like mutation, crossover, and selection.

In other words, using these, we hope to achieve optimal or near-optimal solutions to difficult problems. Such algorithms simulate natural selection.

For any problem, we have a pool of possible solutions. These undergo processes like recombination and mutation to bear new children over generations. The search space is the set of all possible solutions and values the inputs may take.

In optimization, we try to find within this search space the point or set of points that gives us the optimal solution. Each individual is like a string of characters/integers/floats and the strings are like chromosomes.

What are Genetic Algorithms With Python

The fitness value (from a fitness function) for a candidate tells us how close it is to the optimal solution.

This is on the lines of Darwin’s theory of ‘Survival of the Fittest’ and is how we keep producing better (evolving) individuals/ solutions over generations before reaching a criterion where to stop. These algorithms work in four steps:

1. Individuals in population compete for resources, mate
2. Fittest individuals mate to create more offsprings than others
3. Fittest parent propagates genes through generation; parents may produce offsprings better than either parent
4. Each successive generation evolves to suit its ambience

Since the population size is constant, some individuals must die to make room for newer ones.

We arrive at a situation of convergence when the difference between offsprings produced by the current and ancestral populations is no longer significant. Then, the algorithm converges to a set of solutions for the problem.

Operators of Python Genetic Algorithms

To evolve through the generations, an algorithm may make use of one of many operators. Some of those are:

Operators in Python Genetic Algorithms

a. Selection Operator

It prefers individuals with better fitness scores and lets them pass genes on to successive generations.

b. Crossover Operator

This lets individuals mate. We apply the selection operator to select two individuals, and randomly choose crossover sites. We then exchange the genes at these sites- this produces an entirely new individual.

Crossover Operator in Python Genetic Algorithms

c. Mutation Operator

In mutation, we insert random genes in offsprings to maintain diversity and avoid premature convergence.

Mutation Operator in Python Genetic Algorithms

Python Genetic Algorithm Example

Let’s try to build a Genetic Algorithm in Python that can play something like Guess the Number better than us humans. This is a game where I randomly select a number between 1 and 10 (both inclusive) and you guess what number I have picked.
Is it 7? No
Is it 3? No
Is it 6? No
Is is 2? Yes

Seems like no big deal, but when we start talking about 100 or 1000 numbers, it quickly becomes a problem. How do we improve our guesses? What can we do but depend on sheer luck? This ultimately turns into a mechanical process. Maybe we could decide if a certain guess is closer to the solution in a certain direction?

Is it 7? Lower
Is it 1? Higher
Is it 5? Lower
Is it 4? Lower
Is it 3? Yes
Possession of such domain knowledge means we can get to the solution faster. To make informed and improved guesses, the algorithms make use of random exploration of the problem space.

Along with that, they also use evolutionary processes like mutation and crossover (see above). Without experience in the problem domain, they also try out things humans never would dare attempt.

Okay, now let’s try implementing this in Python. Bear in mind that the fitness value for a candidate is how close it is to the optimal. Here, it means how many letters match what it should be- “Hello World!”. Let’s start with building a gene set.

>>> geneSet="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!."
>>> target="Hello World!"

Now, let’s generate a guess.

>>> import random
>>> def gen_parent(length):
       genes=[]
       while len(genes)<length:
               sampleSize=min(length-len(genes),len(geneSet))
               genes.extend(random.sample(geneSet,sampleSize))
       return ''.join(genes)

Here, random.sample() chooses sampleSize random elements from geneSet. Now, let’s do something to calculate the fitness value.

>>> def get_fitness(guess):
      return sum(1 for expected,actual in zip(target,guess) if expected==actual)

With zip(), we can iterate over two lists at once. Now, let’s perform mutation.

>>> def mutate(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)

This is to convert the parent into an array with list(parent). Then, we replace 1 letter with one that we randomly select from geneSet. Finally, we recombine the result into a string with .join().

To avoid wasted guesses, this uses an alternate replacement if the randomly selected newGene is equal to that we expect it to replace. The next function lets us display what is happening.

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

We’re all set. Let’s begin with the main program now.

>>> random.seed()
>>> startTime=datetime.datetime.now()
>>> bestParent=gen_parent(len(target))
>>> bestFitness=get_fitness(bestParent)
>>> display(bestParent)

umaBL.WdlUYj 1 0:00:51.469944
And now, a loop to generate a guess, request its fitness, compare that to that of the previous best guess, and keep the guess with the better fitness.

>>> while True:
      child=mutate(bestParent)
      childFitness=get_fitness(child)
      if bestFitness>=childFitness:
               continue
      display(child)
      if childFitness>=len(bestParent):
               break
      bestFitness=childFitness
      bestParent=child

umaBL.WolUYj 2 0:00:55.974065

umaBL.WollYj 3 0:00:56.032069
umaBL.WollY! 4 0:00:56.044069
umlBL.WollY! 5 0:00:56.061070
HmlBL.WollY! 6 0:00:56.078071
HelBL.WollY! 7 0:00:56.086072
HellL.WollY! 8 0:00:56.095072
HellL.WorlY! 9 0:00:56.105073
Hello.WorlY! 10 0:00:56.112073
Hello.World! 11 0:00:56.127074
Did you see how the fitness gradually developed?

Benefits of Python Genetic Algorithms

Genetic Algorithms in Python observe the following advantages:

• No need for derivative information
• Faster and more efficient than traditional methods
• Good parallel capabilities
• Deliver a list of good solutions instead of just one
• Optimize continuous as well as discrete functions and multi-objective problems
• Always deliver a solution and improves that with time
• Useful for very large search spaces with many parameters involved

Limitations of Python Genetic Algorithms

With all those benefits, we also have certain limitations in Genetic Algorithms with Python-

• Not suitable for simple problems with available derivative information
• Stochastic; no guarantee of the result solution being optimal
• Frequent calculation of fitness value is computationally expensive for some problems
• No guarantee of convergence to the optimal solution if not implemented properly

Applications of Python Genetic Algorithms

Finally, let’s talk about where we typically use such Genetic Algorithms with Python.

• Recurrent Neural Network
• Mutation testing
• Code breaking
• Filtering and signal processing
• Learning fuzzy rule base

So, this was all in Python Genetic Algorithms. Hope you like our explanation.

Conclusion 

Today, we learned about Python Genetic Algorithms and their operators- selection, crossover, and mutation. We talked about the fitness function and took an example problem to demonstrate such Genetic Algorithms Python.

Finally, we learned of benefits, limitations, and applications of Python Genetic Algorithms. Still, if you have any doubt, feel free to ask in the comment tab.