On the hardness of offline multiobjective optimization

Olivier Teytaud (1)

1 TANC - Algorithmic number theory for cryptology

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.

Mots clés: Multi-objective optimization; evolutionary algorithm; complexity

Domaines: Optimisation et contrôle [math.OC]

Olivier Teytaud. On the hardness of offline multiobjective optimization. Evolutionary Computation, 2007. ⟨inria-00173239⟩