Portal de Periódicos da CAPES

Artigo Acesso aberto Produção Nacional Revisado por pares

BIBTEX RIS

Proposta e avaliação de heurísticas grasp para o problema da diversidade máxima

2006; Sociedade Brasileira de Pesquisa Operacional; Volume: 26; Issue: 2 Linguagem: Português

10.1590/s0101-74382006000200007

1678-5142

Geiza Cristina da Silva, Luiz Satoru Ochi, Simone L. Martins,

Metaheuristic Optimization Algorithms Research

O Problema da Diversidade Máxima (PDM) consiste em, dado um conjunto N composto de n elementos, selecionar um subconjunto M <FONT FACE=Symbol>Ì</FONT> N de forma tal que os elementos de M possuam a maior diversidade possível entre eles. O PDM pertence à classe de problemas NP-Difícil limitando, com isso, o uso exclusivo de métodos exatos e tornando atrativo o desenvolvimento de novos métodos heurísticos na solução aproximada deste problema. Neste trabalho são propostos métodos heurísticos de construção e busca local que, combinados, são usados como base em diferentes versões do algoritmo GRASP (Greedy Randomized Adaptive Search Procedure). Incluímos como objetivos analisar o impacto destas heurísticas no desempenho da metaheurística GRASP. Resultados computacionais mostram que os algoritmos propostos sempre alcançam uma solução ótima quando esta é conhecida e, para instâncias maiores, apresentam um desempenho médio superior quando comparados com as melhores heurísticas GRASP da literatura.