GRASP with Path-Relinking for the Maximum Diversity Problem

摘要

The Maximum Diversity Problem (MDP) consists in identifying, in a population, a subset of elements, characterized by a set of attributes, that present the most diverse characteristics between themselves. The identification of such solution is an NP-hard problem. This paper presents a GRASP heuristic associated with the path-relinking technique developed to obtain high-quality solutions for this problem in a competitive computational time. Experimental results illustrate the effectiveness of using the path-relinking method to improve results generated by pure GRASP.