Banca de DEFESA: MATEUS CARVALHO DA SILVA

Uma banca de DEFESA de MESTRADO foi cadastrada pelo programa.
DISCENTE : MATEUS CARVALHO DA SILVA
DATA : 13/12/2023
HORA: 15:00
LOCAL: Online
TÍTULO:

Aplicações de algoritmos genéticos de chaves aleatórias enviesadas e formulações para o problema da coloração de Grundy e o problema da coloração conexa de Grundy

PALAVRAS-CHAVES:

otimização combinatória; coloração de grafos; número de Grundy; BRKGA; análise de pior caso.

PÁGINAS: 49
RESUMO:

Dado um grafo G, seu número de Grundy $\Gamma(G)$ define o comportamento de pior caso para a conhecida e amplamente utilizada heurística de coloração gulosa \textit{first-fit}. Mais especificamente, $\Gamma(G)$ é o maior $k$ para o qual uma $k$-coloração  pode ser obtida com a heurística \textit{first-fit}. O número de Grundy conexo $\Gamma_c(G)$ fornece o comportamento do pior caso para a heurística de coloração \textit{first-fit} conexa, ou seja, aquela em que cada vértice a ser colorido, exceto o primeiro, é adicionado adjacente a um vértice já colorido. Ambos os problemas são NP-difíceis. Nesta dissertação, apresentamos abordagens heurísticas e exatas para o problema da coloração de Grundy e o problema de coloração de Grundy conexo, que são problemas de otimização consistindo na obtenção do número de Grundy e do número de Grundy conexo, respectivamente. Nesse estudo é proposto o uso do algoritmo genético de chaves aleatórias viesado (\textit{Biased random-key genetic algorithm} - BRKGA) e do uso de formulações de programação inteira usando uma abordagem mais tradicional (padrão) e uma por representativos. Também é proposto um novo limite superior combinatório que é válido para ambos os problemas e um algoritmo usando programação dinâmica para o seu cálculo. Os experimentos computacionais mostram que o novo limite superior pode melhorar o limite para vários casos em relação a um limite combinatório bem estabelecido disponível na literatura. Os resultados também evidenciam que a formulação por representativos tem um desempenho geral superior que a formulação padrão, alcançando melhores resultados para as instâncias mais densas, enquanto esta última tem melhor desempenho para as mais esparsas para o problema dos números de Grundy. Contudo mostramos que este tipo de formulações com programação inteira são computacionalmente impraticáveis para a versão conexa. Além disso, o BRKGA pode encontrar soluções de alta qualidade para ambos os problemas e pode ser usado com confiança em grandes instâncias onde as formulações falham para o problema da coloração de Grundy.

MEMBROS DA BANCA:
Presidente - 2115562 - RAFAEL AUGUSTO DE MELO
Interno - 2011187 - FREDERICO ARAUJO DURAO
Externo à Instituição - PEDRO HENRIQUE GONZÁLEZ SILVA - UFRJ
Externo à Instituição - MAURICIO GUILHERME DE CARVALHO RESENDE