An Efficient Feature Selection Algorithm for Evolving Job Shop Scheduling Rules With Genetic Programming

摘要

Automated design of job shop scheduling rules using genetic programming as a hyper-heuristic is an emerging topic that has become more and more popular in recent years. For evolving dispatching rules, feature selection is an important issue for deciding the terminal set of genetic programming. There can be a large number of features, whose importance/relevance varies from one to another. It has been shown that using a promising feature subset can lead to a significant improvement over using all the features. However, the existing feature selection algorithm for job shop scheduling is too slow and inapplicable in practice. In this paper, we propose the first “practical” feature selection algorithm for job shop scheduling. Our contributions are twofold. First, we develop a Niching-based search framework for extracting a diverse set of good rules. Second, we reduce the complexity of fitness evaluation by using a surrogate model. As a result, the proposed feature selection algorithm is very efficient. The experimental studies show that it takes less than 10% of the training time of the standard genetic programming training process, and can obtain much better feature subsets than the entire feature set. Furthermore, it can find better feature subsets than the best-so-far feature subset.