On the hardness of offline multiobjective optimization

Olivier Teytaud 1
1 TANC - Algorithmic number theory for cryptology
Inria Saclay - Ile de France, LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
Abstract : It is empirically established that multiobjective evolutionary algorithms do not scale well with the number of conflicting objectives. We here show that the convergence rate of all comparison-based multiobjective algorithms, for the Hausdorff distance, is not much better than the convergence rate of the random search, unless the number of objectives is very moderate, in a framework in which the stronger assumptions are (i) that the objectives are conflicting (ii) that lower bounding the computational cost by the number of comparisons is a good model. Our conclusions are (i) the relevance of the number of conflicting objectives (ii) the relevance of criteria based on comparisons with random-search for multi-objective optimization (iii) the very-hardness of more than 3- objectives optimization (iv) some hints about cross-over operators.
Type de document :
Article dans une revue
Evolutionary Computation Journal, MIT Press, 2007
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00173239
Contributeur : Olivier Teytaud <>
Soumis le : mercredi 19 septembre 2007 - 14:16:19
Dernière modification le : mercredi 28 novembre 2018 - 15:36:02
Document(s) archivé(s) le : vendredi 9 avril 2010 - 02:29:27

Fichier

pareto2.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00173239, version 1

Collections

Citation

Olivier Teytaud. On the hardness of offline multiobjective optimization. Evolutionary Computation Journal, MIT Press, 2007. 〈inria-00173239〉

Partager

Métriques

Consultations de la notice

269

Téléchargements de fichiers

252