some mutation consideration

[rengel8]

I'm coming back to pyGAD after some time of absence and based on a distinct use case I think to have seen something that I recognized earlier. It is how fast the best solution converges to a known set of values.

Generation : 995
Fitness    : 0.999987994
Solution   : [30, 10, 10, 80, 90, 91]
TARGET     : [30, 10, 10, 80, 90, 90]

Generation : 996
Fitness    : 1.0
Solution   : [30, 10, 10, 80, 90, 90]
TARGET     : [30, 10, 10, 80, 90, 90]

So it does find the result, but given the initial speed by random probing and after that the long phase of close to no advance I thought about a custom mutation function (one of the features of pyGAD), but maybe this is also more generally interesting also for others.

In my case I defined a fixed gene space with all possible image coordinates as integer values like:

gene_spac = [{'low': 0, 'high': 99},                # x1
             {'low': 0, 'high': 99},                # y1
             
             {'low': 0, 'high': 99},                # x2
             {'low': 0, 'high': 99},                # y2
             
             {'low': 0, 'high': 99},                # x3
             {'low': 0, 'high': 99}]                # y3

gene_dtype = [int, int, int, int, int, int] 

So there are 100^6 (1000000000000) possible solutions in total and I think that the randomness to find new values is sometimes rounded to 0 (is this true?), or the wrong gene is slightly changed (adaptively), so that the GA has hard times to finish the run quicker.

My idea would be right now to write a mutation function in which new solutions are created by something like a gene step shifting. In my example I have 6 genes, so I would create up to 12 new solutions, where the gene values (lastly only one at a time) is modified to the next higher and also to the next lower value possible by the gene_spac - definition above.
Since one of these solutions will return with a higher fitness value, this procedure seems to be interesting for predefined gene spaces.

Would it be possible to do something like this i.e. if there was no fitness advance for 5 generations or so?
I mean the benefint of the randomness of pyGAD is to quickly get samples, which helps converging. This will be much better escpecially in the beginning, but at least in my example I wouldn't know a better way to enhance this process further, when it already is rather close.

Any thoughts on this are much appreciated..

[ahmedfgad]

Thanks, @rengel8 for your suggestion.

If you have 100^6 (1000000000000) solutions, then the speed of progression depends on some factors. Some of these factors include the number of solutions, number of genes, and whether elitism or parents are kept. This may get the probability of finding new solutions higher.

It is definitely interesting. So, you would like to do mutation in circular queue (similar to how round robin scheduling works to assign tasks to CPU). We can create:

1. Forward circular mutation.
2. Backward circular mutation.

It will not be a problem to get them supported as independent mutation operators.

It would be a good idea to change the mutation operators at the middle. For now, you can do experiments on whether changing the type of mutation/crossover would help to make faster progress.

Here is the on_generation() callback function which changes the crossover type to two_points_crossover after 20 generations. It also changes the mutation type if the current best fitness is identical to the fitness found 5 generations in the past.

def on_generation(ga_instance):
    print("Generation" + str(ga_instance.generations_completed))

    best_fitness = ga_instance.best_solution(pop_fitness=ga_instance.last_generation_fitness)[1]

    last_5_generation_idx = ga_instance.generations_completed - 5

    if last_5_generation_idx >= 0:
        last_5_generation_fitness = ga_instance.best_solutions_fitness[last_5_generation_idx]
        if (last_5_generation_fitness - best_fitness) == 0:
            ga_instance.mutation = ga_instance.scramble_mutation

    if ga_instance.generations_completed == 20:
        ga_instance.crossover = ga_instance.two_points_crossover

[rengel8]

Thank you Ahmed for your exhaustive reply on this. Maybe one issue is also that random (here randint) might not create a different gene during mutation at all in some cases, due to rounding to integer?) and/or changes genes that were already "fine".

I used adaptive mutation to reduce the randomness for higher fitness-values, but one solution right now would only be to give it more generations and patience so far. So I will try you suggestion soon and report back.

What I also do is keeping the results for executed solutions to save a lot of time, which is a great feature for calculating more intense fitness evaluations.