A Machine Learning Approach for Modeling Algorithm Performance Predictors

摘要

This paper deals with heuristic algorithm selection, which can be stated as follows: given a set of solved instances of a NP-hard problem, for a new instance to predict which algorithm solves it better. For this problem, there are two main selection approaches. The first one consists of developing functions to relate performance to problem size. In the second more characteristics are incorporated, however they are not defined formally, neither systematically. In contrast, we propose a methodology to model algorithm performance predictors that incorporate critical characteristics. The relationship among performance and characteristics is learned from historical data using machine learning techniques. To validate our approach we carried out experiments using an extensive test set. In particular, for the classical bin packing problem, we developed predictors that incorporate the interrelation among five critical characteristics and the performance of seven heuristic algorithms. We obtained an accuracy of 81% in the selection of the best algorithm.