Titre :

Dominance, epsilon, and hypervolume local optimal sets in multi-objective optimization, and how to tell the difference

Auteur(s) :

Liefooghe, Arnaud [Auteur]
Optimisation de grande taille et calcul large échelle [BONUS]
López-Ibáñez, Manuel [Auteur]
University of Manchester [Manchester]
Paquete, Luís [Auteur]
Universidade de Coimbra = University of Coimbra [Portugal] [UC]
Verel, Sébastien [Auteur]
Laboratoire d'Informatique Signal et Image de la Côte d'Opale [LISIC]

Titre de la manifestation scientifique :

GECCO 2018 - Genetic and Evolutionary Computation Conference

Ville :

Kyoto

Pays :

Japon

Date de début de la manifestation scientifique :

2018-07-15

Éditeur :

ACM Press

Date de publication :

2018

Mot(s)-clé(s) en anglais :

Set-based multi-objective optimization
Quality Indicators
Local optima
Local search
Multi-objective combinatorial optimization

Discipline(s) HAL :

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

Résumé en anglais : [en]

Local search algorithms have shown good performance for several multi-objective combinatorial optimization problems. These approaches naturally stop at a local optimal set (LO-set) under given definitions of neighborhood ...
Lire la suite >Local search algorithms have shown good performance for several multi-objective combinatorial optimization problems. These approaches naturally stop at a local optimal set (LO-set) under given definitions of neighborhood and preference relation among subsets of solutions, such as set-based dominance relation, hypervolume or epsilon indicator. It is an open question how LO-sets under different set preference relations relate to each other. This paper reports an in-depth experimental analysis on multi-objective nk-landscapes. Our results reveal that, whatever the preference relation, the number of LO-sets typically increases with the problem non-linearity, and decreases with the number of objectives. We observe that strict LO-sets of bounded cardinality under set-dominance are LO-sets under both epsilon and hypervolume, and that LO-sets under hypervolume are LO-sets under set-dominance, whereas LO-sets under epsilon are not. Nonetheless, LO-sets under set-dominance are more similar to LO-sets under epsilon than under hypervolume. These findings have important implications for multi-objective local search. For instance, a dominance-based approach with bounded archive gets more easily trapped and might experience difficulty to identify an LO-set under epsilon or hypervolume. On the contrary, a hypervolume-based approach is expected to perform more steps before converging to better approximations.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL