Genetic algorithm mutation coded in Python

This example is adapted from Clinton Sheppard’s excellent book “Genetic Algorithms with Python“, a book that I encourage you to buy and read. The very simple example shows how easy is to design in Python a simple mutation algorithm that merges to the optimal solution in 24 iterations.

The example below uses romanian language accents and a small proposition for the purposes of the exercise

The result is:

# coding: utf8
geneSet = " aâăbcdefghiîjklmnopqrsștțuvwxyzAĂÂBCDEFGHIÎJKLMNOPQRSȘTȚUVWXYZ!0123456789."
target = "Cătălin e un tip mișto !"
# Generate a guess
'''Random.sample takes sampleSize values from the input without replacement.
This means there will be no duplicates in the generated parent unless
geneSet contains duplicates, or length is greater than len(geneSet).
The implementation above can generate a long string with
a small set of genes and uses as many unique genes as possible.'''

import random
import datetime


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

# fitness
'''The fitness value the genetic algorithm provides is the only feedback
the engine gets to guide it toward a solution. In this project
the fitness value is the total number of letters in the guess
that match the letter in the same position of the password.'''

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

# mutate
'''Next, the engine needs a way to produce a new guess by mutating the current one.
The following implementation converts the parent string to an array with list(parent),
then replaces 1 letter in the array with a randomly selected one from geneSet,
and finally recombines the result into a string with ''.join(childGenes).
This implementation uses an alternate replacement if the randomly selected newGene
is the same as the one it is supposed to replace, which can prevent
a significant number of wasted guesses.'''

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)

# display
'''Next, it is important to monitor what is happening so that the engine can be stopped
if it gets stuck. Having a visual representation of the gene sequence,
which may not be the literal gene sequence, is often critical to identifying
what works and what does not so that the algorithm can be improved.
Normally the display function also outputs the fitness value and how much time has elapsed.'''

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

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

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