How should I Test a Genetic Algorithm
genetic-algorithm, language-agnostic, non-deterministic, unit-testing
Solution
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.
Problem
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: 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. Use a known list of numbers. Similar to the above but I could follow the code through by hand (which would be very tedious). 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. 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.