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 = - startTime
    fitness = get_fitness(guess)
    print("{0}\t{1}\t{2}".format(guess, fitness, str(timeDiff)))

startTime =
bestParent = generate_parent(len(target))
bestFitness = get_fitness(bestParent)

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

Tuzla 2020, Field day

I published on my YouTube channel a video about the ham radio Field Day event at Tuzla, Romania, 2020.

KiCad Templates for Orange Pi Zero

KiCad templates for two different hat models for Orange Pi Zero boards can be downloaded from my GitHub repo. Two different KiCad templates can be downloaded in the same GitHub archive: one uncut, 46×48 mm exactly same size as Orange Pi Zero; the other one has some cuts for network and USB connector, to accomodate […]

Leave a Reply

Your email address will not be published. Required fields are marked *