genetic algorithm string guess

0
votes

I am trying to understand how to implement a genetic algorithm and wrote a simple string guess. I am having trouble understanding why this solution is not working.

I believe that my problem is in my populating my new generations? The newest generations do not seem to have improved fitness values. I am also not sure if I am doing the crossover and mutation rates correctly. Any help would be really appreciated!

POP_SIZE = 300;
CROSSOVER_RATE = 0.7;
MUTATION_RATE = 0.01
GENESET = " abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!"
target = "Hello World"
RAND_NUM = random.random()

def generateBasePopulation(population_size):
    population = dict()

    for _ in range(POP_SIZE):
        gene = generateParent(len(target))
        population[gene] = 0

    return population


def generateNewPopulation(population, population_size):
    newPopulation = dict()

    while(len(newPopulation) <= POP_SIZE):
        child_one, child_two = crossover(child_one, child_two)
        child_one = mutate(child_one)
        child_two = mutate(child_two)


    newPopulation[child] = 0
    newPopulation[child_two] = 0
    return newPopulation



def assignFitness(population):
    for x in population:
        population[x] = getFitness(x)


def generateParent(length):
    genes = list("")
    for i in range(0,length):
        random_gene = random.choice(GENESET)
        genes.append(random_gene)
    return(''.join(genes))

def getFitness(candidate):
    fitness = 0
    for i in range(0, len(candidate) - 1):
        if target[i] == candidate[i]:
            fitness += 1
    return(fitness)

def mutate(parent):
    gene_index_to_mutate = random.randint(0, len(parent) - 1)
    mutation_value = random.choice(GENESET)
    genes = list(parent)
    genes[gene_index_to_mutate] = mutation_value
    return(''.join(genes))

def crossover(parentA, parentB):
    if(RAND_NUM < CROSSOVER_RATE):
        random_index = random.randint(0, len(target))
        parentASlice = parentA[:random_index]
        parentBSlice = parentB[random_index:]

        return (parentASlice + parentBSlice), (parentBSlice + parentASlice)
    return parentA, parentB


def chooseChild(population):
    fitnessSum = sum(population.values())
    pick = random.uniform(0, fitnessSum)
    current = 0
    for pop in population:
        current += population[pop]
        if current >= pick:
            return pop


def main():
    population = generateBasePopulation(POP_SIZE)

    targetNotFound = True

    while(targetNotFound):
        assignFitness(population)
        if target in population:
            print("target found!")
            targetNotFound = False
        if(targetNotFound):
            tempPopulation = generateNewPopulation(population, POP_SIZE)
            population.clear()
            population = tempPopulation
1
pythonpython-3.xgenetic-algorithmevolutionary-algorithm

1 Answers

1
votes

There are some issues with the generateNewPopulation function.

child_one and child_two are referenced before assignment

You need two individuals from the population to perform the crossover. There are several selection algorithms, but just to give an idea you could start with a form of tournament selection:

def extractFromPopulation(population):
    best = random.choice(list(population.keys()))

    for _ in range(4):
        gene = random.choice(list(population.keys()))
        if population[gene] > population[best]:
            best = gene

    return best

Here the selection pressure (range(4)) is fixed. It's one of the parameters you've to tune in a real case.

Now we have:

def generateNewPopulation(population, population_size):
    newPopulation = dict()

    while len(newPopulation) <= POP_SIZE:
        child_one = extractFromPopulation(population)
        child_two = extractFromPopulation(population)

    # ...

The code still doesn't work because

new individuals aren't inserted in newPopulation

Just indent the two lines:

newPopulation[child] = 0
newPopulation[child_two] = 0

(they must be part of the while loop)

The revised generateNewPopulation function follows:

def generateNewPopulation(population, population_size):
    newPopulation = dict()

    while len(newPopulation) <= POP_SIZE:
        child_one = extractFromPopulation(population)
        child_two = extractFromPopulation(population)

        child_one, child_two = crossover(child_one, child_two)
        child_one = mutate(child_one)
        child_two = mutate(child_two)

        newPopulation[child_one] = 0
        newPopulation[child_two] = 0

    return newPopulation

The crossover function cannot be based on a fixed RAND_NUM value

Delete the RAND_NUM = random.random() assignment and change the crossover function to use a new random value at each call:

def crossover(parentA, parentB):
    if random.random() < CROSSOVER_RATE:
        random_index = random.randint(0, len(target))
        parentASlice = parentA[:random_index]
        parentBSlice = parentB[random_index:]

        return (parentASlice + parentBSlice), (parentBSlice + parentASlice)

    return parentA, parentB

Also the code doesn't correctly perform single point crossover since schemata of the second parent aren't preserved.

You could change many details to improve performance but, as a starting example, it's probably enough as it is (...it works).

Average number of generations to find a solution is about 158 (average on 200 runs).

EDIT (thanks to alexis for the comment)

MUTATION_RATE is unused and a mutation always happens. The mutate function should be something like:

def mutate(parent):
    if random.random() < MUTATION_RATE: 
        gene_index_to_mutate = random.randint(0, len(parent) - 1)
        mutation_value = random.choice(GENESET)
        genes = list(parent)
        genes[gene_index_to_mutate] = mutation_value
        return ''.join(genes)

    return parent

This fix is particularly important if you keep the roulette wheel selection algorithm (chooseChild often doesn't converge without the fix).