On memetic search for the max-mean dispersion problem
  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.
