Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 10593))
Included in the following conference series:
3266Accesses
Abstract
Pareto Local Search (PLS) is a basic building block in many state-of-the-art multiobjective combinatorial optimization algorithms. However, the basic PLS requires a long time to find high-quality solutions. In this paper, we propose and investigate several parallel strategies to speed up PLS. These strategies are based on a parallel multi-search framework. In our experiments, we investigate the performances of different parallel variants of PLS on the multiobjective unconstrained binary quadratic programming problem. Each PLS variant is a combination of the proposed parallel strategies. The experimental results show that the proposed approaches can significantly speed up PLS while maintaining about the same solution quality. In addition, we introduce a new way to visualize the search process of PLS on two-objective problems, which is helpful to understand the behaviors of PLS algorithms.
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 11439
- Price includes VAT (Japan)
- Softcover Book
- JPY 14299
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Branke, J., Schmeck, H., Deb, K., Reddy, S.M.: Parallelizing multi-objective evolutionary algorithms: cone separation. In: IEEE Congress on Evolutionary Computation. vol. 2, pp. 1952–1957. IEEE (2004)
Derbel, B., Liefooghe, A., Zhang, Q., Aguirre, H., Tanaka, K.: Multi-objective local search based on decomposition. In: Handl, J., Hart, E., Lewis, P.R., López-Ibáñez, M., Ochoa, G., Paechter, B. (eds.) PPSN 2016. LNCS, vol. 9921, pp. 431–441. Springer, Cham (2016). doi:10.1007/978-3-319-45823-6_40
Drugan, M.M., Thierens, D.: Stochastic Pareto local search: Pareto neighbourhood exploration and perturbation strategies. J. Heuristics18(5), 727–766 (2012)
Dubois-Lacoste, J., López-Ibáñez, M., Stützle, T.: Anytime pareto local search. Eur. J. Oper. Res.243(2), 369–385 (2015)
Ehrgott, M.: Multicriteria Optimization. Springer, Heidelberg (2006)
Geiger, M.J.: Decision support for multi-objective flow shop scheduling by the Pareto iterated local search methodology. Comput. Ind. Eng.61(3), 805–812 (2011)
Ke, L., Zhang, Q., Battiti, R.: Hybridization of decomposition and local search for multiobjective optimization. IEEE Trans. Cybern.44(10), 1808–1820 (2014)
Liefooghe, A., Humeau, J., Mesmoudi, S., Jourdan, L., Talbi, E.G.: On dominance-based multiobjective local search: design, implementation and experimental analysis on scheduling and traveling salesman problems. J. Heuristics18(2), 317–352 (2012)
Liefooghe, A., Verel, S., Hao, J.K.: A hybrid metaheuristic for multiobjective unconstrained binary quadratic programming. Appl. Soft Comput.16, 10–19 (2014)
Liefooghe, A., Verel, S., Paquete, L., Hao, J.K.: Experiments on local search for bi-objective unconstrained binary quadratic programming. In: 8th International Conference on Evolutionary Multi-Criterion Optimization, vol. 9018, pp. 171–186 (2015)
Liu, H.L., Gu, F., Zhang, Q.: Decomposition of a multiobjective optimization problem into a number of simple multiobjective subproblems. IEEE Trans. Evol. Comput.18(3), 450–455 (2014)
Lust, T., Jaszkiewicz, A.: Speed-up techniques for solving large-scale biobjective TSP. Comput. Oper. Res.37(3), 521–533 (2010)
Lust, T., Teghem, J.: Two-phase Pareto local search for the biobjective traveling salesman problem. J. Heuristics16(3), 475–510 (2010)
Paquete, L., Chiarandini, M., Stützle, T.: Pareto local optimum sets in the biobjective traveling salesman problem an experimental study. In: Gandibleux, X., Sevaux, M., Sörensen, K., T’kindt, V. (eds.) Metaheuristics for Multiobjective Optimisation. LNE, vol. 535, pp. 177–199. Springer, Heidelberg (2004). doi:10.1007/978-3-642-17144-4_7
Paquete, L., Schiavinotto, T., Stützle, T.: On local optima in multiobjective combinatorial optimization problems. Ann. Oper. Res.156(1), 83–97 (2007)
Zhang, Q., Li, H.: MOEA/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans. Evol. Comput.11(6), 712–731 (2007)
Zitzler, E., Thiele, L., Laumanns, M., Fonseca, C.M., Da Fonseca, V.G.: Performance assessment of multiobjective optimizers: an analysis and review. IEEE Trans. Evol. Comput.7(2), 117–132 (2003)
Acknowledgments
The work described in this paper was supported by the National Science Foundation of China under Grant 61473241, and a grant from ANR/RCC Joint Research Scheme sponsored by the Research Grants Council of the Hong Kong Special Administrative Region, China (Project No. A-CityU101/16), and France National Research Agency (ANR-16-CE23-0013-01).
Author information
Authors and Affiliations
Department of Computer Science, City University of Hong Kong, Hong Kong, Hong Kong
Jialong Shi & Qingfu Zhang
The City University of Hong Kong Shenzhen Research Institute, Shenzhen, China
Jialong Shi & Qingfu Zhang
CNRS, Centrale Lille, UMR 9189 – CRIStAL, University of Lille, 59000, Lille, France
Bilel Derbel & Arnaud Liefooghe
Dolphin, Inria Lille – Nord Europe, 59000, Lille, France
Bilel Derbel & Arnaud Liefooghe
LISIC, University Littoral Côte d’Opale, 62100, Calais, France
Sébastien Verel
- Jialong Shi
You can also search for this author inPubMed Google Scholar
- Qingfu Zhang
You can also search for this author inPubMed Google Scholar
- Bilel Derbel
You can also search for this author inPubMed Google Scholar
- Arnaud Liefooghe
You can also search for this author inPubMed Google Scholar
- Sébastien Verel
You can also search for this author inPubMed Google Scholar
Corresponding author
Correspondence toJialong Shi.
Editor information
Editors and Affiliations
Southern University of Science and Technology, Shenzhen, China
Yuhui Shi
City University of Hong Kong, Hong Kong, Kowloon, Hong Kong
Kay Chen Tan
Victoria University of Wellington, Wellington, Wellington, New Zealand
Mengjie Zhang
Southern University of Science and Technology, Shenzhen, China
Ke Tang
RMIT University, Melbourne, Victoria, Australia
Xiaodong Li
City University of Hong Kong, Kowloon Tong, Hong Kong
Qingfu Zhang
Peking University, Beijing, China
Ying Tan
University of Leipzig, Leipzig, Germany
Martin Middendorf
University of Surrey, Guildford, Surrey, United Kingdom
Yaochu Jin
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Shi, J., Zhang, Q., Derbel, B., Liefooghe, A., Verel, S. (2017). Using Parallel Strategies to Speed up Pareto Local Search. In: Shi, Y.,et al. Simulated Evolution and Learning. SEAL 2017. Lecture Notes in Computer Science(), vol 10593. Springer, Cham. https://doi.org/10.1007/978-3-319-68759-9_6
Download citation
Published:
Publisher Name:Springer, Cham
Print ISBN:978-3-319-68758-2
Online ISBN:978-3-319-68759-9
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative