Banca de DEFESA: ROBSON PIRES BORGES

Uma banca de DEFESA de MESTRADO foi cadastrada pelo programa.
DISCENTE : ROBSON PIRES BORGES
DATA : 24/07/2024
HORA: 10:30
LOCAL: https://meet.google.com/vmr-qpvr-gnf
TÍTULO:

Uma abordagem para o Problema da Árvore Geradora Mínima com Restrição de Diâmetro via Metaheurística BRKGA

PALAVRAS-CHAVES:

 

Árvore Geradora Mínima. Restrição de diâmetro. Heurísticas avança- das. Otimização Combinatória. NP-Difícil.

PÁGINAS: 66
RESUMO:

Este trabalho explora abordagens inovadoras para resolver o problema da Árvore Geradora Mínima com Restrição de Diâmetro (AGMRD), um importante problema de otimização combinatória em teoria dos grafos, que pode ser aplicado a diversos problemas como redes de transporte, abastecimento e energias, além de redes neurais e redes sociais. A proposta do trabalho envolve o desenvolvimento de heurísticas avançadas que, integradas à metaheurística BRKGA (Biased Random-Key Genetic Algorithm), visam gerar soluções de alta qualidade de forma eficiente. Para atingir os objetivos, foram desenvolvidas duas novas heurísticas construtivas. A primeira inicia a construção da solução através de um backbone central, composto por D − 1 vértices. A segunda heurística organiza os vértices em níveis, aproximadamente D/2, para formar a árvore geradora. Ambas as heurísticas foram implementadas no framework do BRKGA, que começa com uma população inicial gerada aleatoriamente, onde cada indivíduo representa solução viável para o problema. Além das heurísticas construtivas, o trabalho inclui a aplicação de uma heurística de busca local VND (variable neighborhood descent) para refinar as soluções obtidas. Esta busca local é baseada em propriedades e teoremas de grafos, incluindo movimentos como trocas de nós folhas, caracterizando a vizinhança N1 e melhorias entre nós pai e filho no tipoN2. Os algoritmos foram testados em instâncias conhecidas da literatura, com tamanhos variando de 50 a 500 vértices. Os resultados mostraram que as heurísticas propostas, combinadas com o BRKGA, foram capazes de produzir soluções próximas ao ótimo global de maneira consistente.

MEMBROS DA BANCA:
Externa à Instituição - ANDRÉA CYNTHIA SANTOS
Externo à Instituição - BRENO BARROS TELLES DO CARMO
Presidente - ***.630.884-** - DARIO JOSÉ ALOISE - UERN
Interno - 1669481 - FABIO FRANCISCO DA COSTA FONTES