Unsupervised Learning to Generate Initial Solutions to the Problem of Maximum Diversity

The Maximum Diversity Problem (MDP) aims to select a subset of elements maximizing total dispersion. This work proposes a constructive heuristic based on the learnheuristic paradigm, integrating unsupervised machine learning to generate initial solutions. The method extracts 11 structural features from the vertices via stochastic approximations of quasi-linear cost O(n * A). It then applies clustering (k-means and DBSCAN) and a proportional allocation mechanism to compose the solution. Tests on 315 instances of MDPLib showed an average gap of 8% to 9% in relation to the state of the art, with low variability in 30 executions. The approach processed instances of up to 3000 vertices in seconds, demonstrating high scalability. The results indicate that the methodology is a promising alternative for the rapid generation of initial solutions in hybrid combinatorial optimization pipelines.