Gradually increase the probability of mutation

Question

I am implementing something very similar to a Genetic Algorithm. So you go through multiple generations of a population - at the end of a generation you create a new population in three different ways 'randomly', 'mutation' and 'crossover'.

Currently the probabilities are static but I need to make it so that the probability of mutation gradually increases. I appreciate any direction as I'm a little stuck..

This is what I have:

int random = generator.nextInt(10);
if (random < 1)  
    randomlyCreate() 
else if (random > 1 && random < 9 )
    crossover(); 
else  
    mutate();

Thank you.

Answer 1

In your if statement, replace the hard coded numbers with variables and update them at the start of each generation.

Your if statement effectively divides the interval 0 to 10 into three bins. The probability of calling mutate() vs crossover() vs randomlyCreate() depends on the size of each bin. You can adjust the mutation rate by gradually moving the boundaries of the bins.

In your code, mutate() is called 20% of the time, (when random = 9 or 1), randomlyCreate() is called 10% of the time (when random = 0) and crossover() is called the other 70% of the time.

The code below starts out with these same ratios at generation 0, but the mutation rate increases by 1% each generation. So for generation 1 the mutation rate is 21%, for generation 2 it is 22%, and so on. randomlyCreate() is called 1 / 7 as often as crossover(), regardless of the mutation rate.

You could make the increase in mutation rate quadratic, exponential, or whatever form you choose by altering getMutationBoundary().

I've used floats in the code below. Doubles would work just as well.

If the mutation rate is what you're most interested in, it might be more intuitive to move the mutation bin so that it's at [0, 2] initially, and then increase its upper boundary from there (2.1, 2.2, etc). Then you can read off the mutation rate easily, (21%, 22%, etc).

void mainLoop() {
    // make lots of generations
    for (int generation = 0; generation < MAX_GEN; generation++) {
        float mutationBoundary = getMutationBoundary(generation);   
        float creationBoundary = getCreationBoundary(mutationBoundary);
        createNewGeneration(mutationBoundary, creationBoundary);
        // Do some stuff with this generation, e.g. measure fitness
    }
}

void createNewGeneration(float mutationBoundary, float creationBoundary) {
    // create each member of this generation
    for (int i = 0; i < MAX_POP; i++) {
        createNewMember(mutationBoundary, creationBoundary);
    }
}

void createNewMember(float mutationBoundary, float creationBoundary) {
    float random = 10 * generator.nextFloat();

    if (random > mutationBoundary) {
        mutate();
    }
    else {
        if (random < creationBoundary) {
            randomlyCreate();
        }
        else {
            crossover();
        }
    }
}

float getMutationBoundary(int generation) {
    // Mutation bin is is initially between [8, 10].
    // Lower bound slides down linearly, so it becomes [7.9, 10], [7.8, 10], etc.
    // Subtracting 0.1 each generation makes the bin grow in size.
    // Initially the bin is 10 - 8 = 2.0 units wide, then 10 - 7.9 = 2.1 units wide,
    // and so on. So the probability of mutation grows from 2 / 10 = 20%
    // to 2.1 / 10 = 21% and so on.
    float boundary = 8 - 0.1f * generation;

    if (boundary < 0) {
        boundary = 0;
    }
    return boundary;    
}

float getCreationBoundary(float creationBoundary) {
    return creationBoundary / 8; // fixed ratio
}