CODEWITHSUNDEEP
c#genetic-algorithmgenetic-programming
camelCase
camelCase

Reputation: 1780

Poor randomization in the Genetic Algorithm Framework

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.

Upvotes: 6

Views: 723

Answers (2)

John Newcombe
John Newcombe

Reputation: 384

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.

Upvotes: 3

Matthew Strawbridge
Matthew Strawbridge

Reputation: 20620

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.

Upvotes: 3

Related Questions