Sunday, July 31, 2011

Genetic Algorithm - Part 10 - Algorithm Correctness

How do you know that the genetic algorithm one has coded is correct. It is possible that the algorithm is arriving at a solution, but how one verifies that the algorithm is correct.

I have been rewriting the solution in C#, I have already created the basic structure for genetic algorithm using multithreading. Since I already had a SQL implementation of the same, I was importing the generated DNAs for a generation in C# and applying the fitness function on it in C#.
So the next step was to complete the full algorithm in C#. I coded the complete algorithm and ran it but the solution was not converging. The fitness score increased to 460 (maximum being 500 which is a solution) and it started coming down. I obviously cannot debug a genetic algorithm as I usually debug the code. I looked at the code for a couple of days but couldn't find the problem. So I need to try another way.

I already have a SQL version of the solution, so I exported the set of DNAs for the generation where the fitness score started coming down into SQL server. I realized that the DNAs in that generation had different parents which is incorrect. This was causing the solution not to converge.

I looked at the code and found that the multiple threads which were creating the DNAs for a generation, finds the DNAs with the best fitness score from each of its set of DNAs. Now in the common list used by main thread, the parents were getting overwritten which was causing the issue.

One criteria for the algorithm correctness is that the fitness score should always increase as the generations progress, that is by definition of evolution. And it is evolution what we are using in the algorithm.

So far i have successfully implemented a multi-threading solution for the problem. The next step is to have more realistic conditions in the algorithm which I will describe in the next post.

No comments:

Post a Comment