Titre :

Parallel Pareto local search revisited – First experimental results on bi-objective UBQP

Auteur(s) :

Shi, Jialong [Auteur]
Xi'an Jiaotong University [Xjtu]
Zhang, Qingfu [Auteur]
City University of Hong Kong [Hong Kong] [CUHK]
Derbel, Bilel [Auteur]
Optimisation de grande taille et calcul large échelle [BONUS]
Liefooghe, Arnaud [Auteur]
Optimisation de grande taille et calcul large échelle [BONUS]
Sun, Jianyong [Auteur]
Xi'an Jiaotong University [Xjtu]

Titre de la manifestation scientifique :

GECCO '18: Proceedings of the Genetic and Evolutionary Computation Conference

Ville :

Kyoto

Pays :

Japon

Date de début de la manifestation scientifique :

2018-07-15

Titre de l’ouvrage :

GECCO '18: Proceedings of the Genetic and Evolutionary Computation Conference

Éditeur :

ACM Press

Date de publication :

2018

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

Combinatorial Optimization
Pareto Local Search
Parallel Computation

Discipline(s) HAL :

Computer Science [cs]/Operations Research [math.OC]
Mathématiques [math]/Optimisation et contrôle [math.OC]

Résumé en anglais : [en]

Pareto Local Search (PLS) is a simple, yet effective optimization approach dedicated to multi-objective combinatorial optimization. It can however suffer from a high computational cost, especially when the size of the ...
Lire la suite >Pareto Local Search (PLS) is a simple, yet effective optimization approach dedicated to multi-objective combinatorial optimization. It can however suffer from a high computational cost, especially when the size of the Pareto optimal set is relatively large. Recently, incorporating decomposition in PLS had revealed a high potential, not only in providing high-quality approximation sets, but also in speeding-up the search process. Using the bi-objective Unconstrained Binary Quadratic Programming (bUBQP) problem as an illustrative benchmark, we demonstrate some shortcomings in the resulting decomposition-guided Parallel Pareto Local Search (PPLS), and we propose to revisit the PPLS design accordingly. For instances with a priori unknown Pareto front shape, we show that a simple pre-processing technique to estimate the scale of the Pareto front can help PPLS to better balance the workload. Furthermore, we propose a simple technique to deal with the critically-important scalability issue raised by PPLS when deployed over a large number of computing nodes. Our investigations show that the revisited version of PPLS provides a consistent performance, suggesting that decomposition-guided PPLS can be further generalized in order to improve both parallel efficiency and approximation quality.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Projet ANR :

Optimisation Multiobjectif Big

Collections :

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

Source :

Harvested from HAL