1. Algorithm selection of anytime algorithms
- Author
-
Luís Paquete, Alexandre D. Jesus, Bilel Derbel, Arnaud Liefooghe, Optimisation de grande taille et calcul large échelle (BONUS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Centre for Informatics and Systems (CISUC), Departamento de Engenharia Informática / Department of Informatics Engineering (DEI), University of Coimbra [Portugal] (UC)-Universidade de Coimbra [Coimbra]-University of Coimbra [Portugal] (UC)-Universidade de Coimbra [Coimbra], Japanese French Laboratory for Informatics (JFLI), and National Institute of Informatics (NII)-The University of Tokyo (UTokyo)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)
- Subjects
Optimization problem ,Computer science ,Heuristic (computer science) ,media_common.quotation_subject ,Algorithm Selection ,Context (language use) ,0102 computer and information sciences ,02 engineering and technology ,Function (mathematics) ,01 natural sciences ,Measure (mathematics) ,Anytime Algorithms ,010201 computation theory & mathematics ,Knapsack problem ,Anytime Performance ,Anytime algorithm ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Quality (business) ,[INFO]Computer Science [cs] ,Algorithm ,Selection (genetic algorithm) ,media_common - Abstract
International audience; 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.
- Published
- 2020
- Full Text
- View/download PDF