Meta-Learning for Selecting Meta-heuristics Based on Iterated Local Search to Solve Permutation Flow-Shop Problem

Abstract

In the realm of intelligent systems, addressing the NP-hard Permutation Flow-Shop (PFS) problem presents a notable challenge, especially with burgeoning complexities in manufacturing systems. Conventional wisdom relies on metaheuristic techniques to tackle such intricacies, yet the best metaheuristic remains elusive. This paper introduces a new meta-learning framework that leverages pre-trained metaheuristics rooted in Iterated Local Search (ILS) to forecast the most effective metaheuristic for each PFS instance. Notably, our approach pioneers the extraction of novel meta-features from graph representations, discerning the best metaheuristics in 99.7% of cases using a small set of meta-features and baseline classifiers, such as decision trees and support vector machines. Moreover, the interpretability of our meta-model unveils insights into feature impact, showcasing the efficacy of abstract graph computations, such as centrality and connectivity, over bespoke meta-features related to problem size.