Title :

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

Author(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]
University of Coimbra [Portugal] [UC]
Verel, Sébastien [Auteur]
Laboratoire d'Informatique Signal et Image de la Côte d'Opale [LISIC]

Conference title :

GECCO 2018 - Genetic and Evolutionary Computation Conference

City :

Kyoto

Country :

Japon

Start date of the conference :

2018-07-15

Publisher :

ACM Press

Publication date :

2018

English keyword(s) :

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

HAL domain(s) :

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

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

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

Collections :

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

Source :

Harvested from HAL