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), Laboratoire d'informatique de l'École polytechnique Palaiseau (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-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)
• Format: Conference Object
• Language: English
• Published: HAL CCSD 2006
• Subjects: Multi-Objective Optimization; Evolutionary Computation; Theory; [INFO.INFO-NA]Computer Science [cs]/Numerical Analysis [cs.NA]; [SCCO.COMP]Cognitive science/Computer science; Iceland
• Online Access: https://hal.science/hal-00113362; https://hal.science/hal-00113362/document; https://hal.science/hal-00113362/file/pareto2.pdf

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.