nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Weaving of Metaheuristics with Cooperative Parallelism

verfasst von : Jheisson López, Danny Múnera, Daniel Diaz, Salvador Abreu

Erschienen in: Parallel Problem Solving from Nature – PPSN XV

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Spark Clustering Computing Platform Based Parallel Particle Swarm Optimizers for Computationally Expensive Global Optimization

Nächstes Kapitel Conditional Preference Learning for Personalized and Context-Aware Journey Planning

Terms “immigration” and “emigration” are from the metaheuristics point-of-view.

The source code is available from https://github.com/jlopezrf/COPSolver-V_2.0.

Blum, C., Roli, A.: Metaheuristics in combinatorial optimization: overview and conceptual comparison. ACM Comput. Surv. 35(3), 268–308 (2003)CrossRef

Burkard, R.E., Karisch, S., Rendl, F.: QAPLIB - a quadratic assignment problem library. Eur. J. Oper. Res. 55(1), 115–119 (1991)CrossRef

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)CrossRef

Crainic, T., Gendreau, M., Hansen, P., Mladenovic, N.: Cooperative parallel variable neighborhood search for the p-median. J. Heuristics 10(3), 293–314 (2004)CrossRef

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_17CrossRef

Drezner, Z.: The extended concentric tabu for the quadratic assignment problem. Eur. J. Oper. Res. 160(2), 416–422 (2005)MathSciNetCrossRef

Drezner, Z.: Extensive experiments with hybrid genetic algorithms for the solution of the quadratic assignment problem. Comput. Oper. Res. 35(3), 717–736 (2008)MathSciNetCrossRef

Hoos, H., Stützle, T.: Stochastic Local Search: Foundations and Applications. Morgan Kaufmann/Elsevier, Burlington (2004)MATH

Misevicius, A.: A tabu search algorithm for the quadratic assignment problem. Comput. Optim. Appl. 30(1), 95–111 (2005)MathSciNetCrossRef

10.

Moscato, P., Cotta, C.: Memetic algorithms. In: Handbook of Applied Optimization, vol. 157, p. 168 (2002)

11.

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_4CrossRef

12.

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_17CrossRef

13.

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_2CrossRef

14.

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)

15.

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)

16.

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)

17.

Palubeckis, G.: An algorithm for construction of test cases for the quadratic assignment problem. Inform. Lith. Acad. Sci. 11(3), 281–296 (2000)MathSciNetMATH

18.

Saifullah Hussin, M.: Stochastic local search algorithms for single and bi-objective quadratic assignment problems. Ph.D. thesis. Université de Bruxelles (2016)

19.

Taillard, É.: Robust taboo search for the quadratic assignment problem. Parallel Comput. 17(4–5), 443–455 (1991)MathSciNetCrossRef

20.

Talbi, E.G., Bachelet, V.: COSEARCH: a parallel cooperative metaheuristic. J. Math. Model. Algorithms 5(1), 5–22 (2006)MathSciNetCrossRef

21.

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)

22.

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_6CrossRef

Titel: Weaving of Metaheuristics with Cooperative Parallelism
verfasst von: Jheisson López
Danny Múnera
Daniel Diaz
Salvador Abreu
Verlag: Springer International Publishing
Buch: Parallel Problem Solving from Nature – PPSN XV
Print ISBN: 978-3-319-99252-5

Electronic ISBN: 978-3-319-99253-2

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-99253-2_35

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner