Alex Rivera | Logout

How should I Test a Genetic Algorithm

Asked 2009-06-24T15:26:08.577
54

I have made a quite few genetic algorithms; they work (they find a reasonable solution quickly). But I have now discovered TDD. Is there a way to write a genetic algorithm (which relies heavily on random numbers) in a TDD way?

To pose the question more generally, How do you test a non-deterministic method/function. Here is what I have thought of:

  1. Use a specific seed. Which wont help if I make a mistake in the code in the first place but will help finding bugs when refactoring.

  2. Use a known list of numbers. Similar to the above but I could follow the code through by hand (which would be very tedious).

  3. Use a constant number. At least I know what to expect. It would be good to ensure that a dice always reads 6 when RandomFloat(0,1) always returns 1.

  4. Try to move as much of the non-deterministic code out of the GA as possible. which seems silly as that is the core of it's purpose.

Links to very good books on testing would be appreciated too.

unit-testing language-agnostic genetic-algorithm non-deterministic
Edit
Report

2 Answers

2

One way I do for unit testing of non-deterministic functions of GA algorithms is put the election of random numbers in a different function of the logic one that uses that random numbers.

For example, if you have a function that takes a gene (vector of something) and takes two random points of the gene to do something with them (mutation or whatever), you can put the generation of the random numbers in a function, and then pass them along with the gene to another function that contains the logic given that numbers.

This way you can do TDD with the logic function and pass it certain genes and certain numbers, knowing exactly what the logic should do on the gene given that numbers and being able to write asserts on the modified gene.

Another way, to test with the generation of random numbers is externalizing that generation to another class, that could be accessed via a context or loaded from a config value, and using a different one for test executions. There would be two implementations of that class, one for production that generates actual random numbers, and another for testing, that would have ways to accept the numbers that later it will generate. Then in the test you could provide that certain numbers that the class will supply to the tested code.

answered 2012-12-23T14:18:15.353
1

Well the most testable part is the fitness function - where all your logic will be. this can be in some cases quite complex (you might be running all sorts of simulations based on input parameters) so you wanna be sure all that stuff works with a whole lot of unit tests, and this work can follow whatever methodology.

With regards to testing the GA parameters (mutation rate, cross-over strategy, whatever) if you're implementing that stuff yourself you can certainly test it (you can again have unit tests around mutation logic etc.) but you won't be able to test the 'fine-tuning' of the GA.

In other words, you won't be able to test if GA actually performs other than by the goodness of the solutions found.

answered 2011-07-05T10:49:44.170

Your Answer