skip to main content
10.1145/3512290.3528753acmconferencesArticle/Chapter ViewAbstractPublication PagesgeccoConference Proceedingsconference-collections
research-article

High performance evolutionary computation with tensor-based acceleration

Published: 08 July 2022 Publication History

Abstract

Optimization methods, including evolutionary algorithms, need increasing efficiency in order to solve more and more complex problems in the shortest possible time. Apart from tuning the structure of those algorithms and adapting them to the given problem, the best way to speed up computations is introducing more parallelism, either at the hardware level (by using accelerators), or at the architecture level (by using multiple compute nodes). In this paper, we propose a method for expressing evolutionary computations, based on the tensor computational model. The presented approach enables cross-platform hardware acceleration on CPUs, GPUs and TPUs. To validate the new method, we contribute an open, extensible evolutionary framework, with support for distributed, accelerated execution in heterogeneous environments. Finally, we demonstrate results of the conducted tests that confirm the efficiency of the proposed approach, also in comparison to other existing frameworks.

References

[1]
Ramnik Arora, Rupesh Tulshyan, and Kalyanmoy Deb. 2010. Parallelization of binary and real-coded genetic algorithms on GPU using CUDA. In IEEE Congress on Evolutionary Computation. IEEE, 1--8.
[2]
Aleksander Byrski and Marek Kisiel-Dorohinicki. 2009. Agent-Based Model and Computing Environment Facilitating the Development of Distributed Computational Intelligence Systems. In ICCS.
[3]
GE Cárdenas, R Poveda Ch, and HO García. 2017. A solution for the quadratic assignment problem (QAP) through a parallel genetic algorithm based grid on GPU. Applied Mathematical Sciences 11, 57 (2017), 2843--2854.
[4]
John Runwei Cheng and Mitsuo Gen. 2020. Parallel Genetic Algorithms with GPU Computing. In Industry 4.0, Tamás Bányai and Antonella Petrilloand Fabio De Felice (Eds.). IntechOpen, Rijeka, Chapter 6.
[5]
Mark A. Coletti, EricO. Scott, and Jeffrey K. Bassett. 2020. Library for Evolutionary Algorithms in Python (LEAP). In Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion (Cancún, Mexico) (GECCO '20). Association for Computing Machinery, New York, NY, USA, 1571--1579.
[6]
Stefano Debattisti, Nicola Marlat, Luca Mussi, and Stefano Cagnoni. 2009. Implementation of a simple genetic algorithm within the cuda architecture. In The Genetic and Evolutionary Computation Conference.
[7]
Juan J Durillo and Antonio J Nebro. 2011. jMetal: A Java framework for multiobjective optimization. Advances in Engineering Software 42, 10 (2011), 760--771.
[8]
Félix-Antoine Fortin, François-Michel De Rainville, Marc-André Gardner, Marc Parizeau, and Christian Gagné. 2012. DEAP: Evolutionary Algorithms Made Easy. Journal of Machine Learning Research 13 (jul 2012), 2171--2175.
[9]
Yue-Jiao Gong, Wei-Neng Chen, Zhi-Hui Zhan, Jun Zhang, Yun Li, Qingfu Zhang, and Jing-Jing Li. 2015. Distributed evolutionary algorithms and their models: A survey of the state-of-the-art. Applied Soft Computing 34 (2015), 286--300.
[10]
Jiri Jaros. 2012. Multi-GPU island-based genetic algorithm for solving the knapsack problem. In 2012 IEEE Congress on Evolutionary Computation. 1--8.
[11]
Krzysztof Jurczuk, Marcin Czajkowski, and Marek Kretowski. 2021. Fitness evaluation reuse for accelerating GPU-based evolutionary induction of decision trees. The International Journal of High Performance Computing Applications 35, 1 (2021), 20--32.
[12]
Lek-Heng Lim. 2021. Tensors in computations. Acta Numerica 30 (2021), 555--764.
[13]
Thé Van Luong, Nouredine Melab, and El-Ghazali Talbi. 2010. GPU-based island model for evolutionary algorithms. In Proceedings of the 12th annual conference on Genetic and evolutionary computation. 1089--1096.
[14]
Ogier Maitre, Nicolas Lachiche, Philippe Clauss, Laurent Baumes, Avelino Corma, and Pierre Collet. 2009. Efficient Parallel Implementation of Evolutionary Algorithms on GPGPU Cards, Vol. 5704. 974--985.
[15]
Ogier Maitre, Stéphane Querry, Nicolas Lachiche, and Pierre Collet. 2010. EASEA parallelization of tree-based Genetic Programming. In IEEE Congress on Evolutionary Computation. 1--8.
[16]
Frédéric Pinel, Bernabé Dorronsoro, and Pascal Bouvry. 2013. Solving very large instances of the scheduling of independent tasks problem on the GPU. J. Parallel and Distrib. Comput. 73, 1 (2013), 101--110.
[17]
Chris Simons and Aurora Ramírez. 2017. Evolutionary computing frameworks for optimisation. Overload 25, 142 (2017).
[18]
Shigeyoshi Tsutsui and Pierre Collet (Eds.). 2013. Massively Parallel Evolutionary Computation on GPGPUs. Springer.
[19]
Shigeyoshi Tsutsui and Noriyuki Fujimoto. 2011. ACO with Tabu Search on a GPU for Solving QAPs using Move-Cost Adjusted Thread Assignment. Genetic and Evolutionary Computation Conference, GECCO'11, 1547--1554.

Cited By

View all

Index Terms

  1. High performance evolutionary computation with tensor-based acceleration

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference
    July 2022
    1472 pages
    ISBN:9781450392372
    DOI:10.1145/3512290
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 08 July 2022

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. GPGPU
    2. computing framework
    3. distributed computing
    4. evolutionary computing

    Qualifiers

    • Research-article

    Funding Sources

    • Polish Ministry of Education and Science

    Conference

    GECCO '22
    Sponsor:

    Acceptance Rates

    Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)28
    • Downloads (Last 6 weeks)2
    Reflects downloads up to 03 Jan 2025

    Other Metrics

    Citations

    Cited By

    View all

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media