Skip to Main content Skip to Navigation
Conference papers

Algorithm selection of anytime algorithms

Abstract : Anytime algorithms for optimization problems are of particular interest since they allow to trade off execution time with result quality. However, the selection of the best anytime algorithm for a given problem instance has been focused on a particular budget for execution time or particular target result quality. Moreover, it is often assumed that these anytime preferences are known when developing or training the algorithm selection methodology. In this work, we study the algorithm selection problem in a context where the decision maker's anytime preferences are defined by a general utility function, and only known at the time of selection. To this end, we first examine how to measure the performance of an anytime algorithm with respect to this utility function. Then, we discuss approaches for the development of selection methodologies that receive a utility function as an argument at the time of selection. Then, to illustrate one of the discussed approaches, we present a preliminary study on the selection between an exact and a heuristic algorithm for a bi-objective knapsack problem. The results show that the proposed methodology has an accuracy greater than 96% in the selected scenarios, but we identify room for improvement.
Document type :
Conference papers
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download

https://hal.inria.fr/hal-02898962
Contributor : Alexandre D. Jesus <>
Submitted on : Monday, July 27, 2020 - 1:38:41 PM
Last modification on : Monday, May 17, 2021 - 12:00:05 PM
Long-term archiving on: : Tuesday, December 1, 2020 - 7:26:21 AM

File

main.pdf
Files produced by the author(s)

Identifiers

Citation

Alexandre Borges de Jesus, Arnaud Liefooghe, Bilel Derbel, Luis Paquete. Algorithm selection of anytime algorithms. GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation Conference, Jul 2020, Cancún, Mexico. pp.850-858, ⟨10.1145/3377930.3390185⟩. ⟨hal-02898962⟩

Share

Metrics

Record views

137

Files downloads

504