Title :

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

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

Conference title :

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

City :

Kyoto

Country :

Japon

Start date of the conference :

2018-07-15

Book title :

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

Publisher :

ACM Press

Publication date :

2018

English keyword(s) :

Combinatorial Optimization
Pareto Local Search
Parallel Computation

HAL domain(s) :

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

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

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

ANR Project :

Optimisation Multiobjectif Big

Collections :

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

Source :

Harvested from HAL