Aplicação de aprendizado de máquina supervisionado para o problema da diversidade máxima em grafos

Abstract

The Maximum Diversity Problem in Graphs, classified as NP-hard, seeks to select subsets of vertices that maximize the sum of the distances between them, representing a significant computational challenge for large-scale instances. This work proposes the application of supervised machine learning techniques to optimize vertex allocation in graphs, using labels generated from exact algorithms and metaheuristics to create a training dataset. The methodology includes graph modeling, extraction of relevant features, and training of supervised models. The results indicate that the supervised models achieved a proximity of 91% to 95% compared to the results obtained by the metaheuristic, while also demonstrating good generalization capacity. It is concluded that supervised learning can be an efficient strategy for solving the Maximum Diversity Problem, especially when combined with metaheuristics to generate labels for large-scale instances to be used in training, making the models applicable in complex and large-scale contexts.