Parallel Pareto local search revisited – ...
Document type :
Communication dans un congrès avec actes
DOI :
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]
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
Pareto Local Search
Parallel Computation
HAL domain(s) :
Computer Science [cs]/Operations Research [math.OC]
Mathématiques [math]/Optimisation et contrôle [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 >
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 :
Collections :
Source :
Files
- https://hal.archives-ouvertes.fr/hal-01920339/document
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-01920339/document
- Open access
- Access the document
- document
- Open access
- Access the document
- shi-gecco2018.pdf
- Open access
- Access the document