Assessing model performance of stochastic algorithm I'm looking at how I currently evaluate my classification models and wondering if it could be improved. I've got a stochastic algorithm (Genetic Programming), which for non-classification problems is run ~50 times on each problem to get an overview for how it performs. 
Currently I'm implementing repeated 10-fold stratified cross-validation. For standard deterministic modeling techniques this assesses the algorithm over various splits of the data. With my GP classifiers I have an additional source of variability alongside variability due to how the dataset was split; as the RNG seed for each run will be different. 
Is repeated 10-fold cross-validation a useful measure of my model's performance or would it be better to use a different technique such as bootstrapping and run this multiple times? An alternative approach would be to use repeated CV with 50 repeats, but make each repeat use the same folds. Therefore I've got the CV reducing variance due to the splitting of the data folds, and the 50 repeats minimising variation from the stochastic model. However this would be very computationally expensive!
 A: I'd recommend to measure both ways.
As you say, you have two sources of variation/instabity here:


*

*variability due to different initializtion and

*instability wrt. the training cases


The usual way of repeating cross validation with new splits will measure the both sources of variance together. But of course it is of high practical importance to know whether you'd need to get more cases or a more stable algorithm in order to improve your classification. This means that you should actually measure the variance for constant training set with new seeds as well. 
I'd start with a moderate size (10 * 5 fold * 10 repeated executions maybe) for the computations and then have a look whether variance due to GP seed is in the same order of magnitude as the variance due to training set composition. It may very well be that one source of variance is >> the other. You could then either save a lot of computations by showing that the smaller source of variance is negligible, or concentrate your work to improve the classifier onto the important source of variation.
Once you know what is going and and are satisfied with the total set-up you can spend the time on a larger calculation with more repetitions.

At least for the data I work with, there is no practical difference between out-of-bootstrap and repeated CV (given the same number of surrogate models is evaluated). 
