INTRODUCTION
Here are some materials associated with the paper
"Evaluating optimization algorithms: bounds on the
performance of optimizers on unseen problems"
by David Corne and Alan Reynolds
presented at:
GECCO 2011 Workshop on "Scaling Behaviours of Landscapes,
Parameters and Algorithms"
Keep coming back, we will improve what's here over time.
CONTENTS
The files "upper-m5, "upper-m10", etc, ... contain
BOUNDS in relation to the performance of an
optimizer on a set of (unseen) problems as follows:
Suppose you test your optimizer on a set of M problems.
(then you want to look at the file: upper-m)
Now, suppose your optimizer A beats the state of the
art algorithm B on k of these m problems. I.e. it
has a success rate of k/m. You can use the tables
to give you a lower bound on the success rate 'in general',
for a given confidence level.
Say that A beats B on 14 problems from a test suite of
20 problems. And, say you want a lower bound in which
you have 95% confidence. Now, look at upper-m20
(because there were 20 problems), and look at
the row for 6 (A lost to B on 6 problems in the test set),
and you find 0.507 -- let's call it 51%. Now you can
say:
With 95% confidence, A will be beaten by B in up to 51% of
problems from the same distribution as the test set.
Or equivalently:
With 95% confidence, A will beat by B in at least 49% of
problems from the same distribution.
So far the tables give only upper (lower) bounds on the
failure (success) rate. We'll add the lower (upper)
bounds asap.
------------------