How entropy-theorems can show that approximating high-dim Pareto-fronts is too hard

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 any comparison-based multi-objective algorithm, for the Hausdorff distance, is not much better than the convergence rate of...

Full description

Bibliographic Details
Main Author: Teytaud, Olivier
Other Authors: Algorithmic number theory for cryptology (TANC), Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'informatique de l'École polytechnique Palaiseau (LIX), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)
Format: Other/Unknown Material
Language:English
Published: HAL CCSD 2006
Subjects:
Multi-Objective Optimization
Evolutionary Computation
Theory
info
stat
Iceland
Online Access:https://hal.archives-ouvertes.fr/hal-00113362/file/pareto2.pdf
https://hal.archives-ouvertes.fr/hal-00113362
Description
Summary: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 any comparison-based multi-objective algorithm, 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 assumption is that the objectives have conflicts. Our conclusions are (i) the relevance of the number of conflicting objectives (ii) the relevance of random-search-based criterions (iii) the very-hardness of more than 3- objectives optimization (iv) some hints about new cross-over operators.

Similar Items