Titre :

A model of anytime algorithm performance for bi-objective optimization

Auteur(s) :

Borges De Jesus, Alexandre [Auteur]
Centre for Informatics and Systems [CISUC]
Optimisation de grande taille et calcul large échelle [BONUS]
Paquete, Luis [Auteur]
Centre for Informatics and Systems [CISUC]
Liefooghe, Arnaud [Auteur]
Japanese French Laboratory for Informatics [JFLI]
Optimisation de grande taille et calcul large échelle [BONUS]

Titre de la revue :

Journal of Global Optimization

Pagination :

329-350

Éditeur :

Springer Verlag

Date de publication :

2021

ISSN :

0925-5001

Mot(s)-clé(s) en anglais :

Multi-objective optimization
Combinatorial optimization
Anytime algorithms
Anytime behavior
ε-constraint

Discipline(s) HAL :

Informatique [cs]

Résumé en anglais : [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 ...
Lire la suite >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.Lire moins >

Langue :

Anglais

Vulgarisation :

Non

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL