• English
    • français
  • Help
  •  | 
  • Contact
  •  | 
  • About
  •  | 
  • Login
  • HAL portal
  •  | 
  • Pages Pro
  • EN
  •  / 
  • FR
View Item 
  •   LillOA Home
  • Liste des unités
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
  • View Item
  •   LillOA Home
  • Liste des unités
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

A model of anytime algorithm performance ...
  • BibTeX
  • CSV
  • Excel
  • RIS

Document type :
Article dans une revue scientifique
DOI :
10.1007/s10898-020-00909-9
Title :
A model of anytime algorithm performance for bi-objective optimization
Author(s) :
Borges De Jesus, Alexandre [Auteur]
Optimisation de grande taille et calcul large échelle [BONUS]
Paquete, Luis [Auteur]
Liefooghe, Arnaud [Auteur] refId
Optimisation de grande taille et calcul large échelle [BONUS]
Japanese French Laboratory for Informatics [JFLI]
Journal title :
Journal of Global Optimization
Pages :
329-350
Publisher :
Springer Verlag
Publication date :
2021
ISSN :
0925-5001
English keyword(s) :
Multi-objective optimization
Combinatorial optimization
Anytime algorithms
Anytime behavior
ε-constraint
HAL domain(s) :
Informatique [cs]
English abstract : [en]
Anytime algorithms allow a practitioner to trade-off runtime for solution quality. This is of particular interest in multi-objective combinatorial optimization since it can be infeasible to identify all efficient solutions ...
Show more >
Anytime algorithms allow a practitioner to trade-off runtime for solution quality. This is of particular interest in multi-objective combinatorial optimization since it can be infeasible to identify all efficient solutions in a reasonable amount of time. We present a theoretical model that, under some mild assumptions, characterizes the “optimal” trade-off between runtime and solution quality, measured in terms of relative hypervolume, of anytime algorithms for bi-objective optimization. In particular, we assume that efficient solutions are collected sequentially such that the collected solution at each iteration maximizes the hypervolume indicator, and that the non-dominated set can be well approximated by a quadrant of a superellipse. We validate our model against an “optimal” model that has complete knowledge of the non-dominated set. The empirical results suggest that our theoretical model approximates the behavior of this optimal model quite well. We also analyze the anytime behavior of an ε-constraint algorithm, and show that our model can be used to guide the algorithm and improve its anytime behavior.Show less >
Language :
Anglais
Peer reviewed article :
Oui
Audience :
Internationale
Popular science :
Non
Collections :
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Source :
Harvested from HAL
Files
Thumbnail
  • https://hal.inria.fr/hal-02898963/document
  • Open access
  • Access the document
Thumbnail
  • https://hal.inria.fr/hal-02898963/document
  • Open access
  • Access the document
Université de Lille

Mentions légales
Université de Lille © 2017