Skip to Main content Skip to Navigation
Conference papers

Comparison-Based Complexity of Multiobjective Optimization

Olivier Teytaud 1, 2
1 TAO - Machine Learning and Optimisation
CNRS - Centre National de la Recherche Scientifique : UMR8623, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LRI - Laboratoire de Recherche en Informatique
Abstract : Several comparison-based complexity results have been published recently, including multi-objective optimization. H owever, these results are, in the multiobjective case, quite pessimistic, due to the huge family of fitness function s considered. Combining assumptions on fitness functions and traditional comparison-based assumptions, we get more r ealistic bounds emphasizing the importance of reducing the number of conflicting objectives for reducing the runtime of multiobjective optimization. The approach can in particular predict lower bounds on the computation time, depend ing on the type of requested convergence: pointwise, or to the whole Pareto set. Also, a new (untested yet) algorith m is proposed for approximating the whole Pareto set.
Document type :
Conference papers
Complete list of metadata

Cited literature [25 references]  Display  Hide  Download

https://hal.inria.fr/hal-00786635
Contributor : Olivier Teytaud <>
Submitted on : Saturday, February 9, 2013 - 1:29:04 PM
Last modification on : Thursday, June 17, 2021 - 3:49:43 AM
Long-term archiving on: : Friday, May 10, 2013 - 4:02:04 AM

File

moomosans.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00786635, version 1

Collections

Citation

Olivier Teytaud. Comparison-Based Complexity of Multiobjective Optimization. GECCO 2011, 2011, Dublin, Ireland. pp.801-806. ⟨hal-00786635⟩

Share

Metrics

Record views

662

Files downloads

430