4.7 Article

Instance Space Analysis for Algorithm Testing: Methodology and Software Tools

Journal

ACM COMPUTING SURVEYS
Volume 55, Issue 12, Pages -

Publisher

ASSOC COMPUTING MACHINERY
DOI: 10.1145/3572895

Keywords

Algorithm footprints; algorithm selection; benchmarking; MATLAB; metalearning; meta-heuristics; software as a service; test instance diversity; timetabling

Ask authors/readers for more resources

Instance Space Analysis (ISA) is a methodology developed to support objective testing of algorithms and assess the diversity of test instances. It enables visualization of the entire space of possible test instances and provides insights into how algorithm performance is affected by instance properties. This article serves as a comprehensive tutorial on the ISA methodology, including details of algorithms and software tools. A case study on university timetabling is presented to illustrate the methodology and tools.
Instance Space Analysis (ISA) is a recently developed methodology to (a) support objective testing of algorithms and (b) assess the diversity of test instances. Representing test instances as feature vectors, the ISA methodology extends Rice's 1976 Algorithm Selection Problem framework to enable visualization of the entire space of possible test instances, and gain insights into how algorithm performance is affected by instance properties. Rather than reporting algorithm performance on average across a chosen set of test problems, as is standard practice, the ISA methodology offers a more nuanced understanding of the unique strengths and weaknesses of algorithms across different regions of the instance space that may otherwise be hidden on average. It also facilitates objective assessment of any bias in the chosen test instances and provides guidance about the adequacy of benchmark test suites. This article is a comprehensive tutorial on the ISA methodology that has been evolving over several years, and includes details of all algorithms and software tools that are enabling its worldwide adoption in many disciplines. A case study comparing algorithms for university timetabling is presented to illustrate the methodology and tools.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.7
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available