Banca de DEFESA: ALFREDO LIMA MOURA SILVA

Uma banca de DEFESA de MESTRADO foi cadastrada pelo programa.
DISCENTE : ALFREDO LIMA MOURA SILVA
DATA : 12/11/2021
HORA: 09:00
LOCAL: Remoto
TÍTULO:

Biased Random-Key Genetic Algorithms for the Minimum Broadcast Time Problem

PALAVRAS-CHAVES:

Minium Broadcast Time, Biased Random-Key Genetic Algorithm, Metaheuristics, Combinatorial Optimization

PÁGINAS: 72
RESUMO:

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 and swarms robots. This work proposes Biased Random-Key Genetic Algorithms (BRKGA) and a hybrid algorithm (BRKGA + Integer Linear Programming) for the MBT and 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 is also compared with state-of-the-art exact methods and heuristics. Experimental results show that our algorithms are able to outperform the best-known heuristics for the MBT and WMBT, and also that they are a very good alternative for large instances that cannot be solved by current exact methods.

MEMBROS DA BANCA:
Presidente - 1114959 - RIAN GABRIEL SANTOS PINHEIRO
Interno - 1647956 - ANDRE LUIZ LINS DE AQUINO
Interno - 1803490 - BRUNO COSTA E SILVA NOGUEIRA
Externo à Instituição - FÁBIO PROTTI - UFF