FANG: Fast and Efficient Successor-State Generation for Heuristic Optimization on GPUs

Publikation

Marcel Köster, Julian Groß, Antonio Krüger

In: International Conference on Algorithms and Architectures for Parallel Processing. International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP-2019) 19th December 9-11 Melbourne Australia Springer 2019.

Abstrakt

Many optimization problems (especially nonsmooth ones) are typically solved by genetic, evolutionary, or metaheuristic-based algorithms. However, these genetic approaches and other related papers typically assume the existence of a neighborhood or successor-state function N(x), where x is a candidate state. The implementation of such a function can become arbitrarily complex in the field of combinatorial optimization. Many N(x) functions for a huge variety of different domain-specific problems have been developed in the past to solve this general problem. However, it has always been a great challenge to port or realize these functions on a massively-parallel architecture like a Graphics Processing Unit (GPU). We present a GPU-based method called FANG that implements a generic and reusable N(x) for arbitrary domains in the field of combinatorial optimization. It can be customized to satisfy domain-specific requirements and leverages the underlying hardware in a fast and efficient way by construction. Moreover, our method has a high scalability with respect to the number of input states and the complexity of a single state. Measurements show significant performance improvements compared to traditional exploration approaches leveraging the CPU on our evaluation scenarios.

Weitere Links

https://link.springer.com/chapter/10.1007/978-3-030-38991-8_15,
https://umtl.cs.uni-saarland.de/paper_preprints/paper_koester_fang_19.pdf

FANG: Fast and Efficient Successor-State Generation for Heuristic Optimization on GPUs

Abstrakt

Weitere Links

Folgen Sie uns auf:

Herausgeber

Newsletter

Standorte