HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

On the structure of multiobjective combinatorial search space: MNK-landscapes with correlated objectives

Sébastien Verel 1, 2 Arnaud Liefooghe 2, 3 Laetitia Jourdan 2 Clarisse Dhaenens 2, 3
1 Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis (I3S) / Groupe SCOBI
Laboratoire I3S - MDSC - Modèles Discrets pour les Systèmes Complexes
2 DOLPHIN - Parallel Cooperative Multi-criteria Optimization
Inria Lille - Nord Europe, LIFL - Laboratoire d'Informatique Fondamentale de Lille
Abstract : The structure of the search space explains the behavior of multiobjective search algorithms, and helps to design well-performing approaches. In this work, we analyze the properties of multiobjective combinatorial search spaces, and we pay a particular attention to the correlation between the objective functions. To do so, we extend the multiobjective NK-landscapes in order to take the objective correlation into account. We study the co-influence of the problem dimension, the degree of non-linearity, the number of objectives, and the objective correlation on the structure of the Pareto optimal set, in terms of cardinality and number of supported solutions, as well as on the number of Pareto local optima. This work concludes with guidelines for the design of multiobjective local search algorithms, based on the main fitness landscape features.
Document type :
Journal articles
Complete list of metadata

Contributor : Sébastien Verel Connect in order to contact the contributor
Submitted on : Thursday, September 9, 2021 - 11:23:55 AM
Last modification on : Tuesday, May 3, 2022 - 3:20:22 AM
Long-term archiving on: : Saturday, December 11, 2021 - 7:19:51 AM


Files produced by the author(s)



Sébastien Verel, Arnaud Liefooghe, Laetitia Jourdan, Clarisse Dhaenens. On the structure of multiobjective combinatorial search space: MNK-landscapes with correlated objectives. European Journal of Operational Research, Elsevier, 2013, 227 (2), pp.331-342. ⟨10.1016/j.ejor.2012.12.019⟩. ⟨hal-00760097⟩



Record views


Files downloads