On memetic search for the max-mean dispersion problem
This work provides an incremental improvement for solving a computationally difficult optimization problem relevant to various applications.
The paper tackles the NP-hard max-mean dispersion problem by developing a memetic algorithm that improves or matches best known results for 159 out of 160 benchmark instances, including improving 59 of the 60 most challenging ones, with a 100% success rate and short computing time.
Given a set $V$ of $n$ elements and a distance matrix $[d_{ij}]_{n\times n}$ among elements, the max-mean dispersion problem (MaxMeanDP) consists in selecting a subset $M$ from $V$ such that the mean dispersion (or distance) among the selected elements is maximized. Being a useful model to formulate several relevant applications, MaxMeanDP is known to be NP-hard and thus computationally difficult. In this paper, we present a highly effective memetic algorithm for MaxMeanDP which relies on solution recombination and local optimization to find high quality solutions. Computational experiments on the set of 160 benchmark instances with up to 1000 elements commonly used in the literature show that the proposed algorithm improves or matches the published best known results for all instances in a short computing time, with only one exception, while achieving a high success rate of 100\%. In particular, we improve 59 previous best results out of the 60 most challenging instances. Results on a set of 40 new large instances with 3000 and 5000 elements are also presented. The key ingredients of the proposed algorithm are investigated to shed light on how they affect the performance of the algorithm.