Moving from cowboy coding to agile development

Monday, April 24, 2006

Abusing TDD genetically

I recently made a small program as an example of a genetic algorithm. It was a minor school assignment, so the algorithm type to use was set in advance. Trying to use TDD as much as I can nowadays, I once again started writing code tests first.

After learning about how tests should drive design earlier, I now faced another interesting situation. Part of the design (the algorithm type bit) was already set, so the tests should actually adapt to that. I thought about how I should write tests in a case like this, and decided to experiment a little. Instead of writing tests for existing code (that didn't actually exist yet, but was quite thoroughly planned and only waited to be written), I tried to come up with tests that could have forced me to choose the algorithm I had already thought about. I know this was not anything like the approach TDD is meant to motivate, but it was fun - and writing unit tests still really paid off.

I managed to write tests that drove me towards the algorithm I had already partly designed and made the original design, in a sense, justified. Writing really demanding tests also made me improve the original design by showing that some details in the algorithm worked only occasionally as I had meant them to work. "Occasionally" is an important thing here, since genetic algorithms form a partly random approach to finding solutions in large search spaces.

Next I will present some examples of how unit testing helped me while writing a simple genetic algorithm. If you're not familiar with the concept, you might want to quickly browse Wikipedia's article on the subject. If you want to skip that, let's just say the algorithm is all about evolution (of solutions to the problem) and leave it at that. :)

Uncle Bob's blog post Extract Class provided me with a good way to test randomness. For example, I implemented the mutation of individuals so that the likelihood of mutation depended on the fitness of the individual: a perfect individual should never mutate, a strong individual should mutate only with a small likelihood, and a very poor individual should almost always mutate. So, I wrote tests for each case, writing a loop in which I called the mutation control method and counting the number of times a mutation actually happened.

public void testStrongIndividualVeryUnlikelyMutates() {
Individual original = new Individual("88888");
Individual after;
int changeCount = 0;
for(int i=0; i<1000; i++) {
after = new Individual("88888");
if(!original.equals(after)) {
assertTrue((changeCount < 250) && (changeCount > 50));

One of the things unit tests helped me improve was generating offspring for two parent individuals. Since I didn't want the individuals to produce exact copies of themselves (since that would not give me any new information), I wrote a test that ensured the offspring was different from both parents. I was surprised to see the test fail with randomly generated individuals, since I thought a good selection of the crossover point alone would solve this. I soon realised that if the parents had identical "DNAs" on one side of the crossover point (e.g. "123|456" and "888|456"), the offspring would be an exact copy of one the parents. This was really easy to solve by forcing the offspring to mutate at birth, but I might not have found the flaw without a good test.

All in all, the task was fun and educating, although my approach probably added a (big) twist of solid coding horror to TDD.

No comments: