Parallel hybrid metaheuristics for solving the firefighter problem using the GPU

Abstract

Das Firefighter Problem (FFP) ist ein deterministisches diskretes Zeitmodell, das die Ausbreitung eines Feuers oder eines anderen Problems über einen ungerichteten Graphen simuliert. Es bietet eine Möglichkeit, Brandbekämpfungsstrategien zu entwickeln, indem eine bestimmte Anzahl von Firefightern auf strategischen Punkten in jedem Zeitschritt eingesetzt wird, um so viele Knoten wie möglich vor Feuer zu retten. Das Modell findet Anwendung in zahlreichen Bereichen, wo es um die Verbreitung von verschiedenen Arten von Information geht. Unter Anderem zählen dazu Vakzinationsstrategien, Finanzkapitalflüsse, virales Marketing sowie die Verbreitung von Viren in Computernetzwerken. In mehreren Studien wurde gezeigt, dass das FFP für bestimmte Arten von Graphen [CC17] und eine bestimmte Anzahl der eingesetzten Feuerwehrleute [BCR13] NP-schwer ist. Mit dem Ziel, Strategien für eine effizientere Lösung des FFP zu finden, wird hier eine parallele hybride Metaheuristik auf einer GPU mittels CUDA implementiert. Die hybride Metaheuristik beinhaltet einen parallelen Ant Colony Optimization Algorithmus (ACO), der eine dynamische Kandidatenliste und Heuristik anwendet, welche die Topologie des Graphen zu jedem Zeitschritt berücksichtigen und dadurch den Suchraum reduzieren. Des Weiteren, wird eine parallele Variante der Variable Neighborhood Search (VNS) eingeführt und im Anschluss mit der ACO Implementierung kombiniert. Zusätzlich werden sequentielle Versionen des ACO, der VNS und der hybriden Metaheuristik entwickelt um die Effizienz der parallelen Implementierungen zu testen. Abschließend wird eine Gegenüberdarstellung der entwickelten Algorithmen mit vorherigen Arbeiten [BBGM+14, HWR15] vorgenommen. Für die Leistungsbewertungstests wird dieselbe Testkonfiguration wie in früheren Arbeiten, welche Benchmark-Instanzen mit 120 Graphen unterschiedlicher Dichte und Größe enthalten, verwendet. Testergebnisse zeigen, dass der vorgeschlagene sequenzielle ACO eine durchschnittliche Verbesserung von 10,47% gegenüber der ursprünglichen ACO Implementierung erreicht. Eine weitere Erkenntnis besteht darin, dass, verglichen mit jedem einzelnen Algorithmus, die Kombination von ACO und VNS eine Verbesserung der Lösungsqualität auf beiden Plattformen liefert. Die Testergebnisse der parallelisierten Algorithmen ergeben, dass jede parallele Implementierung ihre sequenzielle Entsprechung übertrifft, wobei auch die Lösungsqualität verbessert wird. Die erreichten Speed-ups betragen bis zu 141x (ACO), 106x (VNS) und 114x (hybrider Algorithmus).

The Firefighter Problem (FFP) is a deterministic discrete-time model which simulates the spread of a fire or other problem over an undirected graph. It offers a possibility of developing fire containment strategies by deploying a given number of firefighters on strategic points at each time step with the goal of saving as many nodes from fire as possible. The model is applied in numerous areas considering the spread of various types of information. These include, among others, vaccination strategies, financial capital flow, viral marketing and the spread of viruses in computer networks. In several studies it has been shown that the FFP is NP-hard for specific types of graphs [CC17] and the number of firefighters [BCR13] involved. With the goal of finding strategies for a more efficient solution to the FFP, a parallel hybrid metaheuristic is implemented on a GPU using CUDA. The hybrid metaheuristic comprises a parallel Ant Colony Optimization algorithm (ACO), which applies a dynamic candidate list and heuristic that take into account the topology of the graph at each time step, thereby reducing the search space. Furthermore, a parallel version of Variable Neighborhood Search (VNS) is introduced and combined with the ACO implementation. In addition, sequential versions of the ACO, the VNS and the hybrid metaheuristic are developed in order to test the efficiency of the parallel implementations. Finally, the developed algorithms are compared with previous works [BBGM+14, HWR15]. For the performance evaluation tests we used the same experimental setup as previous works, which contains a benchmark instance set of 120 graphs with different density and size. Test results show that the proposed sequential ACO achieved an average improvement of 10.47 % compared to the original ACO implementation. Another finding is that the combination of ACO and VNS provides an improvement in the solution quality compared to each algorithm on their own on both platforms. The test results of the parallelized algorithms revealed that each parallel implementation outperforms its sequential counterpart while improving the solution quality. The achieved speed-ups are up to 141x (ACO), 106x (VNS) and 114x (hybrid algorithm).