A GRASP algorithm with Tabu Search improvement for solving the maximum intersection of k-subsets problem

Alejandra Casado (), Sergio Pérez-Peló (), Jesús Sánchez-Oro () and Abraham Duarte ()
Additional contact information
Alejandra Casado: Universidad Rey Juan Carlos
Sergio Pérez-Peló: Universidad Rey Juan Carlos
Jesús Sánchez-Oro: Universidad Rey Juan Carlos
Abraham Duarte: Universidad Rey Juan Carlos

Journal of Heuristics, 2022, vol. 28, issue 1, No 5, 146 pages

Abstract: Abstract The selection of individuals with similar characteristics from a given population have always been a matter of interest in several scientific areas: data privacy, genetics, art, among others. This work is focused on the maximum intersection of k-subsets problem (kMIS). This problem tries to find a subset of k individuals with the maximum number of features in common from a given population and a set of relevant features. The research presents a Greedy Randomized Adaptive Search Procedure (GRASP) where the local improvement is replaced by a complete Tabu Search metaheuristic with the aim of further improving the quality of the obtained solutions. Additionally, a novel representation of the solution is considered to reduce the computational effort. The experimental comparison carefully analyzes the contribution of each part of the algorithm to the final results as well as performs a thorough comparison with the state-of-the-art method. Results, supported by non-parametric statistical tests, confirms the superiority of the proposal.

Keywords: kMIS; GRASP; Tabu search; Metaheuristics (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10732-022-09490-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:28:y:2022:i:1:d:10.1007_s10732-022-09490-8

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-022-09490-8

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().