GRASP para o PQA: um limite de aceitação para soluções iniciais

Pesquisa Operacional

Maria Cristina Range²  Nair Maria Maia De Abreu¹  Paulo Oswaldo Boaventura-netto¹ 

[1] ,UFES CT 1Departamento de Informática

关键词: GRASP;    metaheurísticas;    Problema Quadrático de Alocação;    GRASP;    metaheuristics;    Quadratic Assignment Problem;   

DOI  :  10.1590/S0101-74382000000100006

来源: SciELO

【 摘 要 】

O Problema Quadrático de Alocação (PQA) pertence à classe dos problemas NP-Hard e desafia os pesquisadores tanto em sua teoria quanto em sua parte computacional. Pela sua alta complexidade muitos métodos heurísticos têm sido desenvolvidos para tentar resolvê-lo aproximadamente. A metaheurística GRASP (greedy randomized adaptive search procedures) se mostrou bastante eficiente. Neste trabalho, uma proposta para descartar soluções iniciais supostamente ruins é apresentada com base na normalização de custos calculadas num intervalo entre limites de solução. Para este GRASP restrito, foi observada uma redução do tempo computacional para encontrar as soluções ótimas ou soluções viáveis de boa qualidade quando comparado ao GRASP original.

【 授权许可】

CC BY   
 All the contents of this journal, except where otherwise noted, is licensed under a Creative Commons Attribution License