Banca de QUALIFICAÇÃO: ALFREDO LIMA MOURA SILVA

Uma banca de QUALIFICAÇÃO DE MESTRADO foi cadastrada pelo programa.

DISCENTE: ALFREDO LIMA MOURA SILVA
DATA: 13/11/2020
HORA: 14:00
LOCAL: Remoto
TÍTULO:

Biased Random-Key Genetic Algorithms Minimum Broadcast Time Problem

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 problem has many applications in distributed systems and swarms robots. This work proposes Biased Random-Key Genetic Algorithms (BRKGA) for the MBT. 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 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 also that it is a very good alternative for large instances that cannot be solved by current exact methods. Moreover, we are testing a hybrid algorithm, which is composed of BRKGA with Integer Linear Programming (ILP). Preliminary results indicate that this hybrid algorithm is promissing.

PALAVRAS-CHAVE:

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

PÁGINAS: 69
GRANDE ÁREA: Ciências Exatas e da Terra
ÁREA: Ciência da Computação

MEMBROS DA BANCA:
Presidente - 1114959 - RIAN GABRIEL SANTOS PINHEIRO
Interno(a) - 1647956 - ANDRE LUIZ LINS DE AQUINO
Interno(a) - 1803490 - BRUNO COSTA E SILVA NOGUEIRA
Interno(a) - 1318371 - HEITOR JUDISS SAVINO