How to compare stochastic algorithms, before and after modification I would appreciate suggestions on how I could make some specific statistical claims about the efficacy of changes to an algorithm. My statistics background is pretty minimal (I'm working on it).
I would like to compare two versions of the same basic algorithm, however, one has been tweaked (hopefully improved). These are stochastic, population based optimization algorithms, think Genetic Algorithm, or Particle Swarm Optimization.
For instance, my results may look like this (the specific values, functions may vary of course):
benchmark fn     Before        After
dampened_sine    -0.597       -0.721        
fn1              69.308     -132.688    
fn3           -8457.388    -9000.000    
fn4              -0.394       -0.463        
fn5               0.153       -0.217        
haupt_fn1         9.627        1.000        
haupt_fn2         5.291        0.000        

Any claims I would be making would be specific to the benchmark functions used. I was thinking of using a paired t-test (before and after the change of the algorithm), but I am not sure if that's the correct approach.
I would run each algorithm on each benchmark function N ( > 30?) times for a fixed number of generations and use the mean of these runs as a result to compare. The populations are generated with random values, I could use the same initial seed for each algorithm, but I am assuming that running each algorithm N times with different random seeds would put them more or less on equal footing.
My goal is to write this up in a paper, and be able to state that any observed changes for this specific set of benchmark functions wasn't just due to luck or randomness (given the stochastic nature of these algorithms) but is statistically significant. I am looking for some guidance on how to do this.
I hope the above is clear, I'd be happy to clarify/reword if it would be helpful.
 A: A fair number of papers still simply report the means and variances, bold the lower number in each column, and call it a day, so it's nice to see you're trying to get it right.
Generally, I avoid parametric tests like the t-test, because I'm never 100% confident I'm getting all the assumptions right. Kruskal-Wallis is popular in the literature as a non-parametric test (or Mann-Whitney if you only have two populations you're comparing).
I think those would be good places to start, and then you can branch out if it seems you need something else.
A: I am dealing with similar question as you are. Since you are testing the same algorithm with different parameter's configurations (might be even considered as tunning) I believe that data you generate should be considered dependent (paired). Maybe I'm wrong. 
Anyway, I distinguish two tests: (1) when comparing performance of the algorithm (or whatever else) on the same instance, (2) when comparing performance on the set of more instances. In the first case (1) the set of data is generated by running the algorithms multiple times. We have to do that, because different seeds are changing the final result. Here I use ANOVA with repeated measures when the data is not heavily skewed (ezANOVA in R). When comparing on different sets of instances, (case 2), usually Friedman's test (blocking for instance) is used. This is similar to repeated measures ANOVA however no need for data to be normally distributed.
Permutation test become more popular for the stochastic algorithms. Bootstrapping as well. Both are covered by the R libraries, so no worries there. Didn't use them much so can't provide more details about it.
