کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
480506 | 1445973 | 2016 | 21 صفحه PDF | دانلود رایگان |
• The maximally diverse grouping problem is a difficult combinatorial optimization problem.
• This is a typical grouping problem with wide applications.
• An innovative heuristic algorithm is proposed for solving the problem.
• The proposed method discovers new best known result for a number of benchmark instances.
• The behavior of the proposed algorithm is analysed.
The maximally diverse grouping problem (MDGP) is to partition the vertices of an edge-weighted and undirected complete graph into m groups such that the total weight of the groups is maximized subject to some group size constraints. MDGP is a NP-hard combinatorial problem with a number of relevant applications. In this paper, we present an innovative heuristic algorithm called iterated maxima search (IMS) algorithm for solving MDGP. The proposed approach employs a maxima search procedure that integrates organically an efficient local optimization method and a weak perturbation operator to reinforce the intensification of the search and a strong perturbation operator to diversify the search. Extensive experiments on five sets of 500 MDGP benchmark instances of the literature show that IMS competes favorably with the state-of-the-art algorithms. We provide additional experiments to shed light on the rationality of the proposed algorithm and investigate the role of the key ingredients.
Journal: European Journal of Operational Research - Volume 254, Issue 3, 1 November 2016, Pages 780–800