10
$\begingroup$

I have two implementations of a genetic algorithm which are supposed to behave equivalently. However due to technical restrictions which cannot be resolved their output is not exactly the same, given the same input.

Still I'd like to show that there is no significant performance difference.

I have 20 runs with the same configuration for each of the two algorithms, using different initial random number seeds. For each run and generation the minimum error fitness of the best individual in the population was recorded. The algorithm employs an elite-preserving mechanism, so the fitness of the best individual is monotonically decreasing. A run consists of 1000 generations, so I have 1000 values per run. I cannot get more data, as the calculations are very expensive.

Which test should I employ? An easy way would probably be to only compare the error in the final generations (again, which test would I use here)? But one might also think about comparing the convergence behaviour in general.

Improve this question
$\endgroup$
3
  • $\begingroup$ Just as a clarification: isn't it the case that a genetic algorithm searches randomly for a solution, so that the initial segment of any run is unlikely to produce any worthwhile solution? Also, what exactly do you mean by "the minimum error in the population"? If you mean the minimum difference between a known true value and any solution out of the 1000 values in a run, then isn't that a biased indication of the run's result? After all, in practice you would accept the final solution in each run and reject everything that precedes it, right? $\endgroup$
    – whuber ♦
    Aug 18, 2010 at 14:57
  • $\begingroup$ By error I basically mean 1/fitness, so I'm talking about the value of the best individual in a generation. I've recorded the fitness value of the best individual for every generation. So I have 1000*20*2 numbers, each corresponding to the "fitness" of the best individual in a particular generation of a particular run. $\endgroup$
    – nisc
    Aug 18, 2010 at 15:12
  • $\begingroup$ I guess the initial question was ill-posed, I've added some clarifications .. $\endgroup$
    – nisc
    Aug 18, 2010 at 15:23

2 Answers 2

Reset to default
9
$\begingroup$

Testing stochastic algorithms can be rather tricky!

I work in systems biology and there are many stochastic simulators available to use to simulate a model. Testing these simulators is tricky since any two realizations from a single model will be typically different.

In the dsmts we have calculated (analytically) the expected value and variance of a particular model. We then perform a hypothesis test to determine if a simulator differs from the truth. Section 3 of the userguide gives the details. Essentially we do a t-test for the mean values and a chi-squared test for variances.

In your case, you are comparing two simulators so you should just use a two-sampled t-test instead.

Improve this answer
$\endgroup$
5
  • $\begingroup$ How would I go about using the information from all generations? $\endgroup$
    – nisc
    Aug 18, 2010 at 10:37
  • $\begingroup$ The easiest way is to do multiple tests, i.e. test at every generation, then use a Bonferroni or fdr correction. $\endgroup$
    – csgillespie
    Aug 18, 2010 at 10:43
  • $\begingroup$ When comparing at every generation, I would have to test at a significance level of 1/1000 * 0.05 ? Isn't that a bit harsh? $\endgroup$
    – nisc
    Aug 18, 2010 at 11:18
  • $\begingroup$ True, but you're also doing lots of testing - can't have everything ;) You could rank the p-values, use them as a guide to see where possible errors may occur. $\endgroup$
    – csgillespie
    Aug 18, 2010 at 12:26
  • 1
    $\begingroup$ Instead of bonferroni correction, you could always use the more powerful bonferroni holm. See my anyswer here: stats.stackexchange.com/questions/575/… $\endgroup$
    – Henrik
    Aug 18, 2010 at 16:19
4
$\begingroup$

Maybe you could measure the average difference between two runs of the same algorithm to the average difference between two runs from different algorithms. Doesn't solve the problem of how to measure that difference, but might be a more tractable problem. And the individual values of the time series would feed into the difference calculation instead of having to be treated as individual datapoints to be evaluated against each other (I also don't think that the particular difference at the nth step is what you really want to make statements about).

Update Concerning details - well which features of the time series are you interested in, beyond the final error? I guess you actually got three different questions to solve:

  1. What constitues similarity for you, ie what do you mean when you say you don't believe the two methods are different?
  2. How do you quantify it - can be answered after 1, and
  3. How can you test for significant differences between your two methods?

All I was saying in the first post was that the answer to (1) probably doesn't consider the individual differences at each of the 1000 generations. And that I'd advise coming up with a scalar value for either each time series or at least similarity between time series. Only then you get to the actual statistics question (which I know least about of all three points, but I was advised to use a paired t-test in a similar question I just asked, when having a scalar value per element).

Improve this answer
$\endgroup$
1
  • $\begingroup$ sounds reasonable, any more details? $\endgroup$
    – nisc
    Aug 18, 2010 at 12:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.