Multi-objective NK landscapes with heterogeneous objectives

Raphaël Cosson (1, 2) , Roberto Santana (3) , Bilel Derbel (1, 2) , Arnaud Liefooghe (1, 2)

1 BONUS - Optimisation de grande taille et calcul large échelle
2 CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189
3 UPV / EHU - University of the Basque Country = Euskal Herriko Unibertsitatea

So far, multi-objective NK landscapes have been investigated under the assumption of a homogeneous nature of the involved objectives in terms of difficulty. However, we argue that problems with heterogeneous objectives, e.g., in terms of multi-modality, can be challenging for multi-objective evolutionary algorithms, and deserve further considerations. In this paper, we propose a model of multi-objective NK landscapes, where each objective has a different degree of variable interactions (K), as a benchmark to investigate heterogeneous multi-objective optimization problems. We show that the use of a rank-annotated neighborhood network with labeled local optimal solutions, together with landscape metrics extracted from the heterogeneous objectives, thoroughly characterize bi-objective NK landscapes with a different level of heterogeneity among the objectives.

Mots clés: Multi-objective optimization; heterogeneous objectives; landscape analysis; NK landscapes

Domaines: Informatique [cs]; Intelligence artificielle [cs.AI]; Recherche opérationnelle [math.OC]

Raphaël Cosson, Roberto Santana, Bilel Derbel, Arnaud Liefooghe. Multi-objective NK landscapes with heterogeneous objectives. GECCO 2022 - Genetic and Evolutionary Computation Conference, 2022, Boston, MA, United States. pp.502-510, ⟨10.1145/3512290.3528858⟩. ⟨hal-03693674⟩