On Pareto local optimal solutions networks

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

Document type :

Communication dans un congrès avec actes

DOI :

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

Title :

On Pareto local optimal solutions networks

Author(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]

Conference title :

PPSN 2018 - International Conference on Parallel Problem Solving from Nature

City :

Coimbra

Country :

Portugal

Start date of the conference :

2018-09-08

Journal title :

Lecture Notes in Computer Science

Publisher :

Springer

Publication date :

2018

HAL domain(s) :

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

English abstract : [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 ...
Show more >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.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

ANR Project :

Optimisation Multiobjectif Big

Collections :