Comparing two genetic algorithms 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.
 A: 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.
A: 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: 


*

*What constitues similarity for you, ie what do you mean when you say you don't believe the two methods are different?

*How do you quantify it - can be answered after 1, and 

*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).
