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...
Main Author: | |
---|---|
Other Authors: | , , , |
Format: | Other/Unknown Material |
Language: | English |
Published: |
HAL CCSD
2006
|
Subjects: | |
Online Access: | https://hal.archives-ouvertes.fr/hal-00113362/file/pareto2.pdf https://hal.archives-ouvertes.fr/hal-00113362 |
id |
fttriple:oai:gotriple.eu:10670/1.hbptxy |
---|---|
record_format |
openpolar |
spelling |
fttriple:oai:gotriple.eu:10670/1.hbptxy 2023-05-15T16:48:51+02:00 How entropy-theorems can show that approximating high-dim Pareto-fronts is too hard Teytaud, Olivier 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) Reykjavik, Iceland 2006-01-01 https://hal.archives-ouvertes.fr/hal-00113362/file/pareto2.pdf https://hal.archives-ouvertes.fr/hal-00113362 en eng HAL CCSD hal-00113362 10670/1.hbptxy https://hal.archives-ouvertes.fr/hal-00113362/file/pareto2.pdf https://hal.archives-ouvertes.fr/hal-00113362 other Hyper Article en Ligne - Sciences de l'Homme et de la Société Bridging the Gap between Theory and Practice - Workshop PPSN-BTP Bridging the Gap between Theory and Practice - Workshop PPSN-BTP, 2006, Reykjavik, Iceland Multi-Objective Optimization Evolutionary Computation Theory info stat Conference Output https://vocabularies.coar-repositories.org/resource_types/c_c94f/ 2006 fttriple 2023-01-22T17:55:54Z 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. Other/Unknown Material Iceland Unknown |
institution |
Open Polar |
collection |
Unknown |
op_collection_id |
fttriple |
language |
English |
topic |
Multi-Objective Optimization Evolutionary Computation Theory info stat |
spellingShingle |
Multi-Objective Optimization Evolutionary Computation Theory info stat Teytaud, Olivier How entropy-theorems can show that approximating high-dim Pareto-fronts is too hard |
topic_facet |
Multi-Objective Optimization Evolutionary Computation Theory info stat |
description |
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. |
author2 |
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 |
author |
Teytaud, Olivier |
author_facet |
Teytaud, Olivier |
author_sort |
Teytaud, Olivier |
title |
How entropy-theorems can show that approximating high-dim Pareto-fronts is too hard |
title_short |
How entropy-theorems can show that approximating high-dim Pareto-fronts is too hard |
title_full |
How entropy-theorems can show that approximating high-dim Pareto-fronts is too hard |
title_fullStr |
How entropy-theorems can show that approximating high-dim Pareto-fronts is too hard |
title_full_unstemmed |
How entropy-theorems can show that approximating high-dim Pareto-fronts is too hard |
title_sort |
how entropy-theorems can show that approximating high-dim pareto-fronts is too hard |
publisher |
HAL CCSD |
publishDate |
2006 |
url |
https://hal.archives-ouvertes.fr/hal-00113362/file/pareto2.pdf https://hal.archives-ouvertes.fr/hal-00113362 |
op_coverage |
Reykjavik, Iceland |
genre |
Iceland |
genre_facet |
Iceland |
op_source |
Hyper Article en Ligne - Sciences de l'Homme et de la Société Bridging the Gap between Theory and Practice - Workshop PPSN-BTP Bridging the Gap between Theory and Practice - Workshop PPSN-BTP, 2006, Reykjavik, Iceland |
op_relation |
hal-00113362 10670/1.hbptxy https://hal.archives-ouvertes.fr/hal-00113362/file/pareto2.pdf https://hal.archives-ouvertes.fr/hal-00113362 |
op_rights |
other |
_version_ |
1766038943651856384 |