Attempt to understand Genetic algorithm - Guess the password

GeneticAlgo.png

gistfile1.txt

"""
Tut @ https://www.codeproject.com/Articles/1104747/Introduction-to-Genetic-Algorithms-with-Python-Hel

Guess the password
"""
import random
import datetime
import sys
import time

geneSet = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!. '
password = "Jack and jill went up the hill to fetch a pail of water!"


def generate_parent(length):
    """
    a way to generate a random string of letters from the gene set.
    :return:
    """
    gene = []
    while len(gene) < length:
        sample_size = min(length - len(gene), len(geneSet))
        # appends list with values ==> ['X','B'].extend('a','y') -> ['X','B','a','y']
        gene.extend(random.sample(geneSet, sample_size))
    # converts list to str ==> ['a', 'b', ' ', 'C', 'N', 'x'] -> ab CNx
    return ''.join(gene)


def get_fitness(guess):
    """
    fitness value is the total number of letters in the guess that match the letter in the same position of the password
    :param guess:
    :return: number of letters matches
    """
    # The sum() function adds the items of an iterable and returns the sum
    # more @ https://www.programiz.com/python-programming/methods/built-in/sum
    return sum(1 for expected, actual in zip(password, guess) if expected == actual)


def mutate(parent):
    """
    This implementation uses an alternate replacement
    if the randomly selected newGene is the same as the one it is supposed to replace,
    which can save a significant amount of overhead.
    :param parent:
    :return:
    """
    index = random.randrange(0, len(parent))
    child_genes = list(parent)
    new_gene, alternate = random.sample(geneSet, 2)
    child_genes[index] = alternate if new_gene == child_genes[index] else new_gene
    return ''.join(child_genes)


def display(guess):
    """
    just a moniter function
    :param guess:
    :return:
    """
    time_diff = datetime.datetime.now() - startTime
    fitness = get_fitness(guess)
    # print('{0}\t{1}\t{2}'.format(guess, fitness, time_diff))
    time.sleep(.001)
    sys.stdout.write('\rGeneration #' + '\t' + guess)


if __name__ == '__main__':
    random.seed(4)
    startTime = datetime.datetime.now()
    best_parent = generate_parent(len(password))
    best_fitness = get_fitness(best_parent)
    display(best_parent)

    while True:
        child = mutate(best_parent)
        child_fitness = get_fitness(child)
        display(child)
        if best_fitness >= child_fitness:
            continue
        if child_fitness >= len(best_parent):
            break
        best_fitness = child_fitness
        best_parent = child