Parallel Pareto local search revisited – ...
Type de document :
Communication dans un congrès avec actes
DOI :
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]
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
Pareto Local Search
Parallel Computation
Discipline(s) HAL :
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]
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 >
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 :
Collections :
Source :
Fichiers
- https://hal.archives-ouvertes.fr/hal-01920339/document
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-01920339/document
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- shi-gecco2018.pdf
- Accès libre
- Accéder au document