Abstract
We propose PHYSH (Parallel HYbridization for Simple Heuristics), a framework to ease the design and implementation of hybrid metaheuristics via cooperative parallelism. With this framework, the user only needs encode each of the desired metaheuristics and may rely on PHYSH for parallelization, cooperation and hybridization. PHYSH supports the combination of population-based and single-solution metaheuristics and enables the user to control the tradeoff between intensification and diversification. We also provide an open-source implementation of this framework which we use to model the Quadratic Assignment Problem (QAP) with a hybrid solver, combining three metaheuristics. We present experimental evidence that PHYSH brings significant improvements over competing approaches, as witness the performance on representative hard instances of QAP.
This work was partly funded by FCT under grant UID/CEC/4668/2016 (LISP).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Notes
- 1.
Terms “immigration” and “emigration” are from the metaheuristics point-of-view.
- 2.
The source code is available from https://github.com/jlopezrf/COPSolver-V_2.0.
References
Blum, C., Roli, A.: Metaheuristics in combinatorial optimization: overview and conceptual comparison. ACM Comput. Surv. 35(3), 268–308 (2003)
Burkard, R.E., Karisch, S., Rendl, F.: QAPLIB - a quadratic assignment problem library. Eur. J. Oper. Res. 55(1), 115–119 (1991)
Caniou, Y., Codognet, P., Richoux, F., Diaz, D., Abreu, S.: Large-scale parallelism for constraint-based local search: the costas array case study. Constraints 20(1), 30–56 (2015)
Crainic, T., Gendreau, M., Hansen, P., Mladenovic, N.: Cooperative parallel variable neighborhood search for the p-median. J. Heuristics 10(3), 293–314 (2004)
Crainic, T., Toulouse, M.: Parallel meta-heuristics. In: Gendreau, M., Potvin, J.Y. (eds.) Handbook of Metaheuristics. ISOR, vol. 146, pp. 497–541. Springer, Boston (2010). https://doi.org/10.1007/978-1-4419-1665-5_17
Drezner, Z.: The extended concentric tabu for the quadratic assignment problem. Eur. J. Oper. Res. 160(2), 416–422 (2005)
Drezner, Z.: Extensive experiments with hybrid genetic algorithms for the solution of the quadratic assignment problem. Comput. Oper. Res. 35(3), 717–736 (2008)
Hoos, H., Stützle, T.: Stochastic Local Search: Foundations and Applications. Morgan Kaufmann/Elsevier, Burlington (2004)
Misevicius, A.: A tabu search algorithm for the quadratic assignment problem. Comput. Optim. Appl. 30(1), 95–111 (2005)
Moscato, P., Cotta, C.: Memetic algorithms. In: Handbook of Applied Optimization, vol. 157, p. 168 (2002)
Munera, D., Diaz, D., Abreu, S.: Hybridization as cooperative parallelism for the quadratic assignment problem. In: Blesa, M.J., et al. (eds.) HM 2016. LNCS, vol. 9668, pp. 47–61. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-39636-1_4
Munera, D., Diaz, D., Abreu, S.: Solving the quadratic assignment problem with cooperative parallel extremal optimization. In: Chicano, F., Hu, B., García-Sánchez, P. (eds.) EvoCOP 2016. LNCS, vol. 9595, pp. 251–266. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-30698-8_17
Munera, D., Diaz, D., Abreu, S., Codognet, P.: A parametric framework for cooperative parallel local search. In: Blum, C., Ochoa, G. (eds.) EvoCOP 2014. LNCS, vol. 8600, pp. 13–24. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44320-0_2
Munera, D., Diaz, D., Abreu, S., Codognet, P.: Flexible cooperation in parallel local search. In: Symposium on Applied Computing, SAC 2014, pp. 1360–1361. ACM Press, Gyeongju (2014)
Munera, D., Diaz, D., Abreu, S., Rossi, F., Saraswat, V., Codognet, P.: Solving hard stable matching problems via local search and cooperative parallelization. In: AAAI, Austin, TX, USA (2015)
Novoa, C., Qasem, A., Chaparala, A.: A SIMD tabu search implementation for solving the quadratic assignment problem with GPU acceleration. In: Proceedings of the 2015 XSEDE Conference on Scientific Advancements Enabled by Enhanced Cyberinfrastructure - XSEDE 2015, pp. 1–8 (2015)
Palubeckis, G.: An algorithm for construction of test cases for the quadratic assignment problem. Inform. Lith. Acad. Sci. 11(3), 281–296 (2000)
Saifullah Hussin, M.: Stochastic local search algorithms for single and bi-objective quadratic assignment problems. Ph.D. thesis. Université de Bruxelles (2016)
Taillard, É.: Robust taboo search for the quadratic assignment problem. Parallel Comput. 17(4–5), 443–455 (1991)
Talbi, E.G., Bachelet, V.: COSEARCH: a parallel cooperative metaheuristic. J. Math. Model. Algorithms 5(1), 5–22 (2006)
Toulouse, M., Crainic, T., Gendreau, M.: Communication issues in designing cooperative multi-thread parallel searches. In: Osman, I., Kelly, J. (eds.) Meta-Heuristics: Theory & Applications, pp. 501–522. Kluwer Academic Publishers, Norwell (1995)
Tsutsui, S., Fujimoto, N.: An analytical study of parallel GA with independent runs on GPUs. In: Tsutsui, S., Collet, P. (eds.) Massively Parallel Evolutionary Computation on GPGPUs. NCS, vol. 8, pp. 105–120. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-37959-8_6
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
López, J., Múnera, D., Diaz, D., Abreu, S. (2018). Weaving of Metaheuristics with Cooperative Parallelism. In: Auger, A., Fonseca, C., Lourenço, N., Machado, P., Paquete, L., Whitley, D. (eds) Parallel Problem Solving from Nature – PPSN XV. PPSN 2018. Lecture Notes in Computer Science(), vol 11101. Springer, Cham. https://doi.org/10.1007/978-3-319-99253-2_35
Download citation
DOI: https://doi.org/10.1007/978-3-319-99253-2_35
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-99252-5
Online ISBN: 978-3-319-99253-2
eBook Packages: Computer ScienceComputer Science (R0)