HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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

https://hal.inria.fr/inria-00173239
Contributor : Olivier Teytaud Connect in order to contact the contributor
Submitted on : Wednesday, September 19, 2007 - 2:16:19 PM
Last modification on : Friday, February 4, 2022 - 3:21:39 AM
Long-term archiving on: : Friday, April 9, 2010 - 2:29:27 AM

File

pareto2.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00173239, version 1

Collections

Citation

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

Share

Metrics

Record views

193

Files downloads

393