Is this code fragment a genetic algorithm?

Question

I am trying to learn genetic algorthms and AI developement and I copied this code from a book, but I don't know if it is a proper genetic algorithm. Here is the code (main.py):

import random

geneSet = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!.,1234567890-_=+!@#$%^&*():'[]\""
target = input()

def generate_parent(length):
    genes = []
    while len(genes) < length:
        sampleSize = min(length - len(genes), len(geneSet))
        genes.extend(random.sample(geneSet, sampleSize))
    parent = ""
    for i in genes:
        parent += i
    return parent

def get_fitness(guess):
    total = 0
    for i in range(len(target)):
        if target[i] == guess[i]:
            total = total + 1
    return total
    """
    return sum(1 for expected, actual in zip(target, guess)
        if expected == actual)
    """

def mutate(parent):
    index = random.randrange(0, len(parent))
    childGenes = list(parent)
    newGene, alternate = random.sample(geneSet, 2)
    if newGene == childGenes[index]:
       childGenes[index] = alternate
    else:
       childGenes[index] = newGene
    child = ""
    for i in childGenes:
        child += i

    return child

random.seed()
bestParent = generate_parent(len(target))
bestFitness = get_fitness(bestParent)
print(bestParent)

while True:
    child = mutate(bestParent)
    childFitness = get_fitness(child)
    if bestFitness >= childFitness:
        continue
    print(str(child) + "\t" + str(get_fitness(child)))
    if childFitness >= len(bestParent):
        break
    bestFitness = childFitness
    bestParent = child

I saw that it has the fitness function and the mutate function, but it doesn't generate a population and I don't understand why. I thaught that a genetic algorithm needs a population generation and a crossover from the best population members to the new generation. Is this a proper genetic algorithm?

Sure it generates a population. I see child = mutate(bestParent) what do you have after you do that a few thousand times? — Octopus
@Octopus: the population is always limited to a parent and a child. So there are no two parents that produce a new child. — Willem Van Onsem

Willem Van Onsem Willem Van Onsem · Accepted Answer · 2017-08-24T22:23:16

Although there are a lot of ambiguous definitions in the field of AI, my understanding is that:

An evolutionary algorithm (AE) is an algorithm that has a (set of) solution(s) and by mutating them somehow (crossover is here also seen as "mutating"), you eventually end up with better solution(s).
A genetic algorithm (GA) supports the concept of a crossover where two or more "solutions" produce new solutions.

But the terms are sometimes mixed. Mind however that crossover is definitely not the only way to produce new individuals (there are more ways than genetic algorithms to produce better solutions), like:

Simulated Annealing (SA);
Tabu Search (TS);
...

But as said earlier there is always a lot of discussion what the terms really mean and most papers on probabilistic combinatorial optimization state clearly what they mean with the terms.

So according to the above definition, your program is an evolutionary algorithm, but not a genetic one: it always has a population of one after each iteration. Furthermore your program only accepts a new child if it is better than its parent making it a Local Search (LS) algorithm. The problem with local search algorithms is that - if the mutation space of some/all solutions is a subset of the solution space - local search algorithms can get stuck forever in a local optimum. Even if that is not the case, they can get stuck in a local optimum for a very long time.

Here that is not a problem since there are no local optima (but this is of course an easy problem). More hard (and interesting) problems usually have (a lot) of local optima.

Local Search is not a bad technique if it collaborates with other techniques that help get the system out of the local optimum again. Other evolutionary techniques such as simulated annealing will accept a worse solution with small probability (depending how much worse the solution is, and how far we are in the evolutionary process).

Is this code fragment a genetic algorithm?

1 Answers