Stochastic local search and parameters recommendation: a case study on flowshop problems

The Algorithm Selection Problem (ASP) considers the use of previous knowledge regarding problem features and algorithm performance to recommend the best strategy to solve a previously unseen problem. In the application context, the usual ASP for optimization considers recommending the best heuristics, whenever it faces a new similar problem instance, also known as the Per-Instance ASP. Although ASP for heuristic recommendation is not new, selecting heuristics and also their parameters, or the Per-instance Algorithm Configuration Problem, is still considered a challenging task. This paper investigates the use of meta-learning to recommend six different stochastic local searches and their parameters to solve several instances of permutation flowshop problems. The proposed approach uses several problem features, including fitness landscape metrics, builds the performance database using irace, and trains different multi-label recommendation models on a data set with more than 6000 flowshop problem instances. Experiments show that decision tree-based machine learning models achieve good performance, and the quality of the recommendations is capable of outperforming the state-of-the-art algorithm with tuned configuration.

Automated summary

This paper investigates the use of meta-learning to recommend different stochastic local searches and their parameters to solve permutation flowshop problems. The proposed approach builds a performance database and trains multiple recommendation models to achieve good performance and quality of recommendations. Experiments show that this method outperforms the state-of-the-art algorithm with tuned configuration.