Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download
Contributor : Olivier Teytaud <>
Submitted on : Wednesday, September 19, 2007 - 2:16:19 PM
Last modification on : Monday, May 4, 2020 - 2:30:05 PM
Long-term archiving on: : Friday, April 9, 2010 - 2:29:27 AM


Files produced by the author(s)


  • HAL Id : inria-00173239, version 1



Olivier Teytaud. On the hardness of offline multiobjective optimization. Evolutionary Computation, Massachusetts Institute of Technology Press (MIT Press), 2007. ⟨inria-00173239⟩



Record views


Files downloads