Problem Features vs. Algorithm Performance ...
Type de document :
Compte-rendu et recension critique d'ouvrage
DOI :
Titre :
Problem Features vs. Algorithm Performance on Rugged Multi-objective Combinatorial Fitness Landscapes
Auteur(s) :
Daolio, Fabio [Auteur]
Faculty of Engineering [Nagano]
Liefooghe, Arnaud [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Verel, Sébastien [Auteur]
Laboratoire d'Informatique Signal et Image de la Côte d'Opale [LISIC]
Aguirre, Hernan [Auteur]
Faculty of Engineering [Nagano]
Tanaka, Kiyoshi [Auteur]
Faculty of Engineering [Nagano]
Faculty of Engineering [Nagano]
Liefooghe, Arnaud [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Parallel Cooperative Multi-criteria Optimization [DOLPHIN]
Verel, Sébastien [Auteur]
Laboratoire d'Informatique Signal et Image de la Côte d'Opale [LISIC]
Aguirre, Hernan [Auteur]
Faculty of Engineering [Nagano]
Tanaka, Kiyoshi [Auteur]
Faculty of Engineering [Nagano]
Titre de la revue :
Evolutionary Computation
Pagination :
555–585
Éditeur :
Massachusetts Institute of Technology Press (MIT Press)
Date de publication :
2017
ISSN :
1063-6560
Mot(s)-clé(s) en anglais :
Evolutionary multi-objective optimization
black-box 0–1 multi-objective problems
feature-based analysis
fitness landscape and problem difficulty
empirical performance modeling
multi-level multi-variate analysis
random-effects mixed models
black-box 0–1 multi-objective problems
feature-based analysis
fitness landscape and problem difficulty
empirical performance modeling
multi-level multi-variate analysis
random-effects mixed models
Discipline(s) HAL :
Computer Science [cs]/Operations Research [math.OC]
Mathématiques [math]/Optimisation et contrôle [math.OC]
Mathématiques [math]/Optimisation et contrôle [math.OC]
Résumé en anglais : [en]
In this paper, we attempt to understand and to contrast the impact of problem features on the performance of randomized search heuristics for black-box multi-objective combinatorial optimization problems. At first, we ...
Lire la suite >In this paper, we attempt to understand and to contrast the impact of problem features on the performance of randomized search heuristics for black-box multi-objective combinatorial optimization problems. At first, we measure the performance of two conventional dominance-based approaches with unbounded archive on a benchmark of enumerable binary optimization problems with tunable ruggedness, objective space dimension, and objective correlation (ρMNK-landscapes). Precisely, we investigate the expected runtime required by a global evolutionary optimization algorithm with an er-godic variation operator (GSEMO) and by a neighborhood-based local search heuristic (PLS), to identify a (1 + ε)−approximation of the Pareto set. Then, we define a number of problem features characterizing the fitness landscape, and we study their intercor-relation and their association with algorithm runtime on the benchmark instances. At last, with a mixed-effects multi-linear regression we assess the individual and joint effect of problem features on the performance of both algorithms, within and across the instance classes defined by benchmark parameters. Our analysis reveals further insights into the importance of ruggedness and multi-modality to characterize instance hardness for this family of multi-objective optimization problems and algorithms.Lire moins >
Lire la suite >In this paper, we attempt to understand and to contrast the impact of problem features on the performance of randomized search heuristics for black-box multi-objective combinatorial optimization problems. At first, we measure the performance of two conventional dominance-based approaches with unbounded archive on a benchmark of enumerable binary optimization problems with tunable ruggedness, objective space dimension, and objective correlation (ρMNK-landscapes). Precisely, we investigate the expected runtime required by a global evolutionary optimization algorithm with an er-godic variation operator (GSEMO) and by a neighborhood-based local search heuristic (PLS), to identify a (1 + ε)−approximation of the Pareto set. Then, we define a number of problem features characterizing the fitness landscape, and we study their intercor-relation and their association with algorithm runtime on the benchmark instances. At last, with a mixed-effects multi-linear regression we assess the individual and joint effect of problem features on the performance of both algorithms, within and across the instance classes defined by benchmark parameters. Our analysis reveals further insights into the importance of ruggedness and multi-modality to characterize instance hardness for this family of multi-objective optimization problems and algorithms.Lire moins >
Langue :
Anglais
Vulgarisation :
Non
Collections :
Source :
Fichiers
- https://hal.archives-ouvertes.fr/hal-01380612/document
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-01380612/document
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-01380612/document
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- daolio.ecj2016%20%281%29.pdf
- Accès libre
- Accéder au document