| Journal: | Pesquisa operacional |
| Database: | PERIÓDICA |
| System number: | 000313123 |
| ISSN: | 0101-7438 |
| Authors: | Silva, Geiza Cristina da1 Ochi, Luiz Satoru1 Martins, Simone Lima |
| Institutions: | 1Universidade Federal Fluminense, Instituto de Computacao, Niteroi, Rio de Janeiro. Brasil |
| Year: | 2006 |
| Season: | May-Ago |
| Volumen: | 26 |
| Number: | 2 |
| Pages: | 321-360 |
| Country: | Brasil |
| Language: | Portugués |
| Document type: | Artículo |
| Approach: | Analítico, descriptivo |
| English abstract | The Maximum Diversity Problem (MDP) consists of, given a set N with n elements, selecting a subset M Ì N such that the elements of M have the most possible diversity among them. The MDP belongs to the class of NP-Hard problems limiting the exclusive use of exact methods and turning attractive the development of heuristics to solve the problem. In this work we propose constructive and local search heuristics which are used in different versions of GRASP (Greedy Randomized Adaptive Search Procedure). We also analyze the impact of this heuristics in the GRASP performance. Computational results show that the proposed algorithms always find an optimal solution when this one is known and, for larger instances, produce an average performance better than well known versions of GRASP from the literature |
| Portuguese abstract | O Problema da Diversidade Máxima (PDM) consiste em, dado um conjunto N composto de n elementos, selecionar um subconjunto M Ì 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 |
| Disciplines: | Matemáticas |
| Keyword: | Matemáticas aplicadas, Algoritmos heurísticos, GRASP, Metaheurísticas, Problema da diversidad máxima |
| Keyword: | Mathematics, Applied mathematics, Heuristic algorithms, GRASP, Metaheuristics, Maximum diversity problem |
| Full text: | Texto completo (Ver HTML) |
