Correct way of testing machine learning against random data I am using a genetic algorithm to search a very complex hypothesis space. Now I want to estimate how much overfitting I can expect in the final resulting hypothesis. The final model will be used for predicting N output variables from M predictors.
One simple test I can do is to replace the predictors with M random variables and then run the same algorithm and compare the final results. This let's me know how much overfitting I can expect. However because I have multiple input variables (predictors) the quality of the final result might also be influenced by the (unknown) underlying distribution and the (also unknown) covariance of these variables. 
This leads to the question how I could produce a set of random input variables, which have the same distribution and covariance as the variables I am testing against. One simple solution I could come up with, would be, to just "shuffle" the sets of predictors around. I.e. let 
Y_i=(y_{i,1},y_{i,2},...,y_{i,N})

be the variables I want to predict and
X_i=(x_{i,1},x_{i,2},...,x_{i,M})

are the variables I am using for prediction. Then I would use
X'_i=X_j

for a random and unique j for each i and then use the X'_i to determine the Y_i.
Would this work to produce random predictors from the same distribution that can be used for estimating the overfitting? Or are there other effects I need to take into account when doing this kind of test?
 A: First, I would strongly advise against searching a complex hypothesis space using a genetic algorithm; it is a recipe for over-fitting unless you have a lot of data to constrain the model.  Unrestricted optimisation is generally a very bad thing to do in model-fitting, every time you make a choice about your model, or optimise some parameter, you invite over-fitting, so in practice regularisation and model averaging often give better performance.
I think the approach of creating random features is used in feature selection (see the work of Isabel Guyon on this topic); the random features are known as "probes" and if your modelling approach ends up with a large number of probe features in the model that suggests the model will over-fit.  However it is not the case that models with irrelevant features, (including probes) will not have good generalisation performance.  It is often better in terms of predictive performance not to perform any feature selection and use regularisation instead to prevent over-fitting.
Randomly permuting the responses rather than the explanatory variables sounds an interesting idea as it gives a worst-case bound on the amount over-fitting we should expect as it tells us how good your algorithm is at finding patterns in "realistic" data where no genuine pattern actually exists.
