Test Driven Development for Stochastic algorithms?

Question

this is similar, but no the same as this post, which was the closest question I could find on this. I don't even see that answer as satisfactory for the question asked in that thread let alone TDD. If I'm writing my tests before I write my actual code, how am I supposed to come up with "special" cases if I can't even run my code yet?

I was thinking about this for the domain of things like Neural networks and Genetic programming; While I can mostly avoid unit tests on stochastic aspects of NN's, Genetic Programming is a whole different beast. Selection, recombination, mutation and pairing algorithms should all have certain statistical characteristics to be "correct" in the context of my program. Note this is not a case of "testing non units" because if my program does not have the right statistical properties at each of these levels, I have a bug even though my program may look like it works fine. How do I even test any Evolutionary Algorithm or algorithm with similar stochastic requirements?

EDIT: for some reason the question suggester wasn't working properly, but I just found this in the side bar. The top answer talks about Mocks, but how would that work in a genetic programming environment, where the distributions themselves need to be tested?

Answer 1

Honestly, I don't think true TDD is a good fit for heavily stochastic programs. Really honestly, I don't think it's a good idea for much of anything, but putting that aside, you're going to make life harder than it needs to be trying to do GP where you have to fail tests before you allow yourself to write any code.

There are a few ways to do good unit testing though. Some things are obvious types of tests you could write for any program. I won't spend any effort on that.

One of the specific tricks I'll use for randomized algorithms is figure out what distribution I expect my outputs to have, and then I'll write a test that runs the thing a bunch of times and checks to see that the distribution of results is pretty close to what I expected. These aren't real unit tests in the way you learn about them. My test will fail sometimes just because unlikely events can happen. What I'm looking for is confidence, not certainty. If my test fails, I'll look at the actual results. Do they look like they might have been legitimately drawn from the tail of my distribution or not? Maybe I'll run the suite a few more times to see if things fall back in line.

You can also of course just fix the seed of your RNG, but this makes your tests really brittle, as if you change some aspect of an algorithm to require an additional sample from the generator, everything after that changes. For that reason, it's best used for testing very low-level aspects of an algorithm where the amount of code involved is pretty small.

Mostly though, what I've done in the past is to not worry too much about test coverage as a metric. I use high-level tests like the statistical ones mentioned earlier, and debug the lower levels however I can. Sometimes, I can figure out a way to write a good test. Other times, I do what I did in grad school a few times trying to debug new stochastic optimization algorithms: instrument the crap out of the algorithm with print statements, print out 50 pages of output, tape it to the floor in the lab, and crawl around with a printed copy of the source code going, "OK, it should have generated a random number here, and if the number was less than 0.3, it should have done blah blah...ok, it actually generated 0.46721, so let's see, it should have done this instead...ok, looks like that worked fine." And I do that until I'm convinced my algorithm is doing what I wanted it to do.

Answer 2

TDD gets you thinking about what needs to be made and how you can test it. It's a pain in the ass when you realize the design has to change mid development and now all your tests need adjustment.

For genetic algorithms, there's PLENTY that needs to be made before a single bit of entropy enters into play. You need to generate agents. You want to test that you don't generate a billion agents or zero agents. You need to give them DNA. Let's say it's a path-finding domain and their DNA consists of [N,S,E,W]. You want to test to make sure their DNA never contains anything other than those 4 choices. You need to find out when an agent successfully navigates the path/maze/goal/whatnot. You want to test that the program stops processing it after it gets to the goal. Writing the tests first makes you think about these things and give you a nice list of tasks to do.

The inherently chaotic nature of genetic algorithms comes into play when you want your framework to successfully deal with all the crazy stuff the little agents will try to do. You write what tests you can think of, but you can bet your ass you're going to come back and write more tests once the agents try something you hadn't thought of. Like... walking off the edge of the map.

Start with writing the tests. That's TDD. But you don't stop writing tests, and realize there's going to be a chunk of time in the middle where you respond to your agents breaking your system. And remember you're not trying to test the emergent behavior of your genetic algorithms. Detecting end-conditions should be a part of your genetic algorithm package, testing that it successfully detects what it's supposed to find is the goal of test.

For stochastic algorithms in general, you try and test the entire search-space of possible output it could produce, and mock the rand() function so you can walk it across the entire search space. If the search space is broad, don't pretend you're going to catch everything.