Feature Selection for 50+ features StackExchange newcomer here...I am looking for some advice on feature selection packages in R.  Specifically, I am in search of functions that can identify the best features, out of 500+ features, within a data set that is 500 or less observations.  Most of what I have tried to date (i.e. Regsubsets, Genetic Algorithm, etc.) does not provide results in less than 24 hours.  I need the function(s) to be efficient enough that it can be run on a desktop and produce results in a timely manner.  Lastly, I need the function to find the best combination of features from a linear regression perspective (similar to Regsubsets).
Ideally, the "winner" would be able to do all that I have mentioned above on a standard desktop/laptop in these time frames:


*

*50 or less features < 1 minute

*250 features < 3 minutes

*1000 features < 10 minutes


Fyi...I am mostly concerned with data sets that have linear relationships between features.  By "best" I am referring to highest Adjusted R2 and lowest RMSE.
 A: As a partial answer (see my comment as well), I would say that there is no solution that gives the absolute best (defined in whatever way you choose - $R^2$, adjusted $R^2$ or whatever). This is so because there are too many possible models. Even if we don't consider interactions, 500 variables means there are $2^{500} \approx 3*10^{150}$ possible models. If each model took 1/1000 of second to run, it would take longer than the lifetime of the universe to consider them all.
People have considered the question of variable selection a lot. There are many proposed solutions. Personally, I have my doubts about any analysis that is done via a purely automatic method - whatever it is. This would be so, even if N was very large. You should be using substantive expertise. 
You note that you have only N = 500.  Then one common rule of thumb would limit you to no more than 50 IVs.  Putting that as a limit on regsubsets would speed things up - have you done that?
Another solution is to use LASSO. This doesn't solve all the problems posed by automatic methods, but it does work fast and it does adjust the coefficients to account for model complexity.
