Affordable Access

On the hardness of offline multi-objective optimization.

Authors
  • Teytaud, Olivier
Type
Published Article
Journal
Evolutionary computation
Publication Date
Jan 01, 2007
Volume
15
Issue
4
Pages
475–491
Identifiers
PMID: 18021016
Source
Medline
License
Unknown

Abstract

It has been empirically established that multiobjective evolutionary algorithms do not scale well with the number of conflicting objectives. This paper shows that the convergence rate of all comparison-based multi-objective algorithms, for the Hausdorff distance, is not much better than the convergence rate of the random search under certain conditions. The number of objectives must be very moderate and the framework should hold the following assumptions: the objectives are conflicting and the computational cost is lower bounded by the number of comparisons is a good model. Our conclusions are: (i) the number of conflicting objectives is relevant (ii) the criteria based on comparisons with random-search for multi-objective optimization is also relevant (iii) having more than 3-objectives optimization is very hard. Furthermore, we provide some insight into cross-over operators.

Report this publication

Statistics

Seen <100 times