nach oben

The Journal of Supercomputing

Erschienen in:

05.07.2018

Comparing GPU-parallelized metaheuristics to branch-and-bound for batch plants optimization

verfasst von: Andrey Borisenko, Sergei Gorlatch

Erschienen in: The Journal of Supercomputing | Ausgabe 12/2019

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We systematically compare two approaches with the optimal design of multiproduct batch plants that are widely used, e.g., in the chemical industry. Deterministic algorithms like branch-and-bound achieve global optimality, but often require a prohibitively high computation effort. We propose an alternative, hybrid algorithm by combining two metaheuristics: ant colony optimization (ACO) and simulated annealing (SA), in order to find near-optimal solutions in a reasonable time. We develop a parallel implementation of our hybrid approach on graphics processing units using CUDA. We experimentally compare both approaches, and we show that our hybrid metaheuristic approach \((\hbox {ACO}+\hbox {SA})\) yields almost-optimal solutions, while computing them significantly faster than when using branch-and-bound.

Vorheriger Artikel A formally based parallelization of data mining algorithms for multi-core systems

Nächster Artikel Design and reliability analysis of fault-tolerant shuffle exchange gamma logical neighborhood interconnection network

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

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

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+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

Aarts E, Korst J, Michiels W (2014) Simulated annealing. In: Search methodologies. Springer, pp. 265–285.https://doi.org/10.1007/978-1-4614-6940-7_10

Birattari M (2009) Tuning metaheuristics: a machine learning perspective. Springer, Berlin. https://doi.org/10.1007/978-3-642-00483-4 CrossRef

Borisenko A, Gorlatch S (2017) Parallelizing metaheuristics for optimal design of multiproduct batch plants on GPU. In: Parallel Computing Technologies, Lecture Notes in Computer Science, vol 10421, pp 405–417. https://doi.org/10.1007/978-3-319-62932-2_39

Borisenko A, Haidl M, Gorlatch S (2017) A GPU parallelization of branch-and-bound for multiproduct batch plants optimization. J Supercomput 73(2):639–651. https://doi.org/10.1007/s11227-016-1784-x CrossRef

Borisenko A, Kegel P, Gorlatch S (2011) Optimal design of multi-product batch plants using a parallel branch-and-bound method. In: Parallel Computing Technologies, Lecture Notes in Computer Science, vol 6873. Springer, pp 417–430. https://doi.org/10.1007/978-3-642-23178-0_36

Dawson L, Stewart I (2013) Improving ant colony optimization performance on the GPU using CUDA. In: 2013 IEEE Congress on Evolutionary Computation. IEEE, pp 1901–1908. https://doi.org/10.1109/cec.2013.6557791

Delévacq A, Delisle P, Gravel M, Krajecki M (2013) Parallel ant colony optimization on graphics processing units. J Parallel Distrib Comput 73(1):52–61. https://doi.org/10.1016/j.jpdc.2012.01.003 CrossRef

Dorigo M, Blum C (2005) Ant colony optimization theory: a survey. Theor Comput Sci 344(2–3):243–278. https://doi.org/10.1016/j.tcs.2005.05.020 MathSciNetCrossRefMATH

Dorigo M, Stützle T (2010) Ant colony optimization: overview and recent advances. In: Handbook of Metaheuristics. Springer, pp 227–263. https://doi.org/10.1007/978-1-4419-1665-5_8 CrossRef

10.

Gonzalez-Pardo A, Camacho D (2013) A new CSP graph-based representation for ant colony optimization. In: 2013 IEEE Congress on Evolutionary Computation. Institute of Electrical and Electronics Engineers (IEEE), pp 689–696. https://doi.org/10.1109/cec.2013.6557635

11.

Kallioras NA, Kepaptsoglou K, Lagaros DN (2015) Transit stop inspection and maintenance scheduling: a GPU accelerated metaheuristics approach. Transp Res Part C Emerg Technol 55:246–260. https://doi.org/10.1016/j.trc.2015.02.013 CrossRef

12.

Khan S, Bilal M, Sharif M, Sajid M, Baig R (2009) Solution of \(n\)-queen problem using ACO. In: 2009 IEEE 13th International Multitopic Conference. Institute of Electrical and Electronics Engineers (IEEE), pp 1–5. https://doi.org/10.1109/inmic.2009.5383157

13.

Kirkpatrick S, Gelatt CD, Vecchi MP et al (1983) Optimization by simulated annealing. Science 220(4598):671–680. https://doi.org/10.1126/science.220.4598.671 MathSciNetCrossRefMATH

14.

NVIDIA Corporation: CUDA C programming guide 9.1 (2016). http://docs.nvidia.com/cuda/pdf/CUDA_C_Programming_Guide.pdf

15.

F Rossi, Van Beek P, T Walsh (2006) Handbook of constraint programming. Elsevier, New York

16.

Solnon C (2010) Ant colony optimization and constraint programming. Wiley, Hoboken. https://doi.org/10.1002/9781118557563

17.

Stützle T, López-Ibánez M, Pellegrini P, Maur M, de Oca MM, Birattari M, Dorigo M (2011) Parameter adaptation in ant colony optimization. In: Autonomous search. Springer, Berlin, pp 191–215. https://doi.org/10.1007/978-3-642-21434-9_8 CrossRef

18.

Valadi J, Siarry P (2014) Applications of metaheuristics in process engineering. Springer, Berlin. https://doi.org/10.1007/978-3-319-06508-3 MATH

19.

Wei KC, Wu CC, Yu HL (2015) Mapping the simulated annealing algorithm onto CUDA GPUs. In: 2015 10th International Conference on Intelligent Systems and Knowledge Engineering (ISKE), pp 1–8. https://doi.org/10.1109/iske.2015.97

20.

Yang XS (2010) Nature-inspired metaheuristic algorithms. Luniver Press, Beckington

Titel: Comparing GPU-parallelized metaheuristics to branch-and-bound for batch plants optimization
verfasst von: Andrey Borisenko
Sergei Gorlatch
Publikationsdatum: 05.07.2018
Verlag: Springer US
Erschienen in: The Journal of Supercomputing / Ausgabe 12/2019
Print ISSN: 0920-8542
Elektronische ISSN: 1573-0484
DOI: https://doi.org/10.1007/s11227-018-2472-9

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"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Weitere Artikel der Ausgabe 12/2019

Domino pattern formation by cellular automata agents

Data-independent vantage point selection for range queries

The DiamondCandy LRnLA algorithm: raising efficiency of the 3D cross-stencil schemes

A hybrid job scheduling algorithm based on Tabu and Harmony search algorithms

Parallel computing technologies 2018

A similarity study of I/O traces via string kernels

Premium Partner