Recommending Meta-Heuristics and Configurations for the Flowshop Problem via Meta-Learning: Analysis and Design

摘要

This work proposes a meta-learning system based on Gradient Boosting Machines to recommend local search heuristics for solving flowshop problems. The investigated approach can decide if a metaheuristic (MH) is suitable for each instance. It can also provide well-suited parameters for each recommended MH using data from Irace parameter tuning. This paper considers four MHs (Hill Climbing, Tabu Search, Simulated Annealing, and Iterated Local Search) as candidates to solve several flowshop instances. In the experiments, 540 flowshop problems (with different sizes, variants, and objectives) and 50 instances for each problem are considered, resulting in a total of 27,000 instances being addressed. We use simple low-level meta-features in the meta-learning system like the number of jobs and machines, processing time distribution, flowshop variant, objective, and evaluations budget. Besides testing the recommendations in terms of accuracy and Kappa (for MH and categorical parameters), RMSE and R2 (for numerical parameters), we also explore the importance of each meta-feature in MH recommendation models. Moreover, we perform a multiple correspondence analysis on MH configurations to gain further insights into the parameters values. Results show that the proposed approach is promising, particularly for MH recommendation.