9
$\begingroup$

How can one select the proper number of parameters for a genetic algorithm to model a given system?

For example, say you want to optimize production of cars, and you have 1,000 measurements of hourly efficiency at various tasks for each of 1,000 different employees. So, you have 1,000,000 data points. Most of these are likely to be weakly correlated to the overall efficiency of your factory, but not so weakly that you can say they are irrelevant with statistical confidence. How do you go about picking inputs for your GA so that you don't have 1,000,000+ degrees of freedom, resulting in very slow convergence or no convergence at all?

Specifically, what are the algorithms one could use to pre-select or selectively eliminate features?

One approach I have used myself in this scenario is to evolve the parameter selection itself, so I might have parents like {a,b,c}, {b,d,e,q,x,y,z}, and so on. I would then mutate the children to add or drop features. This works well for a few dozen features. But the problem is that it is inefficient if there is a large number of degrees of freedom. In that case, you are looking at 10^n combinations (in the example above, 10^1,000,000), which makes some pre-filtering of features critical to get any kind of useful performance.

$\endgroup$

migrated from ai.stackexchange.com Feb 24 '14 at 18:15

This question came from our site for people interested in conceptual questions about life and challenges in a world where "cognitive" functions can be mimicked in purely digital environment.

11
$\begingroup$

First of all - the example doesn't seem well suited because you would probably use some regression or classical ML methods to solve this. Secondly - you are referring to a general problem of feature selection (Kira, Rendell, 1992) or attribute selection (Hall, Holmes, 2003) or variable selection (Guyon, Elisseeff, 2003) or variable subset selection (Stecking, Schebesch, 2005) or feature extraction (Hillion, Masson, Roux, 1988) or dimensionality reduction (Roweis, Saul, 200) or state abstraction (Amarel, 1968). This problem is relevant not only to genetic algorithms but for almost all machine learning techniques when dealing with high dimensional data.

Three cases can be distinguished here: the last instance of this problem known as state abstraction is usually related to process modelling (which suits your example, but not the GA context). The first three, i.e. feature selection, attribute selection or variable selection seem to be most relevant when taking your question literally. In this context a common solution is the mRMR approach (Peng, Long, Ding, 2005). From my experience it doesn't always work well with continuous data - however, mutual information can be substituted with other coefficients, like correlation for example. Another possible approach is to use cross-validation (Picard, Cook, 1984) for this. You can have multiple models each using different features, and by means of model selection with cross-validation techniques you choose the best model, which gives you the information on which features work best for the given task.

The feature extraction and dimensionality reduction cases allow to not only select initial features, but also their combinations. A well known example solution for this case is the PCA algorithm (Pearson, 1901), which produces the optimal, in terms of explained variance, set of features being linear combinations of input features.

Also note, that there are many models that handle feature extraction task by themselves. Some examples are: Growing Neural Gas Network (Fritzke, 1995), LASSO (Tibshirani, 2011), RFE SVM (Zeng, Chen, Tao, 2009), Decision Trees (Quinlan, 1986).

References:

$\endgroup$
3
$\begingroup$

I have never done this before, and obviously don't have access to said data, but a potentially good way to do this would be through clustering. For each employee, we have an n-dimensional vector, where each dimension cooresponds to a different task. Then, we can use clustering to group "similar" employees together; however, this is going to be solely dependent on your data, ie it's quite possible that given only 1000 employees that clustering will yield groups of employees that aren't really all that related, and so while we may get a reduction in population, it may be at the expense of information loss.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.