Biased random-key genetic algorithms for the minimum broadcast time problem

Abstract

The MINIMUM BROADCAST TIME (MBT) is a well-known data dissemination problem whose goal is to find a broadcast scheme that minimizes the number of steps needed to execute the broadcast operation. The WEIGHTED MINIMUM BROADCAST TIME (WMBT) is a generalization of the MBT, such that each operation has a cost. Both problems have many applications in distributed systems, e.g., the devices update process in a peer-to-peer network. This work proposes Biased Random-Key Genetic Algorithms (BRKGA) for the MBT and WMBT. A hybrid algorithm (BRKGA + Integer Linear Programming) for the MBT. Algorithms to calculate a lower bound for the MBT and WMBT. A refinement approach and methods to create instances with known optima for the MBT and WMBT. Moreover, reducing rules for the WMBT. We carry out experiments with our BRKGA on instances commonly used in the literature and also on massive synthetic instances (up to 1000 vertices), allowing us to cover many possibilities of real industry topologies. Our proposal compared state-of-the-art exact methods and heuristics. Our algorithms outperformed the best-known heuristics for the MBT and WMBT. The experiments demonstrated they are a very good alternative when exact methods cannot be applied. For all instances for the MBT with known optima value, our approaches either attained the optimal value or missed it by at most one broadcast step. For all instances for the WMBT, our approaches attained or improved the results of literature.