Problem Features versus Algorithm Performance on Rugged Multiobjective Combinatorial Fitness Landscapes.
In this article, we attempt to understand and to contrast the impact of problem features on the performance of randomized search heuristics for black-box multiobjective 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 ([Formula: see text]MNK-landscapes). Precisely, we investigate the expected runtime required by a global evolutionary optimization algorithm with an ergodic variation operator (GSEMO) and by a neighborhood-based local search heuristic (PLS), to identify a ([Formula: see text]approximation of the Pareto set. Then, we define a number of problem features characterizing the fitness landscape, and we study their intercorrelation and their association with algorithm runtime on the benchmark instances. At last, with a mixed-effects multilinear 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 multimodality to characterize instance hardness for this family of multiobjective optimization problems and algorithms.
Shinshu University, Faculty of Engineering, Nagano, Japan fdaolio@shinshu-u.ac.jp.
Fabio
F
Daolio
Univ. Lille, CNRS, Centrale Lille, UMR 9189 - CRIStAL, F-59000, Lille, France Inria Lille-Nord Europe, F-59650 Villeneuve d'Ascq, France arnaud.liefooghe@univ-lille1.fr.
Arnaud
A
Liefooghe
Univ. Littoral Côte d'Opale, EA 4491 - LISIC - F-62228 Calais, France verel@lisic.univ-littoral.fr.
Sébastien
S
Verel
Shinshu University, Faculty of Engineering, Nagano, Japan ahernan@shinshu-u.ac.jp.
Hernán
H
Aguirre
Shinshu University, Faculty of Engineering, Nagano, Japan ktanaka@shinshu-u.ac.jp.
Kiyoshi
K
Tanaka
D000465:Algorithms; D019985:Benchmarking; D003198:Computer Simulation; D000066506:Heuristics
Evolutionary multiobjective optimization; black-box 0–1 multiobjective problems; empirical performance modeling; feature-based analysis; fitness landscape and problem difficulty; multilevel multivariate analysis; random-effects mixed models