How should I Test a Genetic Algorithm

Question

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.

Answer 1

Seems to me that the only way to test its consistent logic is to apply consistent input, ... or treat each iteration as a single automaton whose state is tested before and after that iteration, turning the overall nondeterministic system into testable components based on deterministic iteration values.

For variations/breeding/attribute inheritance in iterations, test those values on the boundaries of each iteration and test the global output of all iterations based on known input/output from successful iteration-subtests ...

Because the algorithm is iterative you can use induction in your testing to ensure it works for 1 iteration, n+1 iterations to prove it will produce correct results (regardless of data determinism) for a given input range/domain and the constraints on possible values in the input.

Edit I found this strategies for testing nondeterministic systems which might provide some insight. It might be helpful for statistical analysis of live results once the TDD/development process proves the logic is sound.

Answer 2

I would test random functions by testing them a number of times and analyzing whether the distribution of return values meets the statistical expectations (this involves some statistical knowledge).