Opposition-based learning memetic algorithm for the maximum intersection of k -subsets problem

Given m elements and n subsets of elements, the maximum intersection of k -subsets (kMIS) problem is to select k subsets of elements to maximize the number of elements simultaneously covered by all of the selected subsets. As a general model, kMIS can be used to formulate some practical problems including data privacy control, community detection, and deoxyribonucleic acid microarray technology. This paper presents an opposition-based learning memetic algorithm that integrates opposition-based learning initialization, adaptive crossover, and solution-based tabu search. Experimental results on 608 instances show that the algorithm competes favorably with the state-of-the-art methods. The importance of the algorithmic components is experimentally validated.

Authors

• Wen Sun
• Xu Li
• Jin-Kao Hao
• Wenlong Li
• Zhipeng Lü Huazhong University of Science and Technology

Keywords

• Opposition-based learning
• Solution-based tabu search
• Maximum intersection