0
$\begingroup$

(My statistics knowledge comes mainly from computer science, so I might be overthinking the following...)

I have implementations of several stochastic optimization algorithms (evolutionary algorithms, to be specific), and some unit tests for them, each one using fixed parameters on some known problems. These tests should ensure that the algorithms do indeed find an optimal solution reasonably well -- so they don't measure performance, but convergence to a known solution (a sanity check for the overall implementation). This is to make sure that when I change the implementation, no errors are introduced.

Now, there's some inconvenience: since I didn't spend too much time on parameter tuning, the unit tests sometimes don't converge (in the sense that the best found solution is not within some reasonable distance from the known optimum).

My intent is to improve this simple strategy to something more statistically sound. Assume just one unit test, with fixed parameters, known optimum $x^*$, and a distance function $d$. Independent test runs have independent outcomes $X_i \sim D$. We can introduce $S_i = d(X_i, x^*) < c \sim \mathrm{Bernoulli}(p)$, with $p$ the "test convergence rate", and $c$ a fixed cutoff for when we accept a solution "good enough".

Ideas:

  • Is one result reasonably close to the optimum? This is the current situation. I just take one sample $s_1$. If $s_1 = \mathtt{true}$, the test succeeds.

    The problem here is that the cutoff $c$ is too arbitrary. Larger $c$ makes the test fail less often, but decreases the strength of the assertion. Also, convergernce might just appear by accident (while actually being unlikely).

  • Is the fraction of converging runs reasonable? Generalization of the above: estimating the true $p$ once by a large number of runs, then for the unit testing, take a (small) number of samples $s_1, \ldots, s_n$, and do a statistical test whether $p$ equals $\hat{p}$ estimated from those.

    This has the disadvantage that the true $p$ might of course change if I change the implementation, and the cutoff is still arbitrary.

    Alternatively, one could just estimate $\hat{p}$ and test whether it is "reasonably large" (ie., close to one). This avoids having to know the true $p$, but I wouldn't know how to test "reasonably large".

  • Do the results lie within a reasonable distance from the optimum? Taking a sample $x_1, \ldots, x_n$, and using them to test whether the expected distance from the optimum is zero.

    But what test to use? $D$ is unknown, and totally skewed ($X_i$ can never be above $x^*$, since that is the optimum).

I'd say that the third option is the best (but of course, it occured to me only during the writing of this question :)). So the questions are:

  • Is the third option really good, and if yes, what test to use? Does the second one make any sense?
  • Any other, better options? Something more Bayesian, perhaps?
  • Is there any information or literature on this kind of testing? I would think that it is related to cross-validation, although here, we're interested in the actual result and variance, but the hypothesis whether the algorithm works correctly.
$\endgroup$
2
  • $\begingroup$ This is way too broad a question. $\endgroup$ – user2974951 Jan 15 '19 at 12:24
  • $\begingroup$ Really? I tried it to make it as specific as possible, instead of just asking "how to test GAs"... What exactly is too broad? $\endgroup$ – phipsgabler Jan 15 '19 at 12:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.