Uma heurística ABC paralela em CUDA com decodificação gulosa para o problema do conjunto independente dominante mínimo

Abstract

The Minimum Independent Dominating Set (MIDS) problem is an NP-Hard combinatorial optimization challenge with broad applications in wireless sensor networks and the Internet of Things (IoT). Due to the intractability of exact methods for large-scale graphs, approximate approaches are essential; however, the literature focuses primarily on sequential executions on the CPU. The objective of this work is to develop and evaluate a massively parallel Artificial Bee Colony (ABC) meta-heuristic, implemented in CUDA architecture with a greedy decoding strategy for the MIDS problem. The methodology encompassed a systematic literature review, an exploratory implementation of the Ant Colony Optimization (ACO) algorithm on the GPU, and the final development of the ABC algorithm using cooperative kernels mapped in a continuous vector space. Experimental results indicated that the ABC approach achieved speedup rates of up to 62.97x compared to its sequential version, also outperforming the parallel ACO model in both solution quality and execution time. When compared to the sequential state-of-the-art (drMIDS, ILPS3, and MAE-PB), the ABC in CUDA demonstrated high competitiveness, obtaining smaller sets across various instances in the order of milliseconds. It is concluded that massive parallelization combined with swarm intelligence is a robust and highly efficient solution, enabling complex optimizations in real-time for large-scale systems.