Applying Machine Learning on Algorithm Selection for the Graph Coloring Problem

O problema de coloração de grafos é um problema NP-Completo para o qual muitos algoritmos foram desenvolvidos ao longo das últimas décadas. Por ser um problema de natureza difícil, a ideia de seleção de algoritmos torna-se relevante para que apenas o algoritmo de coloração mais apropriado seja executado. Este trabalho apresenta uma análise sistemática da aplicação de métodos de aprendizado de máquina no problema de seleção de algoritmos, utilizando coloração de grafos como um caso de estudo. Muitos trabalhos foram realizados nesta área focando em classificação de rótulo único e visualização do espaço do problema, preterindo métodos como regressão e classificação multi-rótulo. Ademais, não houve um estudo sistemático para testar alterações na lista de propriedades de grafos disponíveis como entrada do problema. Essas lacunas são endereçadas por experimentos utilizando como ponto de partida as bases de dados e propriedades consideradas em trabalhos relacionados. A comparação dos resultados mostra que os métodos utilizados neste trabalho geram bons resultados em termos de acurácia ao selecionar os melhores algoritmos de coloração. Ficou claro que a acurácia do algoritmo de aprendizado é muito dependente do critério de desempenho e também pode ser impactada pelas propriedades de grafos. A ideia de classificação multi-rótulo neste contexto traz uma melhora relevante, pois quando há disponibilidade de tempo, alguns algoritmos de coloração alcançam valores similares para o número cromático. Por fim, de um portfólio de oito algoritmos, foi possível recomendar na média apenas quatro destes, com uma acurácia de 89%, ou apenas um, com uma acurácia de 79%.