Application of biased random-key genetic algorithm and formulations for the Grundy coloring problem and the connected Grundy coloring problem

Dado um grafo G, seu número de Grundy Γ(G) define o comportamento de pior caso para a conhecida e amplamente utilizada heurística de coloração gulosa first-fit. Mais especificamente, Γ(G) é o maior k para o qual uma k-coloração pode ser obtida com a heurística first-fit. O número de Grundy conexo Γc(G) fornece o comportamento do pior caso para a heurística de coloração 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 (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

Grantor dc:publisher

Universidade Federal da Bahia

Year dc:date.issued

2023

Author dc:creator

• Silva, Mateus Carvalho

• Otimização combinatória
• Coloração de grafos
• Número de Grundy
• BRKGA
• Análise de pior caso

Statement dc:rights

• Acesso Aberto

Language dc:language

eng

Repository record dc:identifier.uri

https://repositorio.ufba.br/handle/ri/39322

OAI identifier oai:identifier

oai:repositorio.ufba.br:ri/39322