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

• 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

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.