A statistical approach for algorithm selection

Authors / Editors

Research Areas

Publication Details

Output type: Other

Author list: Perez J, Pazos RA, Frausto J, Rodriguez G, Romero D, Cruz L, Sosa V, Mutulu M, Sosa V

Publisher: Springer

Publication year: 2004

Volume number: 3059

Start page: 417

End page: 431

Number of pages: 15

ISBN: 3-540-22067-4

ISSN: 0302-9743

Languages: English-Great Britain (EN-GB)

Unpaywall Data

Open access status: closed

Abstract

This paper deals with heuristic algorithm characterization, which is applied to the solution of an NP-hard problem, in order to select the best algorithm for solving a given problem instance. The traditional approach for selecting algorithms compares their performance using an instance set, and concludes that one outperforms the other. Another common approach consists of developing mathematical models to relate performance to problem size. Recent approaches try to incorporate more characteristics. However, they do not identify the characteristics that affect performance in a critical way, and do not incorporate them explicitly in their performance model. In contrast, we propose a systematic procedure to create models that incorporate critical characteristics, aiming at the selection of the best algorithm for solving a given instance. To validate our approach we carried out experiments using an extensive test set. In particular, for the classical bin packing problem, we developed models that incorporate the interrelation among five critical characteristics and the performance of seven heuristic algorithms. As a result of applying our procedure, we obtained a 76% accuracy in the selection of the best algorithm.

Keywords

No matching items found.

Documents