On Pareto local optimal solutions networks

Liefooghe, Arnaud; Derbel, Bilel; Verel, Sébastien; López-Ibáñez, Manuel; Aguirre, Hernan; Tanaka, Kiyoshi

Type de document :

Communication dans un congrès avec actes

DOI :

10.1007/978-3-319-99259-4_19

Titre :

On Pareto local optimal solutions networks

Auteur(s) :

Liefooghe, Arnaud [Auteur]

Optimisation de grande taille et calcul large échelle [BONUS]
Derbel, Bilel [Auteur]

Optimisation de grande taille et calcul large échelle [BONUS]
Verel, Sébastien [Auteur]
Laboratoire d'Informatique Signal et Image de la Côte d'Opale [LISIC]
López-Ibáñez, Manuel [Auteur]
University of Manchester [Manchester]
Aguirre, Hernan [Auteur]
Faculty of Engineering [Nagano]
Tanaka, Kiyoshi [Auteur]
Faculty of Engineering [Nagano]

Titre de la manifestation scientifique :

PPSN 2018 - International Conference on Parallel Problem Solving from Nature

Ville :

Coimbra

Pays :

Portugal

Date de début de la manifestation scientifique :

2018-09-08

Titre de la revue :

Lecture Notes in Computer Science

Éditeur :

Springer

Date de publication :

2018

Discipline(s) HAL :

Informatique [cs]/Intelligence artificielle [cs.AI]

Résumé en anglais : [en]

Pareto local optimal solutions (PLOS) are believed to highly influence the dynamics and the performance of multi-objective optimization algorithms, especially those based on local search and Pareto dominance. A number of ...
Lire la suite >Pareto local optimal solutions (PLOS) are believed to highly influence the dynamics and the performance of multi-objective optimization algorithms, especially those based on local search and Pareto dominance. A number of studies so far have investigated their impact on the difficulty of searching the landscape underlying a problem instance. However, the community still lacks knowledge on the structure of PLOS and the way it impacts the effectiveness of multi-objective algorithms. Inspired by the work on local optima networks in single-objective optimization, we introduce a PLOS network (PLOS-net) model as a step toward the fundamental understanding of multi-objective landscapes and search algorithms. Using a comprehensive set of ρmnk-landscapes, PLOS-nets are constructed by full enumeration, and selected network features are further extracted and analyzed with respect to instance characteristics. A correlation and regression analysis is then conducted to capture the importance of the PLOS-net features on the runtime and effectiveness of two prototypical Pareto-based heuristics. In particular, we are able to provide empirical evidence for the relevance of the PLOS-net model to explain algorithm performance. For instance, the degree of connectedness in the PLOS-net is shown to play an even more important role than the number of PLOS in the landscape.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Projet ANR :

Optimisation Multiobjectif Big

Collections :