Diversity Measures for Set-Based Meta-Heuristics
Kyle N. Erwin, Andries Petrus Engelbrecht · 2020
The diversity of agents moving through a search space gives researchers insight into a heuristic's ability to explore and exploit the search space. Much of the work done on measuring diversity has focused on heuristics for continuous search spaces. Due to the lack of spatial structure among sets, these established diversity measures are not applicable to set-based algorithms. Therefore, there is a need for setbased diversity measures that give researchers the same insights for set-based heuristics as the diversity measures for continuous-based heuristics. This paper conducts a thorough investigation into the use of the Jaccard distance and the Hamming distance as methods for calculating the diversity of set-based populations. It is shown that the Jaccard distance better represents a researcher's intuition about the diversity for sets, while Hamming distance under-represents diversity. In cases where the sizes of sets are relatively small, changes in diversity calculated using the Jaccard distance are large and give impressions of chaotic movements.