unit testing with uncertainty

[martinus]

Hi all, I am writing an particle swarm optimizer that tries to find
good floating point values for optimization problems. I have several
test cases, and some target fitness value that the optimizer should be
able to reach. The problem is that since such optimizers make lots of
use of random numbers, so the optimizer can only find in about 90% of
the cases the target fitness value. I can relax the target fitness
value, than 95% of the runs are ok; but that is not really a solution.

Any ideas how to write tests when you have such an uncertainty about
the result?

Martin

 

[Farrel Lifson]

Hi all, I am writing an particle swarm optimizer that tries to find
good floating point values for optimization problems. I have several
test cases, and some target fitness value that the optimizer should be
able to reach. The problem is that since such optimizers make lots of
use of random numbers, so the optimizer can only find in about 90% of
the cases the target fitness value. I can relax the target fitness
value, than 95% of the runs are ok; but that is not really a solution.

Any ideas how to write tests when you have such an uncertainty about
the result?

Martin

Could you make use of assert_in_delta? It's in Test::Unit. You can
either check that each attempt is within a certain tolerance, or you
can run a number of attempts and check that the number of successfult
ones falls within the threshold.

Farrel

 

[Mike Woodhouse]

Hi all, I am writing an particle swarm optimizer that tries to find
good floating point values for optimization problems. I have several
test cases, and some target fitness value that the optimizer should be
able to reach. The problem is that since such optimizers make lots of
use of random numbers, so the optimizer can only find in about 90% of
the cases the target fitness value. I can relax the target fitness
value, than 95% of the runs are ok; but that is not really a solution.

Any ideas how to write tests when you have such an uncertainty about
the result?

Martin

You can use a predetermined random number sequence (or sequences) for
unit testing, where I'd suggest you ought to be working in a fairly
black and white world. Establishing expected results if the number of
drawing from the RNG is large doesn't look like a fun job. Could you
use mock objects to provide predetermined results at a higher level?

I don't see that your problem really falls into the unit test category
though, it looks more like a user, performance or acceptance test
issue, since you'll pretty much have to perform multiple runs to
establish the success rate, and the program hitting or missing the 90%
criterion is still not going to tell you definitively if it's working.
It's as much a benchmarking deal as a testing one.

--Mike

 

[martinus]

You can use a predetermined random number sequence (or sequences) for

unit testing, where I'd suggest you ought to be working in a fairly
black and white world. Establishing expected results if the number of
drawing from the RNG is large doesn't look like a fun job. Could you
use mock objects to provide predetermined results at a higher level?

If I used a predetermined random number I cannot make much changes in
the optimization algorithm, e.g. if I optimize it and it needs less
random numbers the result cannot be the same.

I don't see that your problem really falls into the unit test category
though, it looks more like a user, performance or acceptance test
issue, since you'll pretty much have to perform multiple runs to
establish the success rate, and the program hitting or missing the 90%
criterion is still not going to tell you definitively if it's working.
It's as much a benchmarking deal as a testing one.

That's very true, it is an acceptance test. Nevertheless I would love
to have
an automated test for it, I need some way to automatically find out
regressions.

After some googling I think I should have a close look how statistics
deal with this kind of problem:
http://en.wikipedia.org/wiki/Confidence_interval#Practical_example


Martin