Algorithm Instance Footprint: Separating Easily Solvable and Challenging Problem Instances - Sorbonne Université Access content directly
Conference Papers Year : 2023

Algorithm Instance Footprint: Separating Easily Solvable and Challenging Problem Instances

Ana Nikolikj
Sašo Džeroski
Mario Andrés Muñoz
Carola Doerr
Peter Korošec
Tome Eftimov

Abstract

In black-box optimization, it is essential to understand why an algorithm instance works on a set of problem instances while failing on others and provide explanations of its behavior. We propose a methodology for formulating an algorithm instance footprint that consists of a set of problem instances that are easy to be solved and a set of problem instances that are difficult to be solved, for an algorithm instance. This behavior of the algorithm instance is further linked to the landscape properties of the problem instances to provide explanations of which properties make some problem instances easy or challenging. The proposed methodology uses meta-representations that embed the landscape properties of the problem instances and the performance of the algorithm into the same vector space. These meta-representations are obtained by training a supervised machine learning regression model for algorithm performance prediction and applying model explainability techniques to assess the importance of the landscape features to the performance predictions. Next, deterministic clustering of the meta-representations demonstrates that using them captures algorithm performance across the space and detects regions of poor and good algorithm performance, together with an explanation of which landscape properties are leading to it.
Fichier principal
Vignette du fichier
GECCO_2023_Footprints_HAL.pdf (1.91 Mo) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-04180584 , version 1 (12-08-2023)

Identifiers

Cite

Ana Nikolikj, Sašo Džeroski, Mario Andrés Muñoz, Carola Doerr, Peter Korošec, et al.. Algorithm Instance Footprint: Separating Easily Solvable and Challenging Problem Instances. GECCO '23: Genetic and Evolutionary Computation Conference, Jul 2023, Lisbon, Portugal. pp.529-537, ⟨10.1145/3583131.3590424⟩. ⟨hal-04180584⟩
16 View
3 Download

Altmetric

Share

Gmail Facebook X LinkedIn More