New heuristics for the maximum diversity problem |
| |
Authors: | Geiza C Silva Marcos R Q de Andrade Luiz S Ochi Simone L Martins Alexandre Plastino |
| |
Institution: | 1.Departamento de Ciência da Computa??o,Universidade Federal Fluminense,Niterói,Brazil |
| |
Abstract: | The maximum diversity problem (MDP) consists of identifying, in a population, a subset of elements, characterized by a set
of attributes, that present the most diverse characteristics among the elements of the subset. The identification of such
solution is an NP-hard problem. Some heuristics are available to obtain approximate solutions for this problem. In this paper,
we propose different GRASP heuristics for the MDP, using distinct construction procedures and including a path-relinking technique.
Performance comparison among related work and the proposed heuristics is provided. Experimental results show that the new
GRASP heuristics are quite robust and are able to find high-quality solutions in reasonable computational times.
G.C. Silva’s work sponsored by CAPES MSc scholarship. L.S. Ochi’s work sponsored by CNPq research grants 304103/2003-9 and
550059/2005-9. S.L. Martins’s work sponsored by CNPq research grant 475124/03-0. A. Plastino’s work sponsored by CNPq research
grants 300879/00-8 and 475124/03-0. |
| |
Keywords: | Maximum diversity problem GRASP Path relinking Metaheuristics |
本文献已被 SpringerLink 等数据库收录! |
|