Construção e comparação de heurísticas: estudos de caso aplicados ao problema da diversidade máxima.

Abstract

The Maximum Diversity Problem (PDM) consists of determining, from a set V with n elements, a subset S of V with m (m < n) elements, in such a way that the diversity (which is calculated by adding the edges of the graph) between the ordered pairs {x, y} of S is as large as possible. This work presents implementations of two heuristic algorithms that use the Local Search (BL) method in their structures. The first is based on probabilities as a selection criterion and the second is based on the greedy principle. The implementations are tested on benchmark instances in the literature and on instances generated by two case studies that were introduced at the Federal University of Ceará - Campus Russas. To the best of our knowledge, we are among the first to carry out a comparative approach between heuristic algorithms and an exact method about PDM. The results of the computational experiments highlight that the developed heuristics are able to solve the PDM and obtain results as good as those obtained by the exact method of Soares et al. (2018) with the instances of the case studies. In relation to the instances of the literature, the experiments show that the developed algorithms obtained, in most tests performed, results as good or better than those achieved by the Soares Heuristic (HS), which was used for comparative purposes.