A tabu search based memetic algorithm for the Max-Mean dispersion problem
From MaRDI portal
Abstract: Given a set of elements and a distance matrix among elements, the max-mean dispersion problem (MaxMeanDP) consists in selecting a subset from 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.
Recommendations
- An exact semidefinite programming approach for the max-mean dispersion problem
- A two-phase intensification tabu search algorithm for the maximum min-sum dispersion problem
- A hybrid three-phase approach for the Max-Mean dispersion problem
- A hybrid heuristic approach based on a quadratic knapsack formulation for the max-mean dispersion problem
- VNS variants for the Max-Mean dispersion problem
Cites work
- scientific article; zbMATH DE number 1062113 (Why is no real title available?)
- A Gentle Introduction to Memetic Algorithms
- A branch and bound algorithm for the maximum diversity problem
- A heuristic approach for the max-min diversity problem based on max-clique
- A hybrid heuristic approach based on a quadratic knapsack formulation for the max-mean dispersion problem
- A hybrid metaheuristic method for the maximum diversity problem
- A hybrid three-phase approach for the Max-Mean dispersion problem
- A simple and effective algorithm for the MaxMin diversity problem
- An efficient memetic algorithm for the graph partitioning problem
- Construction and improvement algorithms for dispersion problems
- Fundamentals of scatter search and path relinking
- GRASP and path relinking for the equitable dispersion problem
- GRASP and path relinking for the max-min diversity problem
- Heuristic algorithms for the maximum diversity problem
- Iterated tabu search for the maximum diversity problem
- Maxminmin \(p\)-dispersion problem: a variable neighborhood search approach
- Tabu search and GRASP for the maximum diversity problem
- Tabu search versus GRASP for the maximum diversity problem
- The equitable dispersion problem
Cited in
(16)- Methods for improving the efficiency of swarm optimization algorithms. A survey
- An exact semidefinite programming approach for the max-mean dispersion problem
- Two-stage solution-based tabu search for the multidemand multidimensional knapsack problem
- VNS variants for the Max-Mean dispersion problem
- A two-phase intensification tabu search algorithm for the maximum min-sum dispersion problem
- Multiple phase tabu search for bipartite Boolean quadratic programming with partitioned variables
- Effective metaheuristic algorithms for the minimum differential dispersion problem
- An opposition-based memetic algorithm for the maximum quasi-clique problem
- Tabu search guided by reinforcement learning for the max-mean dispersion problem
- A review on discrete diversity and dispersion maximization from an OR perspective
- Reinforcement learning enhanced multi-neighborhood tabu search for the max-mean dispersion problem
- A memetic algorithm based on reformulation local search for minimum sum-of-squares clustering in networks
- A hybrid three-phase approach for the Max-Mean dispersion problem
- A two-phase tabu search based evolutionary algorithm for the maximum diversity problem
- A hybrid metaheuristic of integrating estimation of distribution algorithm with Tabu search for the max-mean dispersion problem
- A hybrid heuristic approach based on a quadratic knapsack formulation for the max-mean dispersion problem
This page was built for publication: A tabu search based memetic algorithm for the Max-Mean dispersion problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q342388)
