Poor randomization in the Genetic Algorithm Framework

Question

Has anyone seen convincing results from the .Net Genetic Algorithm Framework?

I am seeing poor randomization in the Traveling Salesman Problem demo provided with the Genetic Algorithm Framework. The following call generates the same gene shuffle order across the x 100 seed chromosome population:

chromosome.Genes.ShuffleFast();

If I single step through the code the gene order looks randomized hence I suspect there is a time/Rdn() bug in ShuffleFast() or else I am overlooking a setup step.

I have tried to work around the problem by preshuffling the chromosome gene sequences and this produced a minor change in the TSP results. However the console log of the run still shows the GAF discovering only 4 potential solutions across 400 population generations. This is at odds with GA YouTube videos showing genetic algorithm implementations homing in on a suggested solution with a lot of jitter. I cite this as a further indication that the GAF has a systemic internal problem with random number generation.

The Genetic Algorithm Framework is very well documented via the authors Blog, so I am trying to keep an open mind as the reason.

Steps to reproduce = Download GAF from nuget, compile & debug the default project with a breakpoint after the create chromosomes for-loop, inspect population.Solutions. Windows 7, VS2015, .Net 4.5 & 4.61. Debug or Release.

Notum

Can you post more of the code to show the context of this call. There can be issues with random number generators if they're not initialised properly. – Nussbaum

@Nussbaum The inner workings of the ShuffleFast() routine are within the GAF library which I think is closed source. The author of the library would need to respond, he is active on SO. Until then I will look for another GA library. The ShuffleFast() call is made 100 times in a tight loop on a list of 16 integers, if I manually break and F10 within that loop the Shuffle results look random. – Notum

"The ShuffleFast() call is made 100 times in a tight loop on a list of 16 integers," - That's probably the cause of the problem. It looks like the random number generator is being initialised each iteration of the loop. Stepping in the debugger slows it down enough to give you random results. You need to initialise the generator once outside the loop. – Nussbaum

Note that basic GA:s are not really the best approach for solving the TSP. Just a simple ant system (AS) implementation usually outperforms GA for TSP:s even if including, in the latter, problem-specifically tested mutation rates / advanced cross-over schemes to keep the permutation encoding intact. Probably, for the youtube videos you've seen, the chromosomes have been initialized with good heuristic solutions as well as showing the final results after problem-specific parameter tunings. – Saltatory

Answer 1

Looking at the code in a disassembler, there are two versions of ShuffleFast defined as extension methods: one takes a Random object as a parameter and the other creates a new one using the default constructor and uses that. They are otherwise identical, doing a standard Fisher–Yates shuffle.

So you need to construct your own Random and then pass it in:

Random r = new Random();
...
chromosome.Genes.ShuffleFast(r);
otherChromosome.Genes.ShuffleFast(r);
...

This way you've got only one stream of random numbers, and that stream is seeded based on the current time whenever you run your program.

Heptamerous

I followed your advice using the ShuffleFast(Random r) overload with r declared outside the chromosome population loop. Now the seed population has random gene sequences. The test output still looks odd with just a few city tour distance changes across 400 generations. My next step will be to port the GAF test data across to an alternative GA .Net framework to see if the algorithm homes in progressively on a best answer. I will mark your reply as the accepted answer if the author of the GAF does not offer a deeper description of the runtime test results. – Notum

Answer 2

Sorry for the late response to the question. The issue is indeed with the GAF. The Shuffle method uses a System.Random number generator and creates a new one each time the method is called. This causes issues due to seeding. I have fixed this (tonight) in the GAF and this will be in the next release. I suggest that the following code is used as a workaround.

var rnd = GAF.Threading.RandomProvider.GetThreadRandom ();
myList.ShuffleFast (rnd);

Each random number generator created using the above code creates a random number generator with a singe seed per thread. This can then be passed to the Shuffle() method as described by Matthew.

Washcloth